Working Review of "Practical ML Programming with SML#" (Ohori, Ueno), CHAPTER 3

List Processing
2023-07-29

Chapter Summary

Chapter 3 deals with the bread-and-butter of classical functional programming: list processing.

The main thrust 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