IDisposable Thoughts

Now it is the turn for three favourites in the Caml standard List module, map, fold_right, fold_left.

Let’s start with the non-tail recursive version of map (the List module version is not tail recursive neither), the idea is to return a list 'b which is the result of applying the function 'a -> 'b to all the members of a list 'a, or well in our case ('a -> 'b) -> 'a seq -> 'b seq

let seq_map ~f l =
  | Next (x, t) -> Next ((f x), ((seq_map [@tailcall]) f t))
  | _ -> End
;;

seq_map ~f:(fun x -> x * 2) sample

val seq_map : f:('a -> 'b) -> 'a seq -> 'b seq = <fun>
- : int seq = Next(2, Next(4, Next(6, End)))

As expected we will get the tailcall error:

Again, the original map function in the Caml standard list module is not tail recursive (the version in Core is), notice as well the use of the named arguments, when working with the mix of list and functions is a good idea to use them.

Let’s work in our tail recursive version, it will become easy if we use the now familiar reverse inner loop accumulator style

let seq_map f l =
  let rec map' acc = function
    | End -> acc
    | Next (x, t) -> map' (Next((f x), acc)) t
  in
  rev_seq (map' End l)
;;

The power of fold

The fold operations are called reducers and aggregators by others, the idea is calculating a running value through a sequence. We agregate values from a sequence with a function who takes the current value and previous value of the applied function. In some parlance it is called reducers.

There are two versions of fold, the common left version folding from left to right (moving the apply function from the left to the right)

Let’s start with probably the most powerful function in the List module, fold_left

let rec seq_fold_left ~f ~init = function
  | End -> init
  | Next (x, tl) -> (seq_fold_left [@tailcall]) ~f ~init:(f x init) tl
;;

seq_fold_left ~f:(fun a b -> a + b) ~init:0 sample

val seq_fold_left : ~f:('a -> 'b -> 'b) -> ~init:'b -> 'a seq -> 'b = <fun>
- : int = 6

Here I put the @tailcall here so I can demostrate the function is already tail recursive, the compiler throws no warning! Nice!

The fold_right expression (fold from the right to the left) can be easily expressed now simply reversing the sequence and applying fold_left:

let seq_fold_right ~f ~init l = 
  seq_fold_left ~f ~init (seq_rev l)
;;

val fold_right_seq : f:('a -> 'b -> 'b) -> 'a seq -> init:'b -> 'b = <fun>

We can even express functions like rev as a fold function:

let rev_seq' = 
  fold_left_seq ~f:(fun l' x -> cons_seq x l') ~init:End 
;;

rev_seq' sample

val rev_seq' : '_weak8 seq -> '_weak8 seq = <fun>
- : int seq = Next (3, Next (2, Next (1, End)))

Notice how we curry the function, this is a very common style in FP

Another function easy to implement now with fold is the familiar map

let map_seq' ~f =
  fold_right_seq ~f:(fun elem l -> cons_seq (f elem) l) ~init:End
;;
map_seq' ~f:(fun x -> x * 2) sample

val map_seq' : f:('a -> 'b) -> 'a seq -> 'b seq = <fun>
- : int seq = Next (2, Next (4, Next (6, End)))

See? I told you fold is a very powerful function ;)

Next time (I hope) we will talk more about tail recursion and why some functions in the Caml standard library are not tail recursive (and core offers both versions). As usual the Jupyter notebook with more of my notes (and the origin of this series) is in my GitHub repo.