Recursion

Structural recursion pattern: handle the base case ([], 0, Leaf), then express the result for the recursive case in terms of smaller inputs. Most explicit recursion can be replaced by map, filter, foldr, and friends.

-- Recursion replaces loops
sumList :: [Int] -> Int
sumList [] = 0
sumList (x : xs) = x + sumList xs

myLength :: [a] -> Int
myLength [] = 0
myLength (_ : xs) = 1 + myLength xs

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

myFilter :: (a -> Bool) -> [a] -> [a]
myFilter _ [] = []
myFilter p (x : xs)
  | p x = x : myFilter p xs
  | otherwise = myFilter p xs

-- Tail recursion with an accumulator (use strictness to avoid thunk build-up: Module 22)
sumAcc :: [Int] -> Int
sumAcc = go 0
  where
    go !acc [] = acc                 -- needs {-# LANGUAGE BangPatterns #-} (included in GHC2021)
    go !acc (x : xs) = go (acc + x) xs

-- Quicksort (elegant, not in-place)
quicksort :: Ord a => [a] -> [a]
quicksort [] = []
quicksort (p : xs) = quicksort smaller ++ [p] ++ quicksort larger
  where
    smaller = [x | x <- xs, x < p]
    larger = [x | x <- xs, x >= p]

-- Mutual recursion
isEven', isOdd' :: Int -> Bool
isEven' 0 = True
isEven' n = isOdd' (n - 1)
isOdd' 0 = False
isOdd' n = isEven' (n - 1)

-- Fibonacci: naive vs efficient
fibNaive :: Int -> Integer
fibNaive n = if n < 2 then toInteger n else fibNaive (n - 1) + fibNaive (n - 2)

fibs :: [Integ
…