Recursion and Higher-Order Functions

Loops without loops

Without mutable variables, repetition is expressed with recursion: a base case and a recursive case that works on a smaller input. Most recursion follows common shapes captured by higher-order functions: map transforms each element, filter keeps matching ones, and folds combine a structure into one value. foldr f z replaces each : with f and [] with z; it works on infinite lists when f is lazy in its second argument and is the natural choice for building lists. foldl' (from Data.List) is a strict left fold, the right choice for sums and counters on large lists, because the lazy foldl builds up a chain of unevaluated thunks and can exhaust memory. Functions compose with . ((f . g) x = f (g x)) and $ applies a function with the lowest precedence, avoiding parentheses: print $ sum $ map square xs. Writing functions without naming their arguments, such as countPaid = length . filter paid, is called point-free style; use it when it reads clearly, not to be clever.

Recursion, folds and composition

The same sums written three ways, plus composition.

import Data.List (foldl')
import Data.Char (toUpper, isAlpha)

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

-- strict left fold: constant stack, good for long lists
sumStrict :: [Int] -> Int
sumStrict = foldl' (+) 0

-- our own map, written with foldr
myMap :: (a -> b) -> [a] -> [b]
myMap f = foldr (\x acc -> f x : acc) []

data Order = Order { orderId :: String, totalPaise :: Int, paid :: Bool }

paidRevenue :: [Order] -> Int
paidRevenue = sum . map totalPaise . filter paid       -- point-free pipeline

shout :: String -> String
shout = map toUpper . filter isAlpha

main :: IO ()
main = do
  print (sumList [1 .. 100])                 -- 5050
  print (sumStrict [1 .. 10000000])          -- 50000005000000
  print (myMap (* 2) [1, 2, 3 :: Int])       -- [2,4,6]
  print $ paidRevenue [Order "o1" 120000 True, Order "o2" 30000 False]   -- 120000
  putStrLn (shout "hello, world!")           -- HELLOWORLD

Use foldl' for accumulation

The lazy foldl is almost never what you want: summing ten million numbers with it can build millions of thunks. Import foldl' from Data.List for strict accumulation, or use sum, which is strict in modern GHC versions.

Quick check: Why is foldl' usually preferred over foldl for summing a large list?

• It evaluates the accumulator at each step, avoiding a build-up of unevaluated thunks
• It is lazier
• It works only on infinite lists
• It sorts the list first