Haskell/Solutions/More about lists

← Back to More about lists

Constructing lists

Exercises

Write the following functions and test them out. Don't forget the type declarations. 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]. Is there any difference between "scanSum (takeInt 10 [1..])" and "takeInt 10 (scanSum [1..])"? diffs returns a list of the differences between adjacent items. So diffs [3,5,6,8] returns [2,1,2]. (Hint: write a second function that takes two lists and finds the difference between corresponding items).

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.

scanSum :: [Int] -> [Int]
scanSum = scanSum' 0
 
scanSum' :: Int -> [Int] -> [Int]
scanSum' tot [] = []
scanSum' tot (x:xs) = x + tot : scanSum' (x + tot) xs
 
----------- ALTERNATIVELY -----------------
scanSum ::  [Integer] -> [Integer]
scanSum (a:[]) = a:[]
scanSum (a:b:as) = a : scanSum ((a+b):as)

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.

5.

diffs          :: [Int] -> [Int]
diffs []       = []
diffs (x:[])   = []
diffs (x:y:xs) = (y-x) : diffs (y:xs)
 
-- alternative which uses the recommended second 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

Exercises

The (!!) operator takes a list and an Int as arguments and returns the list element at the position given by the Int (starting from zero). Write a function which performs that task using head and tail. 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 with the usual pattern matching schemes or 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.

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)

2.

-- this is just like the Prelude function last
lastOf :: [a] -> a
lastOf [] = error "Empty list"
lastOf (x:[]) = x
lastOf (_:xs) = lastOf (xs)
 
-- more complicated alternative with head and tail only and no pattern matching
lastOf :: [a] -> a
lastOf [] = error "Empty list"
lastOf ls =
  if (tail ls == [])
     then head ls
     else lastOf ls
 
<!-- *Check Correction* I think the dropLast type was wrong. Change from "dropLast :: [a]" -> a to "dropLast :: [a] -> [a]" -->
 
-- 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 (tail ls == [])
     then []
     else ((head ls) : dropLast (tail ls))

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

A simple one:

rle ::(Eq a) => [a] -> [(Int, a)]    
rle (x:xs) = zip (map length (group (x:xs))) (head (group (x:xs)))

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