Haskell/Solutions/Lists II

< Haskell‎ | Solutions(Redirected from Haskell/Solutions/More about lists)

Rebuilding listsEdit


Write the following functions and test them out. Don't forget the type signatures.

  1. takeInt returns the first n items in a list. So takeInt 4 [11,21,31,41,51,61] returns [11,21,31,41].
  2. dropInt drops the first n items in a list and returns the rest. So dropInt 3 [11,21,31,41,51] returns [41,51].
  3. sumInt returns the sum of the items in a list.
  4. scanSum adds the items in a list and returns a list of the running totals. So scanSum [2,3,4,5] returns [2,5,9,14].
  5. diffs returns a list of the differences between adjacent items. So diffs [3,5,6,8] returns [2,1,2]. (Hints: one solution involves writing an auxiliary function which takes two lists and calculates the difference between corresponding elements. Alternatively, you might explore the fact that for lists with at least two elements can be matched to a (x:y:ys) pattern.)
The first three functions are in Prelude, under the names take, drop, and sum.


takeInt          :: Int -> [a] -> [a]
takeInt 0 _      = []
takeInt _ []     = []
takeInt n (x:xs) = x : takeInt (n-1) xs


dropInt          :: Int -> [a] -> [a]
dropInt 0 list   = list
dropInt _ []     = []
dropInt n (x:xs) = dropInt (n-1) xs


sumInt        :: [Int] -> Int
sumInt []     = 0
sumInt (x:xs) = x + sumInt xs


--------- USING Helper function -----------
scanSum :: [Int] -> [Int]
scanSum = scanSum' 0

scanSum' :: Int -> [Int] -> [Int]
scanSum' tot [] = []
scanSum' tot (x:xs) = x + tot : scanSum' (x + tot) xs

---- USING takeInt, dropInt and sumInt ----
scanSum :: [Int] -> [Int]
scanSum [] = []
scanSum (x:[]) = [x]
scanSum (x:xs) = x : scanSum ((x + sumInt (takeInt 1 xs)) : dropInt 1 xs)

----------- USING (a:b:as) ----------------
scanSum ::  [Int] -> [Int]
scanSum [] = []
scanSum (a:[]) = a:[]
scanSum (a:b:as) = a : scanSum ((a+b):as)


diffs          :: [Int] -> [Int]
diffs []       = []
diffs (x:[])   = []
diffs (x:y:xs) = (y-x) : diffs (y:xs)

-- alternative with the auxiliary function:
diffsAlt :: [Int] -> [Int]
diffsAlt [] = []
diffsAlt (x:xs) = diffsAlt' (x:xs) xs
    diffsAlt' :: [Int] -> [Int] -> [Int]
    diffsAlt' _ [] = []
    diffsAlt' [] _ = []
    diffsAlt' (x:xs) (y:ys) = (y-x): diffsAlt' xs ys

The map functionEdit

  1. Use map to build functions that, given a list xs of Ints, return:
    • A list that is the element-wise negation of xs.
    • A list of lists of Ints xss that, for each element of xs, contains the divisors of xs. You can use the following function to get the divisors:
      divisors p = [ f | f <- [1..p], p `mod` f == 0 ]
    • The element-wise negation of xss.
  2. Implement a Run Length Encoding (RLE) encoder and decoder.
    • The idea of RLE is simple; given some input:
      compress it by taking the length of each run of characters:(4,'a'), (2, 'b'), (3, 'a')
    • The concat and group functions might be helpful. In order to use group, you will need to import the Data.List module. You can access this by typing :m Data.List at the ghci prompt, or by adding import Data.List to your Haskell source code file.
    • 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) Assuming numeric characters are forbidden in the original string, how would you parse that string back into a list of tuples?


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.
-- The dots are just another higher-order trick. (g . f) x = g(f(x)) 
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)


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)

Here is my version which uses group and map in a single function with a anonymous helper function (I only included the solution for encode because in my opinion there are a few very useful functions that need to be introduced prior to going through the other functions. concatMap, which can be used as an inverse of map and replicate, which can be used for repetition.):

import Data.List

encode :: [Char] -> [(Int, Char)]
encode list = map go (group list)
go (x:xs) = (length (x:xs), 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

This is a version I made to learn to use map and group.

import Data.List

count_tuple (x:xs) = (length (x:xs) , x)

map count_tuple (group "aaaaaabbbbbcccccccaaaaaaaaaaaaaaa")

Here's my (Zevras) solution:

import Data.List

encode :: (Eq a) => [a] -> [(Int, a)]
encode x = map helper $ group x
		helper x = (length x, head x)

decode :: [(Int, a)] -> [a]
decode xs = concat $ map rep xs
		rep (n, x) = take n $ repeat x

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 &&&).

Here’s my solution to the “bonus” problem. The function is called extract here.

-- Takes a string like "2a4c11b" and turns it into its encoded
-- counterpart; in this case: [(2, 'a'), (4, 'c'), (11, 'b')].
extract :: String -> [(Int, Char)]
extract [] = []
extract (x:xs) = extract' [x] xs

-- helper function to keep track of the numbers.
-- ns : List of digits ("1234").
extract' :: String -> String -> [(Int, Char)]
extract' _ [] = []
extract' ns [x] = [(read ns, x)] -- the last element of the string
                                 -- is assumed to be a non-digit.
extract' ns (y:z:zs) = 
  if y `elem` ['0','1','2','3','4','5','6','7','8','9']
    then extract' (ns ++ [y]) (z:zs)
    else (read ns, y) : extract' [z] zs

A possible answer to the question "How would you convert the list of tuples (e.g. [(4,'a'), (6,'b')]) into a string (e.g. "4a6b")?"

-- Convert a list of tuples into a string.
-- For example, [(4, 'a'), (6, 'b')] becomes "4a6b".

-- I begin with a function that converts a single tuple into a string two characters long.
-- The intToDigit function converts a interger into a character. For example: intToDigit 1 = '1'.
-- If intToDigit isn't used, GHCi will throw a type error.

import Data.Char

tupleToString :: (Int, Char) -> [Char]
tupleToString x = (intToDigit.fst) x:(snd x):[]

-- Now we'll map this function to a list of tuples. We get back a list of strings.
-- For example: tuplesToStrings [(1, 'a'), (2, 'b')] = ["1a", "2b"].

tuplesToStrings [] = []
tuplesToStrings (x:xs) = tupleToString x : tuplesToStrings xs

-- A little concat and we're done.

tuplesToString xs = (concat . tuplesToStrings) xs

Test with the function call
tuplesToString [(4,'a'), (6,'b')] ==> "4a6b"

Tips and tricksEdit

  1. With respect to your solutions to the first set of exercises in this chapter, is there any difference between scanSum (takeInt 10 [1..]) and takeInt 10 (scanSum [1..])?
  2. Write functions that when applied to lists give the last element of the list and the list with the last element dropped. That can be done either with pattern matching or by using head and tail only. We suggest you to try, and compare, both approaches. (Note that this functionality is provided by Prelude through the last and init functions.)

1. Both scanSum (takeInt 10 [1..]) and takeInt 10 (scanSum [1..]) have the same value. This is possible because Haskell is a lazy language, thus in both cases the result is only evaluated as needed.


-- this is just like the Prelude function last
lastOf :: [a] -> a
lastOf [] = error "Empty list"
lastOf (x:[]) = x
lastOf (_:xs) = lastOf (xs)
-- this is just like the Prelude init
dropLast :: [a] -> [a]
dropLast [] = error "Empty list"
dropLast (x:[]) = []
dropLast (x:xs) = x : (dropLast xs)