From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.1.3 (2006-06-01) on yquem.inria.fr X-Spam-Level: X-Spam-Status: No, score=0.0 required=5.0 tests=AWL,HTML_MESSAGE autolearn=disabled version=3.1.3 X-Original-To: caml-list@yquem.inria.fr Delivered-To: caml-list@yquem.inria.fr Received: from mail1-relais-roc.national.inria.fr (mail1-relais-roc.national.inria.fr [192.134.164.82]) by yquem.inria.fr (Postfix) with ESMTP id B99E4BC69 for ; Fri, 19 Oct 2007 15:00:40 +0200 (CEST) X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: Ah4FAG9HGEdCm3xr/2dsb2JhbACCPDaNSg X-IronPort-AV: E=Sophos;i="4.21,300,1188770400"; d="scan'208,217";a="3346966" Received: from janestcapital.com (HELO smtp.janestcapital.com) ([66.155.124.107]) by mail1-smtp-roc.national.inria.fr with ESMTP; 19 Oct 2007 15:00:40 +0200 Received: from [172.25.129.161] [38.96.172.125] by janestcapital.com with ESMTP (SMTPD-9.10) id AA760688; Fri, 19 Oct 2007 09:00:38 -0400 Message-ID: <4718AA76.3010103@janestcapital.com> Date: Fri, 19 Oct 2007 09:00:38 -0400 From: Brian Hurt User-Agent: Mozilla/5.0 (Windows; U; Windows NT 5.1; en-US; rv:1.7.2) Gecko/20040804 Netscape/7.2 (ax) X-Accept-Language: en-us, en MIME-Version: 1.0 To: Jon Harrop Cc: caml-list@yquem.inria.fr Subject: Re: [Caml-list] Help me find this pdf References: <200710181457.58077.jon@ffconsultancy.com> <47176C28.1090509@janestcapital.com> <200710181818.31430.jon@ffconsultancy.com> In-Reply-To: <200710181818.31430.jon@ffconsultancy.com> Content-Type: multipart/alternative; boundary="------------040602050406090007040606" X-Spam: no; 0.00; node:01 node:01 val:01 appending:01 haskell:01 compiler:01 val:01 appending:01 haskell:01 compiler:01 wrote:01 wrote:01 rec:01 rec:01 syntactic:01 This is a multi-part message in MIME format. --------------040602050406090007040606 Content-Type: text/plain; charset=ISO-8859-15; format=flowed Content-Transfer-Encoding: 7bit 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 = ># 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 --------------040602050406090007040606 Content-Type: text/html; charset=ISO-8859-15 Content-Transfer-Encoding: 8bit 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

--------------040602050406090007040606--