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

[Brian Hurt <bhurt@janestcapital.com>]

[-- Attachment #1: Type: text/plain, Size: 2780 bytes --]

Jon Harrop wrote:

>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.
>
>  
>
You don't need to force all of them, you just need to force *one* (at 
least).

As an example, you might define a lazy list like:
type 'a node_t =
    | Empty
    | Cons of 'a * 'a lazylist
and 'a lazylist = 'a node_t Lazy.t;;

To see if the list is not empty, you have to first the first (but only 
the first!) element:

let is_empty zlst =
    match Lazy.force zlst with
    | Empty -> true
    | Cons _ -> false
;;

Etc.  Notice how the tail of the lazy list isn't forced in this 
example.  It works just fine on an infinite list.

Now, in a pattern with multiple lazy values, you need to be carefull not 
to over-force the result.

>>(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;;
>
>  
>
Bad definition of a lazy list- the first element always has to be 
forced.  Using my definition from above:

let rec f zlst = lazy (
    match Lazy.force zlst with
    | Empty -> Empty
    | Cons (None, xs) -> Cons (None, f xs)
    | Cons (Some x, xs) as t ->
       match Lazy.force xs with
          | Empty -> t
          | Cons(None, ys) -> Cons(Some x, lazy (Cons(None, f ys)))
          | Cons(Some y, ys) -> Cons (Some (x @ y), f ys)
);;

Not quite as pretty, I'll admit.  But it works.  And (modulo laziness 
around the options and appending) is the same as what Haskell would do.  
And note that the first two elements of the arguments are not forced 
until the first element of the result is forced- and I don't see how to 
avoid this.

The only thing missing is some syntactic sugar to make the above pattern 
matching nicer- computationally, the same values will need to be 
forced.  If you're arguing in favor of the syntactic sugar, I'm 
sympathetic.  If you're arguing that the compiler could somehow avoid 
forcing the same values, I don't see how.

Brian


[-- Attachment #2: Type: text/html, Size: 3547 bytes --]