Day 2: Lists, Higher-Order Functions & Laziness | Haskell in 5 Days

List Operations

Lists are linked lists: [] is empty, (x:xs) is head:tail. Prelude functions: head, tail, init, last, length, reverse, take, drop, zip, unzip, concat, concatMap, elem, null, filter, map. List comprehensions: [x*2 | x <- [1..10], x `mod` 2 == 0] generates doubled even numbers. Ranges: [1..10], [1,3..10] (step), ['a'..'z'].

Higher-Order Functions

map f xs applies f to every element. filter p xs keeps elements satisfying predicate p. foldr f z xs reduces right-to-left: foldr (+) 0 [1,2,3] = 1+(2+(3+0)) = 6. foldl is left-to-fold; foldl' (strict) avoids stack overflow on large lists. Function composition: (f . g) x = f (g x). Partial application: map (*2) [1..5] — (*2) is a partially applied section.

Lazy Evaluation and Infinite Lists

Haskell only evaluates expressions when their values are needed. This enables infinite lists: [1..] is an infinite list of naturals. 'take 10 [1..]' evaluates only the first 10 elements. Infinite lists: repeat x (infinite xs), cycle xs (repeating cycle), iterate f x ([x, f x, f(f x), ...]). Fibonacci: 'fibs = 0 : 1 : zipWith (+) fibs (tail fibs)' — an infinite list defined recursively.

haskell

-- Higher-order functions
doubles :: [Int] -> [Int]
doubles = map (*2)

evens :: [Int] -> [Int]
evens = filter even

sumSquares :: [Int] -> Int
sumSquares = foldl' (+) 0 . map (^2)
  where foldl' = foldl seq `seq` foldl
-- Better: import Data.List (foldl')

-- List comprehension: Pythagorean triples
pyTriples :: Int -> [(Int,Int,Int)]
pyTriples n = [(a,b,c) | c <- [1..n],
                          b <- [1..c],
                          a <- [1..b],
                          a^2 + b^2 == c^2]

-- Infinite Fibonacci list
fibs :: [Integer]
fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

-- First 15 Fibonacci numbers
first15 :: [Integer]
first15 = take 15 fibs  -- [0,1,1,2,3,5,8,13,21,34,55,89,144,233,377]

💡

Use foldl' (strict) from Data.List instead of foldl when summing large lists. Lazy foldl builds up unevaluated thunks and causes a stack overflow. foldl' forces evaluation at each step.

📝 Day 2 Exercise

Solve Problems with HOFs

In GHCi, compute the sum of squares of all odd numbers from 1 to 100 using map, filter, sum
Generate all Pythagorean triples where the hypotenuse is less than 100
Use the infinite fibs list to find the first Fibonacci number greater than 1,000,000
Implement your own version of map using foldr
Write a function that runs length encodes a list: 'aaabbc' -> [(3,'a'),(2,'b'),(1,'c')]

Day 2 Summary

List comprehensions provide a concise syntax for map + filter
map, filter, foldr/foldl' are the core higher-order list functions
Function composition (.) chains transformations without intermediate variables
Lazy evaluation allows infinite lists — take/takeWhile extract finite portions
foldl' prevents stack overflow when reducing large lists

Challenge

Implement quicksort in Haskell in 3 lines using list comprehensions. Then implement merge sort. Compare both against Haskell's built-in sort using criterion benchmarks on a list of 1,000,000 random integers.

← Previous

Day 1: Pure Functions & Types

Day 3: Type Classes & Custom Types

→