1.1 Building vocabulary — the standard list toolkit

Fluent Haskell programmers compose programs from a small, powerful vocabulary of list functions. Learn these with their types — exam questions often ask for the type and a usage example.

The lowercase a is a type variable: length :: [a] -> Int works on a list of anything. This is parametric polymorphism.

1.2 The big three higher-order functions

map — transform every element:

map :: (a -> b) -> [a] -> [b]
ghci> map (* 2) [1,2,3]
[2,4,6]
ghci> map toUpper "hello"
"HELLO"

filter — keep elements that satisfy a predicate:

filter :: (a -> Bool) -> [a] -> [a]
ghci> filter even [1..10]
[2,4,6,8,10]

foldr — collapse a list with an operator, nesting it between the elements:

foldr f z [a,b,c]  =  f a (f b (f c z))    -- infix: a `f` (b `f` (c `f` z))

foldr :: (a -> b -> b) -> b -> [a] -> b
sum     = foldr (+) 0
product = foldr (*) 1
concat  = foldr (++) []

Almost every list function is a fold in disguise — recognising this is "building vocabulary" at its best.

1.3 Anonymous functions and sections

ghci> map (\x -> x * x + 1) [1,2,3]    -- lambda, straight from Unit 1
[2,5,10]
ghci> map (+ 10) [1,2,3]                -- operator section: (+ 10) = \x -> x + 10
[11,12,13]
ghci> filter (> 5) [3,8,1,9]
[8,9]

1.4 List comprehensions

Borrowed from set-builder notation — { x² | x ∈ [1..10], x even }:

ghci> [ x*x | x <- [1..10], even x ]
[4,16,36,64,100]

-- multiple generators: all pairs
ghci> [ (x,y) | x <- [1,2,3], y <- "ab" ]
[(1,'a'),(1,'b'),(2,'a'),(2,'b'),(3,'a'),(3,'b')]

-- pythagorean triples up to 20
ghci> [ (a,b,c) | c <- [1..20], b <- [1..c], a <- [1..b],
                  a*a + b*b == c*c ]
[(3,4,5),(6,8,10),(5,12,13),(9,12,15),(8,15,17),(12,16,20)]

A comprehension is pure sugar: [ f x | x <- xs, p x ] = map f (filter p xs).

1.5 Laziness pays off: infinite lists

ghci> take 5 [1..]                 -- the infinite list of naturals
[1,2,3,4,5]
ghci> take 6 (cycle [0,1])
[0,1,0,1,0,1]
ghci> takeWhile (< 100) [ 2^n | n <- [0..] ]
[1,2,4,8,16,32,64]

Because evaluation is lazy (Unit 1, graph reduction), only the demanded prefix is ever built.

1.6 Worked example — frequency-style processing pipeline

"Given a sentence, return the lengths of the words longer than three letters, sorted descending."

import Data.List (sortBy)
import Data.Ord (comparing, Down(..))

answer :: String -> [Int]
answer = sortBy (comparing Down) . map length . filter ((> 3) . length) . words

ghci> answer "functional programming is honestly fun"
[11,10,8,3]  -- wait: 'fun' was filtered, 'is' was filtered → [11,10,8]
ghci> answer "functional programming is honestly fun"
[11,10,8]

Note the function composition operator . — (f . g) x = f (g x) — letting us build the program as a left-to-right pipeline read right-to-left. Designing with small composable functions is the core skill of Unit 2.

1.7 foldr vs foldl — the comparison every exam expects

foldl is the left-bracketing twin of foldr:

foldr f z [a,b,c]  =  f a (f b (f c z))      -- brackets nest to the RIGHT
foldl f z [a,b,c]  =  f (f (f z a) b) c      -- brackets nest to the LEFT

Expansion traces — write these in full in the exam:

foldr (+) 0 [1,2,3]                     foldl (+) 0 [1,2,3]
= 1 + foldr (+) 0 [2,3]                 = foldl (+) (0+1) [2,3]
= 1 + (2 + foldr (+) 0 [3])             = foldl (+) ((0+1)+2) [3]
= 1 + (2 + (3 + foldr (+) 0 []))        = foldl (+) (((0+1)+2)+3) []
= 1 + (2 + (3 + 0))                     = ((0+1)+2)+3
= 6                                     = 6

Their hand-written definitions (also asked directly):

foldr :: (a -> b -> b) -> b -> [a] -> b
foldr _ z []     = z
foldr f z (x:xs) = f x (foldr f z xs)

foldl :: (b -> a -> b) -> b -> [a] -> b
foldl _ z []     = z
foldl f z (x:xs) = foldl f (f z x) xs        -- note: tail recursive

1.8 zipWith and friends

zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]
ghci> zipWith (+) [1,2,3] [10,20,30]
[11,22,33]
ghci> zipWith (*) [1,2,3] [1,2,3]          -- squares, pairwise
[1,4,9]

-- the famous one-liner: the entire Fibonacci sequence
fibs :: [Integer]
fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
ghci> take 8 fibs
[0,1,1,2,3,5,8,13]

fibs works because laziness lets a list be defined in terms of itself — each element is demanded only after the two before it exist. This example combines Unit 1 (laziness) and Unit 2 (higher-order functions) and is a favourite "explain why this terminates" question.

1.9 More pipeline practice (exam-style one-liners)

-- count vowels in a string
countVowels :: String -> Int
countVowels = length . filter (`elem` "aeiouAEIOU")

-- sum of squares of the even numbers up to n
sumSqEven :: Int -> Int
sumSqEven n = sum [ x*x | x <- [2,4..n] ]

-- are all elements positive?  (and/or collapse lists of Bool)
allPos :: [Int] -> Bool
allPos = and . map (> 0)

-- first prime factor table: list primes below n (trial division)
primes :: Int -> [Int]
primes n = [ p | p <- [2..n], all (\d -> p `mod` d /= 0) [2..p-1] ]
ghci> primes 20
[2,3,5,7,11,13,17,19]

For each, practise stating the types of every stage of the pipeline — examiners award marks for the intermediate types, not just the answer.

Exam pointers

• "Define map/filter/foldr with type and example" — give the type, the two-equation definition, and one evaluation. All three fit in six lines each.
• "Differentiate foldr and foldl" — table of §1.7 plus the (-) counter-example; mention infinite lists for the top grade.
• List-comprehension-to-map/filter translation (and back) is a routine 2-mark conversion: [ f x | x <- xs, p x ] = map f (filter p xs).

Self-check

1. What is the type of map map? (Work it out by unification — a classic brain-teaser.)
2. Expand foldr (:) [] [1,2,3] — what well-known function is foldr (:) []?
3. Why does foldl never terminate on [1..] even with a lazy f?
4. Write length as a fold.
5. Using a comprehension, list all pairs (x,y) with x ∈ [1..3], y ∈ [1..3], x < y.