Ocaml Lazy Lists- An Introduction

[Edit: I fixed the links on this article. I am never changing the link format again. Ever. Blargh. ~~ The Mgmt.]

Solidifying this blogs iron-fisted hold on being the leading provider of information for Ocaml Lazy Lists (hope you weren’t drinking there), I thought I’d add in some old-fasioned meanderings on the subject. There’s some new information in a later post for those already familiar with the subject, but I think I’ll start with an introduction. Some passing knowledge of Ocaml is assumed, however. Lazy lists are, I beleive, a powerful and usefull concept. Unfortunately, they are virtually unknown outside of the functional programming community, and, I think, under appreciated even within the functional language community. There use and power deserves to be popularized.

Functional languages have come up with the concept of lazy evaluation. The idea here is that you take an expression, and rather than evaluating it, you “capture” it, in what is called a lazy thunk, a memory object (in the broad sense, not in the OO sense). At a later point in time you can “force” or “evaluate” the thunk. The first time a lazy thunk is forced, the original captured expression is evaluated. The expression itself is then discarded, and the value returned from the expression is both returned as the value of forcing the lazy thunk, and cached within the thunk itself (in place of the expression). So the second and subsequent times the thunk is forced, the cached value is simply returned.

In Ocaml, the keyword ‘lazy’ is used before an expression to capture the expression as a lazy thunk. The function Lazy.force can be used to then force the lazy thunk and return the value. An example of this makes things more clear. One advantage Ocaml has is that as a hybrid lanuage, I can have the expression evaluated by the lazy thunk have side effects. For example, it can print something out so we can see when the expression gets evaluated. So say we had a function:

# let f x =
      Printf.printf "Adding %d+3.\n" x;
      x + 3
  ;;
val f : int -> int = <fun>
#

So now we can create a lazy thunk, capturing a call to this function:

# let thunk = lazy (f 4);;
val thunk : int lazy_t = <lazy>
#

The type of a thunk is ‘a lazy_t, where ‘a is the type of the expression captured. We can then force the thunk. Note that the first time, and only the first time, is the function evaluated (and the printf called)- the other times it just returns the cached value:

# Lazy.force thunk;;
Adding 4+3.
- : int = 7
# Lazy.force thunk;;
- : int = 7
# Lazy.force thunk;;
- : int = 7
#

Now, at this point a lot of people are probably going “big deal- we used to do that all the time!” And, to a point, they’re right. But there is a difference between what a programming language makes possible, and what it makes easy. Making lazy evaluation easy- and in other languages, such as Haskell, even mandatory- changes things. An example of what I mean by this is lazy lists.

You can consider a list to be either empty, or a head element followed (recursively) by a list of the remaining elements. If Ocaml didn’t have lists as a built in type, we might reimplement them thusly:

type 'a list_t =
    | Empty
    | Node of 'a * 'a list_t
;;

Lazy evaluation opens up a new possibility- rather than have a list of the rest of elements, why not have it be a lazily evaluated list? We could instead define our list like:

type 'a list_t =
    | Empty
    | Node of 'a * 'a list_t lazy_t

The “next” member of a Node, rather than being just a pointer to the next node, is a lazy evaluation we can force to get the next value. The first time we force the next member, some expression is evaluated and the next member returned. If we force the next member a later time, we just get the returned value. The lazy value acts sort of like a semi-mutable state in this sense. We can set it, but only once. I wrote it the way I did to make the relationship with our original list structure obvious, but in normal practice we want to make even the head node lazily evaluated. So we’re more likely to make our definition like:

type 'a node_t =
    | Empty
    | Node of 'a * 'a zlist_t
and 'a zlist_t = 'a node_t lazy_t
;;

This structure turns out to have a lot of interesting properties. The first is that I was carefully vague about what expression gets evaluated to get the next node of a lazy list. The expression can be arbitrarily complicated. For example, if I had a binary tree (ignoring balancing for the moment):

