Haskell/Solutions/Lists II
Rebuilding lists[edit]
Exercises 

Write the following functions and test them out. Don't forget the type signatures.
take , drop , and sum . 
1.
takeInt :: Int > [a] > [a]
takeInt 0 _ = []
takeInt _ [] = []
takeInt n (x:xs) = x : takeInt (n1) xs
2.
dropInt :: Int > [a] > [a]
dropInt 0 list = list
dropInt _ [] = []
dropInt n (x:xs) = dropInt (n1) 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) = (yx) : 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) = (yx): diffsAlt' xs ys
The map
function[edit]
Exercises 


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 higherorder 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 (n1) 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)
where
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
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 nondigit.
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 tricks[edit]
Exercises 


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