# Recursion and Higher-Order Functions — Haskell

Source: https://www.geekswithgeeks.com/en/haskell/c-recursion

> Replace loops with recursion, map, filter and folds, and compose 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.

```haskell
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.

**Quiz:** Why is foldl' usually preferred over foldl for summing a large list?

- [x] 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

*Answer:* It evaluates the accumulator at each step, avoiding a build-up of unevaluated thunks. Strict accumulation keeps memory use constant.