6.0  Prologue

A combinator is a higher-order function with no free variables - its behavior is determined entirely by the functions it receives as arguments. Combinators are the standard vocabulary for processing collections: instead of writing a loop that accumulates results, you compose map, filter, and fold to express the same transformation declaratively.

6.1  map, filter, fold

These three combinators cover the vast majority of collection-processing patterns. -- Haskell map (*2) [1,2,3] -- [2,4,6] transform each element filter even [1,2,3,4,5] -- [2,4] keep matching elements foldr (+) 0 [1,2,3] -- 6 combine to a single value foldl' (+) 0 [1,2,3] -- 6 strict left fold (prefer for sums) -- F# List.map ((*) 2) [1;2;3] // [2;4;6] List.filter (fun x -> x % 2 = 0) [1;2;3;4;5] // [2;4] List.fold (+) 0 [1;2;3] // 6 -- Rust (lazy iterators; collect drives evaluation) (1..=5).map(|x| x * 2).collect::<Vec<_>>() (1..=5).filter(|x| x % 2 == 0).collect::<Vec<_>>() (1..=5).fold(0, |acc, x| acc + x) // 15 -- Python list(map(lambda x: x*2, [1,2,3])) list(filter(lambda x: x%2==0, [1,2,3,4,5])) from functools import reduce; reduce(lambda a,x: a+x, [1,2,3], 0) fold (also called reduce) is the most general of the three: both map and filter can be expressed as folds.

6.2  scan, zip, unfold

scan is like fold but keeps every intermediate accumulator value, producing a list of running totals. zip pairs elements from two lists by position. unfold generates a list from a seed value. -- Haskell scanl (+) 0 [1,2,3,4] -- [0,1,3,6,10] running sum (includes seed) zip [1,2,3] ['a','b','c'] -- [(1,'a'),(2,'b'),(3,'c')] zipWith (+) [1,2,3] [4,5,6] -- [5,7,9] zip then apply -- unfoldr generates a list from a seed (dual of foldr) import Data.List (unfoldr) unfoldr (\n -> if n == 0 then Nothing else Just (n, n-1)) 5 -- [5,4,3,2,1] -- Rust (0..=4).scan(0, |acc, x| { *acc += x; Some(*acc) }).collect::<Vec<_>>() // [0,1,3,6,10] (1..=3).zip('a'..='c').collect::<Vec<_>>() // [(1,'a'),(2,'b'),(3,'c')] -- Python import itertools list(itertools.accumulate([1,2,3,4])) # [1,3,6,10] list(zip([1,2,3], ['a','b','c']))

6.3  Applicative and Monoidal Operations

Applicative operations apply a function wrapped in a context to a value wrapped in the same context. Monoidal operations combine values of the same type associatively with an identity element. -- Haskell: Applicative (<*> applies a wrapped function to a wrapped value) Just (+3) <*> Just 5 -- Just 8 Nothing <*> Just 5 -- Nothing -- Apply a list of functions to a list of values (Cartesian product) [(+1),(+10)] <*> [1,2,3] -- [2,3,4, 11,12,13] -- Haskell: Monoid (mempty is identity, mappend/<> combines) "hello" <> " " <> "world" -- "hello world" [1,2] <> [3,4] -- [1,2,3,4] Sum 3 <> Sum 4 -- Sum 7 -- Rust: Iterator::chain (monoid on iterators) (1..=3).chain(4..=6).collect::<Vec<_>>() // [1,2,3,4,5,6] -- liftA2: apply a binary function under a context liftA2 (+) (Just 3) (Just 4) -- Just 7 liftA2 (+) Nothing (Just 4) -- Nothing

6.4  Point-Free Composition

Point-free style defines functions without naming their arguments (the “points”). Instead, the function is expressed entirely as a composition of other functions. This style emphasizes the pipeline rather than the data flowing through it. -- Haskell: point-free vs pointed style -- Pointed (names the argument x): sumOfSquaresOfEvens xs = sum (map (^2) (filter even xs)) -- Point-free (no argument named): sumOfSquaresOfEvens = sum . map (^2) . filter even -- Both are identical; the point-free form reads as a pipeline -- F#: point-free with (>>) composition operator let sumOfSquaresOfEvens = List.filter (fun x -> x % 2 = 0) >> List.map (fun x -> x * x) >> List.sum -- Rust: iterator combinators are inherently point-free-ish let sum_sq_even = |v: &[i32]| v.iter() .filter(|&&x| x % 2 == 0) .map(|&x| x * x) .sum::<i32>(); Point-free style is idiomatic in Haskell and common in F#. It becomes unreadable when overused; the balance point is where naming the argument would add nothing beyond what the composition already expresses.

6.5  Epilogue

Combinators provide a vocabulary for expressing data transformations without loops or mutable accumulators. map, filter, and fold handle 90% of collection-processing needs. The applicative and monoidal abstractions generalize these patterns from lists to any context (Option, Result, parsers, futures). The next chapter examines lazy evaluation, which makes infinite structures and demand-driven computation possible.

6.6  References

Haskell Data.List - Hackage
F# Lists - Microsoft
Rust Iterator Trait - std
Python itertools