Haskell/Solutions/List processing

From Wikibooks, the open-content textbooks collection

Jump to: navigation, search

← Back to List processing


[edit] Map

Exercises

Use map to build functions that, given a list l of Ints, returns:

  • A list that is the element-wise negation of l.
  • A list of lists of Ints ll that, for each element of l, contains the factors of l. It will help to know that
factors p = [ f | f <- [1..p], p `mod` f == 0 ]
  • The element-wise negation of ll.

In one block of code. In addition to the variations here, you can also replace Int by Integer:

negateList, negateList2 :: [Int] -> [Int]
negateList = map negate
negateList2 list = map negate list

factorList, factorList2 :: [Int] -> [[Int]]
factorList = map factors
factorList2 list = map factors list

-- There are a few possible variations for this one. If yours is different, check with a Haskell interpreter to see if it's correct.
negateFactorList, negateFactorList2, negateFactorList3, negateFactorList4 :: [Int] -> [[Int]]
negateFactorList = map (negateList . factors)
negateFactorList2 = map negateList . factorList
negateFactorList3 list = map (negateList . factors) list
negateFactorList4 list = map (map negate) (map factors list)
Exercises

Implement a Run Length Encoding (RLE) encoder and decoder.

  • The idea of RLE is simple; given some input: 
    "aaaabbaaa"
    compress it by taking the length of each run of characters: 
    (4,'a'), (2, 'b'), (3, 'a')
  • The group function might be helpful
  • What is the type of your encode and decode functions?
  • How would you convert the list of tuples (e.g. [(4,'a'), (6,'b')]) into a string (e.g. "4a6b")?
  • (bonus) How would you parse that string back into a list of tuples?

Here's my Run Length Encoding, although I don't see how I'm supposed to use map. (Maybe if the text explained group?)

encode :: Eq a => [a] -> [(Int,a)]
encode [] = []
encode [x] = [(1,x)]
encode (x:y:xs) | x == y = succHead (encode (y:xs))
                | otherwise = (1,x) : encode (y:xs)

succHead :: [(Int,a)] -> [(Int,a)]
succHead [] = [] --this should never be called by encode on any input
succHead ((n,x):ps) = (n+1,x):ps

decode :: [(Int,a)] -> [a]
decode [] = []
decode ((n,x):ps) = (repetition n x) ++ decode ps

repetition :: Int -> a -> [a]
repetition 0 _ = [] --this should never be called by decode on a properly formatted input
repetition n x = x:(repetition (n-1) x)

And here is mine using map. To understand what the group command did, I visited hayoo. If you aren't familiar with hayoo yet, take a couple of minutes to try it now. It's very useful.

import Data.List

lenwhat :: [Char] -> (Int, Char)
lenwhat x = (length x, head x)

encode :: [Char] -> [(Int, Char)]
encode "" = []
encode x = map lenwhat (group x)

decode :: [(Int, Char)] -> [Char]
decode [] = ""
decode ((l, w):xs) = (replicate l w) ++ decode xs

toRleString :: [(Int, Char)] -> [Char]
toRleString [] = ""
toRleString ((l, w):xs) = show l ++ w : rlestring xs

N.B., the RLE example is inspired from a blog post by Don Stewart on the same subject. See Don's post for a more elegant solution (which might not be immediately understandable; see Haskell/Understanding arrows for a discussion on &&&)

[edit] Folds

Exercises

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.

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).
 
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 = 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 = foldr1 min --Same as above.

[edit] Scans

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]
Retrieved from "http://en.wikibooks.org/wiki/Haskell/Solutions/List_processing"