List Processing

# Chapter Summary

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 `List` structure. It has nothing new to offer a seasoned functional programmer, but its brevity and conciseness make it a quick and pleasant read.

# Exercises

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 `fold(l)`.

# Solutions (spoilers)

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