Working Review of "Practical ML Programming with SML#" (Ohori, Ueno), CHAPTER 3
Chapter 3 deals with the bread-and-butter of classical functional programming: list processing.
The main thust of this chapter is getting the reader acquainted with the
fundamental list processing functions, which are to be found in the
structure. It has nothing new to offer a seasoned functional programmer, but
its brevity and conciseness make it a quick and pleasant read.
The exercises revolve around reimplementing fundamental list processing functions.
Seeing as it’s July, the 24th anniversary of Graham Hutton’s A tutorial on the
universality and expressiveness of fold appearing in the Journal of Functional
Programming, I decided to do a little challenge for myself and implement all
the required functions in terms of
fun uncurry (f: 'a -> 'b -> 'c) : (('a * 'b) -> 'c) = fn (x,y) => f x y; structure L = struct fun foldl f acc nil = acc | foldl f acc (x::xs) = foldl f (f (x, acc)) xs; fun rev (xs: 'a list) : 'a list = foldl (op ::) nil xs fun append (l1 : 'a list) (l2 : 'a list) : 'a list = foldl (op ::) l2 (rev l1) fun concat (ls : 'a list list) : 'a list = foldl (uncurry append) nil (rev ls) fun filter (pred : 'a -> bool) (ls : 'a list) : 'a list = foldl (fn (el,acc) => if pred el then (el::acc) else acc)  (rev ls) fun map (f : ('a -> 'b)) (ls : 'a list) : 'b list = foldl (fn (el,acc) => (f el)::acc) nil (rev ls) fun zip (aa : 'a list) (bb : 'b list) : ('a * 'b) list = (rev o #2) (foldl (fn (x, (ys, r)) => if null ys then (ys, r) else (tl ys, (x,hd ys)::r)) (bb, nil) aa) fun unzip (abs : ('a * 'b) list) : ('a list * 'b list) = foldl (fn ((a,b),(aa,bb)) => (a::aa, b::bb)) (,) (rev abs); end