Haskell/Solutions/More about lists

← Back to More about lists

Rebuilding lists

Exercises

Write the following functions and test them out. Don't forget the type signatures. takeInt returns the first n items in a list. So takeInt 4 [11,21,31,41,51,61] returns [11,21,31,41]. dropInt drops the first n items in a list and returns the rest. So dropInt 3 [11,21,31,41,51] returns [41,51]. sumInt returns the sum of the items in a list. 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]. 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.

1.

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

2.

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

3.

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

4.

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

5.

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
    where
    diffsAlt' :: [Int] -> [Int] -> [Int]
    diffsAlt' _ [] = []
    diffsAlt' [] _ = []
    diffsAlt' (x:xs) (y:ys) = (y-x): diffsAlt' xs ys

The map function

Exercises

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. 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 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?

1.

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)

2.

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

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
        where
                helper x = (length x, head x)
 
decode :: [(Int, a)] -> [a]
decode xs = concat $ map rep xs
        where
                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

Tips and tricks

Exercises

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..])? In the final block of exercises of the previous chapter you implemented the (!!) operator. Redo it, but this time using head and tail. (If by any chance you did it with head and tail back then, redo it with pattern matching.) 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.

2.

getElemAt :: Int -> [a] -> a
getElemAt _ [] = error "Index too large" -- a custom error message, just for extra "sugar"
getElemAt 0 ls = head ls
getElemAt n ls = getElemAt (n-1) (tail ls)

3.

-- this is just like the Prelude function last
lastOf :: [a] -> a
lastOf [] = error "Empty list"
lastOf (x:[]) = x
lastOf (_:xs) = lastOf (xs)
 
-- somewhat more complicated alternative with no pattern matching
lastOf :: [a] -> a
lastOf [] = error "Empty list"
lastOf ls =
  if (null (tail ls))
     then head ls
     else lastOf (tail ls)
 
-- this is just like the Prelude init
dropLast :: [a] -> [a]
dropLast [] = error "Empty list"
dropLast (x:[]) = []
dropLast (x:xs) = x : (dropLast xs)
 
-- again, the head/tail alternative
dropLast :: [a] -> [a]
dropLast [] = error "Empty list"
dropLast ls =
  if (null (tail ls))
     then []
     else ((head ls) : dropLast (tail ls))