type 'a tree_t =
    | Leaf of 'a
    | Branch of 'a tree_t * 'a tree_t
;;

I could write a routine to convert a tree to a lazy list like:

let rec get_next_node = function
    | [] -> Empty
    | Leaf(x) :: t -> Node(x, lazy (get_next_node t))
    | Branch(l, r) :: t -> get_next_node (l :: r :: t)
;;

let zlist_of_tree tree = lazy (get_next_node [ tree ] );;

This code is the standard in-order walking of the tree, except I’m hand managing my stack. Each time I force a next element of the resulting lazy list for the first time, I walk the tree a little bit further until I find the next element. Note that the captured expression is freed once it’s evaluated the first time- so if it holds references to data (like a reference to the list I’m using as a stack), the reference is dropped and may give opportunities for the garbage collector to collect some memory. As I create my lazy list of the elements of my tree, there is at any time only one list which is not garbage- the list in the expression of the first never-forced thunk.

A similiar function can be written to construct a tree from a lazy list. Although I’d take a look at this paper by Ralph Hinze as to efficient ways to construct a tree. But that’s a different discussion.

At this point, the comparison to iterators (aka enumerators) popular in object oriented languages is inevitable. “Congratulations,” I can hear you say, “you’ve reinvented Java.Util.Iterator. Have a cookie.” In a sense this is valid- every ecological niche filled by iterators can also be filled by lazy lists just as easily. And were I to stop here, there would be validity to this complaint. How ever, I’m not going to stop there.

Because lazy lists are lists. Which means, as a functional programmer, we want to write list comprehensions for them- map, filter, fold, iter, etc. The map comprehension is especially interesting:

let rec map f zlst = lazy (
    match Lazy.force zlst with
        | Empty -> Empty
        | Node(h, t) -> Node(f h, map f t)
);;

What’s interesting about map is when the mapping is applied. A value in the original list is not converted until that node is forced. This is especially interesting when multiple mapping are applied. Let’s say three mappings have been applied to a list of type ‘a- map function f (of type ‘a -> ‘b), function g (‘b -> ‘c), and function h (‘c -> ‘d), producing a final lazy list of type ‘d. When the map functions are called nothing really happens aside from the allocation of lazy thunks. When the first element of the resultant list is forced, what happens is this: the first element of the original list is forced. The return value of that is passed to a call to f, the return value from f is passed to g, and the return value from g is passed to h. An example (again using printf to show when stuff gets evaluated) makes what I’m saying more clear:

# let zlst = zlist_of_list [1.0;2.0;3.0;4.0;5.0];;
val zlst : float zlist_t =<lazy>
# let f x =
    Printf.printf "Converting %f to int.\n" x;
        int_of_float x
;;
val f : float -> int = <fun>
# let g x =
        Printf.printf "Converting %d to char.\n" x;
    char_of_int (x + (int_of_char '0'))
;;
val g : int -> char = <fun>
# let h x =
        Printf.printf "Converting %c to string.\n" x;
        String.make 1 x
;;
val h : char -> string = <fun>
# let res = map h (map g (map f zlst));;
val res : string zlist_t = <lazy>
# list_of_zlist res;;
Converting 1.000000 to int.
Converting 1 to char.
Converting 1 to string.
Converting 2.000000 to int.
Converting 2 to char.
Converting 2 to string.
Converting 3.000000 to int.
Converting 3 to char.
Converting 3 to string.
Converting 4.000000 to int.
Converting 4 to char.
Converting 4 to string.
Converting 5.000000 to int.
Converting 5 to char.
Converting 5 to string.
- : string list = ["1"; "2"; "3"; "4"; "5"]
#

Notice the order in which things get evaluated. We expressed the algorithm in what you might call a row-major way. Take this lazy list of floats and convert it into a lazy list of ints, then convert that into a lazy list of chars, then convert that into a lazy list of strings. But when the actual computation happens, when we force the list, it’s done in what you might call a column-major way- the first float is calculated, then it’s converted into an int, then a char, then a string, before moving on to the next float.

