Composition

Partial application is the most essential feature for a peoper function composition. Languages without parial application are cripled.

factorial = product . enumFromTo 1

Whenever a new datatype is defined, higher-order functions should be written for processing it.

It also hides “knowledge” about the details of its representation (just like an ADT) inside a module.

Instances of appropriate “standard” type-classes has to be writtern (Monoid, etc).

Eventually, public functions form layers of DSLs, just like trees of lists.

copy = foldr Cons Nil

append xs ys = foldr Cons ys xs

(g . f) x = g (f x)

map = foldr (Cons . f) Nil

Nested types are cool, so is abstraction by parameterization.

treeof ∗ ::= Node ∗ (listof (treeof ∗))

foldtree f g a (Node v xss) = f v (foldtree f g a xss)
foldtree f g a (Cons x xs) = g (foldtree f g a x) (foldtree f g a xs)
foldtree f g a Nil = a

inorder = foldtree Cons append Nil

maptree f = foldtree (Node . f ) Cons Nil

Once we could define a foldr we could define a map, and then some for-comprehensions.

length = foldr count 0
where
   count _ n = n + 1

let length = foldr (\_ n -> n+1) 0

let map f = foldr ((:) . f) []