Haskell/Solutions/List processing
Folds[edit]
Exercises 


and [] = True and (x:xs) = x && and xs As a fold and = foldr (&&) True or [] = False or (x:xs) = x  or xs As a fold or = foldr () False maximum :: Ord a => [a] > a  omitting type declaration results in "Ambiguous type variable" error maximum = foldr1 max foldl1 also works, but not if you want infinite lists. Not that you can ever be sure of the maximum of an infinite list. minimum :: Ord a => [a] > a minimum = foldr1 min Same as above. Using foldl'; you will want to import Data.List in order to do the same. reverse :: [a] > [a] reverse = foldl' flippedCons [] where flippedCons xs x = x : xs
Scans[edit]
Exercises 

Write your own definition of scanr , first using recursion, and then using foldr . Do the same for scanl first using recursion then foldl . 
 with recursion scanr2 step zero [] = [zero] scanr2 step zero (x:xs) = (step x (head prev)):prev where prev = scanr2 step zero xs scanl2 step zero [] = [zero] scanl2 step zero (x:xs) = zero : scanl2 step (step zero x) xs  An alternative scanl with poorer performance. The problem is that  last and init, unlike head and tail, must run through the entire  list, and (++) does the same with its first argument. scanl2Slow step zero [] = [zero] scanl2Slow step zero xs = prev ++ (step (last prev) (last xs)):[] where prev = scanl2Slow step zero (init xs) with fold scanr3 step zero xs = foldr step' [zero] xs where step' x xs = (step x (head xs)):xs  This implementation has poor performance due to (++), as explained  for scanl2Slow. In general, using (++) to append to a list  repeatdely is not a good idea. scanl3Slow step zero xs = foldl step' [zero] xs where step' xs x = xs ++ (step (last xs) x):[]
In the efficient scanr
implementations above, we use head
and tail
as a way to avoid having to break down the list argument with pattern matching in the where clause only to assemble it back in the righthand side. In the Pattern matching chapter, we will see how aspatterns allow us to reach the same effect without needing head
.
Exercises 

Define the following functions:

factList n = scanl1 (*) [1..n] factList' n = scanl (*) 1 [2..n]
filter and list comprehension[edit]
Exercises 

Write a 
returnDivisible :: Int > [Int] > [Int] returnDivisible n xs = [ x  x<xs , (mod x n) == 0 ] or, if you prefer to use filter... returnDivisible :: Int > [Int] > [Int] returnDivisible n = filter (\x > (mod x n) == 0)
Exercises 


The artificial constraints of the exercise suggest a solution which uses head and tail instead of pattern matching.
choosingTails :: [[Int]] > [[Int]] choosingTails ls = [ tail l  l < ls, not (null l), head l > 5 ]
The boolean conditions in a list comprehension are evaluated in order, so if you swapped the conditions like this:
choosingTails ls = [ tail l  l < ls, head l > 5, not (null l) ]
if one of the l turned out to be an empty list the program would try to apply head on it, which would cause an error. Putting not (null l) first causes the program to, when it meets an empty list, to shortcircuit the conditional  that is, ignore the second condition since the first one being false is enough for rejecting the list  thus avoiding doing head [] and the error that follows.
Exercises 

Over this section we've seen how list comprehensions are essentially syntactic sugar for filter and map. Now work in the opposite direction and define alternative versions of the filter and map using the list comprehension syntax. 
alternativeFilter :: (a > Bool) > [a] > [a] alternativeFilter cond xs = [ x  x<xs, cond x ] alternativeMap :: (a > b) > [a] > [b] alternativeMap f xs = [ f x  x<xs ] no need for any condition, as all x will be accepted
Exercises 

Rewrite doubleOfFirstForEvenSeconds using filter and map instead of list comprehension. 
doubleOfFirstForEvenSeconds' :: [(Int, Int)] > [Int] doubleOfFirstForEvenSeconds ps = let f pair = 2 * (fst pair) g pair = isEven (snd pair) in map f (filter g ps) isEven, naturally, remains the same. isEven :: Int > Bool isEven n = (mod n 2 == 0)  a small teaser  using the (.) function composition operator which will be formally introduced on "More on functions". doubleOfFirstForEvenSeconds' :: [(Int, Int)] > [Int] doubleOfFirstForEvenSeconds' ps = map ((2*) . fst) (filter (isEven . snd) ps)