This is one of the points I was trying to make in my Functional-Relational Impedence Match article. If the elements of the lazy list are being brought in peicemeal from the database or a file, and then being copied back out again to a database or a file, only a small number of elements need to be in memory at any given time- we get the benefits of stream processing without having to explicitly code it.

Now, there’s nothing here that couldn’t be done with iterators, only it generally isn’t done. Even if the capabilities aren’t fundamentall different, thinking about something differently often demonstrates capabilities not previously seen. While possible, applying a lazy map to an iterator isn’t obvious, isn’t intuitive. But applying a map to a list is both obvious and intuitive, and if it’s a lazy list, so is applying a lazy map. Same thing for filter. Wether the Saphir-Worph hypothesis is true for natural languages or not, it is beyond a doubt true for programming languages.

In case you’re wondering how much this idea is worth, it’s worth, approximately, 18.73 bazillion dollars- as this is the core, the heart and soul, of what makes Google possible.

Now, I want to back up a bit and take a different path. Remember that I was carefully vague about what expression gets evaluated to get the next node of a lazy list. The expression can be arbitrarily complicated. And that the expression isn’t evaluated until it is needed. Up until now, I’ve been getting the elements for the lazy from some finite collection of elements- a list, or a tree, or a database table. But I can just as easily have the expression simply calculate the next value. In this case I can have, conceptually, an infinite list- use all you want, we’ll create more.

Again, a concrete example helps. Consider Newton’s method for find a root of a function. If you remember your calculus, this was probably introduced as xi+1 = xi - f(xi)/f'(xi), where f'(x) is the derivitive of f(x), the function we’re trying to find a root for.

Now, mathematically this is an infinite sequence of numbers, but when it’s actually programmed a set of ad-hoc terminating conditions are generally applied. We programmers are impatient, and aren’t willing to wait until the end of time for our programs to complete (indeed, more than a second or two starts getting iffy). So if two numbers xi and xi+1 are “close enough”, we declare the series has converged, and stop. Or if we have to calculate too many steps, we say the sequence doesn’t converge and stop.

The interesting thing here is that we can code this sequnce as an infinite lazy list:

let rec newtons f df x = lazy (
    let x' = x -. ((f x) /. (df x)) in
    Node(x', newtons f df x')
);;

The various stoping criteria we can then code as functions which terminate the lazy list when some criteria is met. For example, we could stop after n steps by writting a function like this:

let rec take n zlist = lazy (
    if (n  Empty
            | Node(h, t) -> Node(h, (take (n-1) t))
);;

A similiar function is easy enough to write to terminate the lazy list whenever two elements in a row are “close enough together”. Note that the two functions can be supplied one atop the other- the first one to terminate the original, infinite lazy list “wins”.

What we have managed to do here is to modularize Newton’s method! We can easily supply multiple different termination algorithms, just by supplying multiple different lazy list termination functions. The user of our library is able to pick and choose which ones, and in what order, they apply.

And to reuse them. Consider if we wanted to implement the fixed point algorithm. Given a function g and an initial guess x0, this algorithm finds an x such that g(x) = x, by the infinite iteration xi+1 = g(xi). Once we generate the infinite lazy list of these values, the exact same termination routines written for Newton’s method work here as well- we’ve opened up the possibility of a new form of code reuse, one that isn’t possible with the old style for-loop implementation of these algorithms.

Again, by chaning our perspective, we change what is apparently possible. An iterator implies some data structure we’re iterating over, but a list is a structure by itself. There’s nothing here that couldn’t, conceptually, be done with iterators, but I’ve never heard of it being done (indeed, I haven’t heard of it being done with lazy lists yet either).

There’s more things I want to discuss with lazy lists, but I figured a basic introduction was necessary before getting into the deeper issues. So, until later…