Re: [Caml-list] Help me find this pdf

[Jon Harrop <jon@ffconsultancy.com>]

On Thursday 18 October 2007 15:22:32 Brian Hurt wrote:
> You have to explicitly force the lazy value first-

If you force all lazy values before the pattern match then you are doing eager 
evaluation, not lazy. Moreover, you must also generate an auxiliary data 
structure to store the forced values in order to pattern match over them.

> but other than it being explicit,

And not lazy.

> this is no different from other languages that implicitly force the value
> for you. 

On the contrary, it fails to achieve laziness.

> Well, Haskell has an option where a pattern match can always succeed that
> doesn't necessarily force the lazy value

Exactly. Not "necessarily forcing" the lazy value is the essence of lazy 
evaluation and the only point to my suggestion.

> (I forget what it's called at the moment), but baring that... 

You can't ignore that: its the whole point! :-)

Consider a function that concatenates adjacent "Some _" values in a list:

# let rec f = function
    | [] -> []
    | Some x :: Some y :: t -> f(Some(x @ y) :: t)
    | h :: t -> h :: f t;;
val f : 'a list option list -> 'a list option list = <fun>
# f [Some [1]; Some [2;3]; None; Some [4;5]];;
- : int list option list = [Some [1; 2; 3]; None; Some [4; 5]]

Thanks to pattern matching, this solution is almost as beautiful as my wife.

An equivalent with lazy lists might be:

# type 'a llist = Nil | Cons of 'a * 'a llist lazy_t;;

# let rec f = function
    | Nil -> Nil
    | Cons(None, t) -> Cons(None, lazy(f(Lazy.force t)))
    | Cons(Some x as h, t) ->
        match Lazy.force t with
        | Nil -> Cons(h, lazy Nil)
        | Cons(None, t) -> Cons(h, lazy(Cons(None, lazy(f(Lazy.force t)))))
        | Cons(Some y, t) -> Cons(Some(x @ y), lazy(f(Lazy.force t)));;
val f : 'a list option llist -> 'a list option llist = <fun>

# let rec forces = function
    | Nil -> []
    | Cons(h, t) -> h :: forces(Lazy.force t);;
val forces : 'a llist -> 'a list = <fun>

# forces(f(Cons(Some [1], lazy(Cons(Some [2;3], lazy(Cons(None, lazy(Cons(Some 
[4;5], lazy Nil)))))))));;
- : int list option list = [Some [1; 2; 3]; None; Some [4; 5]]

Because you can't pattern match over lazy values, this solution is about as 
beautiful as my first girlfriend.

This is no freakishly theoretical problem either, it crops up whenever I want 
to destructure a collection as a sequence. You can use an unfold but that 
only buys you 1 element look ahead whereas the power of pattern matching 
stems from its ability to dispatch based upon destructuring to arbitrary 
depths.

If it were possible to pattern match over lazy values, you would simply write 
a to_lazylist function in the module of each container and pattern match over 
its result to dissect any container with minimal copying.

In this case, you would write:

# let rec f = function
    | Nil -> []
    | Cons(Some x, lazy(Cons(Some y, lazy t))) -> f(Some(x @ y) :: t)
    | Cons(h, lazy t) -> h :: f t;;
val f : 'a list option llist -> 'a list option llist = <fun>

You could even define the primitives in terms of pattern matching:

  let force (lazy x) = x

-- 
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/products/?e