Haskell/Solutions/List processing

From Wikibooks, open books for an open world
Jump to: navigation, search

← Back to List processing


Folds[edit]

Exercises
  1. Define the following functions recursively (like the definitions for sum, product and concat above), then turn them into a fold:
    • and :: [Bool] -> Bool, which returns True if a list of Bools are all True, and False otherwise.
    • or :: [Bool] -> Bool, which returns True if any of a list of Bools are True, and False otherwise.
  2. Define the following functions using foldl1 or foldr1:
    • maximum :: Ord a => [a] -> a, which returns the maximum element of a list (hint: max :: Ord a => a -> a -> a returns the maximum of two values).
    • minimum :: Ord a => [a] -> a, which returns the minimum element of a list (hint: min :: Ord a => a -> a -> a returns the minimum of two values).
  3. Use a fold (which one?) to define reverse :: [a] -> [a], which returns a list with the elements in reverse order.
Note that all of these are Prelude functions, so they will be always close at hand when you need them. (Also, that means you will want to use slightly different names for testing your answers in GHCi.)
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):[]
Exercises

Define the following functions:

  • factList :: Integer -> [Integer], which returns a list of factorials from 1 up to its argument. For example, facList 4 = [1,2,6,24].
More to be added
factList n = scanl1 (*) [1..n]
factList' n = scanl (*) 1 [2..n]

filter and list comprehension[edit]

Exercises

Write a returnDivisible :: Int -> [Int] -> [Int] function which filters a list of integers retaining only the numbers divisible by the integer passed as first argument. For integers x and n, x is divisible by n if (mod x n) == 0 (note that the test for evenness is a specific case of that).

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
  • Write - using list comprehension syntax, a single function definition and no if, case and similar constructs - a [[Int]] -> [[Int]] which, from a list of lists of Int, returns a list of the tails of those lists using, as filtering condition, that the head of each [Int] must be larger than 5. Also, your function must not trigger an error when it meets an empty [Int], so you'll need to add an additional test to detect emptiness.
  • Does order matter when listing the conditions for list comprehension? (You can find it out by playing with the function you wrote for the first part of the exercise.)

The extraneous constraints of the exercise lead to a solution which uses head and tail instead of pattern matching.

choosingTails :: [[Int]] -> [[Int]]
choosingTails ls = [ tail l | l <- ls, not (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 (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 (l == []) first causes the program to, when it meets an empty list, to short-circuit 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)