Haskell/Solutions/Lists II

← Back to Lists II

Note that, for our current purposes, it is indifferent whether to use Int or Integer, so don't worry if you have used one and the solutions below the other.

Rebuilding lists

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.

-- "Direct" solution with pattern matching.
scanSum ::  [Int] -> [Int]
scanSum [] = []
scanSum [x] = [x]
scanSum (x:y:xs) = x : scanSum ((x + y) : xs)

-- Alternatively, using a helper function with an accumulator argument:
scanSum :: [Int] -> [Int]
scanSum = scanSum' 0
    where
    -- The following type signature is entirely optional.
    -- We have added it just for extra clarity.
    scanSum' :: Int -> [Int] -> [Int]
    scanSum' tot [] = []
    scanSum' tot (x:xs) = tot' : scanSum' tot' xs
        where
        tot' = x + tot

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

5.

diffs :: [Int] -> [Int]
diffs [] = []
diffs (x:xs) = diffs' (x:xs) xs
    where
    diffs' :: [Int] -> [Int] -> [Int]
    diffs' _ [] = []
    diffs' [] _ = []
    diffs' (x:xs) (y:ys) = (y-x) : diffs' xs ys

-- Alternatively, without the auxiliary function:
diffs          :: [Int] -> [Int]
diffs []       = []
diffs [x]      = []
diffs (x:y:xs) = (y-x) : diffs (y:xs)

The map function

1. A handful of variations for each function will be shown below, in a single block:

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

divisorsList, divisorsList2 :: [Int] -> [[Int]]
divisorsList = map divisors
divisorsList2 xs = map divisors xs

-- Note that there are even more possible ways of writing this one.
-- Remember that the dot operator composes functions: (g . f) x = g (f x) 
negateDivisorsList, negateDivisorsList2, negateDivisorsList3, negateDivisorsList4 :: [Int] -> [[Int]]
negateDivisorsList = map (negateList . divisors)
negateDivisorsList2 = map negateList . divisorsList
negateDivisorsList3 list = map (negateList . divisors) list
negateDivisorsList4 list = map (map negate) (map divisors list)

2. One possible solution:

import Data.List

myRLEencoder :: String -> [(Int, Char)]
myRLEencoder s = map pairRLE (group s)
    where
    pairRLE xs = (length xs, head xs) 

myRLEdecoder :: [(Int, Char)] -> String
myRLEdecoder l = concat (map expandRLE l)
    where
    expandRLE (n, x) = replicate n x

N.B.: the RLE example is inspired from a blog post by Don Stewart on the same subject. If you are curious, check Don's post for a neat solution which likely won't not be immediately understandable, as it uses some things we didn't see yet.

Tips and tricks

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)