Recursion

Haskell has no for or while loops. Repetition is done by recursion — a function calling itself — or, more often, by library functions like map and foldr that are themselves recursive.

The recipe

1. Handle the base case — the simplest input, such as 0 or [].
2. Handle the recursive case — do a little work, and call the function on a smaller input.

factorial :: Integer -> Integer
factorial 0 = 1
factorial n = n * factorial (n - 1)

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

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

main :: IO ()
main = do
  print (factorial 20)
  print (factorial 25)
  print (sumList [1 .. 100])
  print (myLength "recursion")

2432902008176640000
15511210043330985984000000
5050
9

Think of sumList [1, 2, 3] as 1 + sumList [2, 3] = 1 + (2 + sumList [3]) = 1 + (2 + (3 + 0)) = 6.

Building lists recursively

doubleAll :: [Int] -> [Int]
doubleAll [] = []
doubleAll (x : xs) = x * 2 : doubleAll xs

myTake :: Int -> [a] -> [a]
myTake n _ | n <= 0 = []
myTake _ [] = []
myTake n (x : xs) = x : myTake (n - 1) xs

countdown :: Int -> [Int]
countdown 0 = [0]
countdown n = n : countdown (n - 1)

main :: IO ()
main = do
  print (doubleAll [1, 2, 3])
  print (myTake 3 "Haskell")
  print (countdown 5)

[2,4,6]
"Has"
[5,4,3,2,1,0]

Accumulators

Some problems are easier with a helper that carries the result so far:

reverseList :: [a] -> [a]
reverseList xs = go xs []
  where
    go [] acc = acc
    go (y : ys) acc = go ys (y : acc)

fib :: Int -> Integer
fib n = go n 0 1
  where
    go 0 a _ = a
    go k a b = go (k - 1) b (a + b)

main :: IO ()
main = do
  print (reverseList [1, 2, 3, 4])
  print (map fib [0 .. 10])
  print (fib 90)

[4,3,2,1]
[0,1,1,2,3,5,8,13,21,34,55]
2880067194370816120

Naming the helper go is a Haskell convention. The accumulator version of fib is fast; the "obvious" fib n = fib (n - 1) + fib (n - 2) recomputes the same values exponentially many times.

Common mistakes

• Forgetting the base case, or a recursive call that doesn't get smaller — the program loops forever or runs out of memory.
• Writing recursion when a library function exists. Once you know the pattern, reach for map, filter, sum, or a fold (Level 2) instead.

Practice

Write a recursive countOccurrences :: Char -> String -> Int.

countOccurrences :: Char -> String -> Int
countOccurrences _ [] = 0
countOccurrences c (x : xs)
  | c == x = 1 + countOccurrences c xs
  | otherwise = countOccurrences c xs

main :: IO ()
main = print (countOccurrences 's' "mississippi")

4