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.3 required=5.0 tests=AWL autolearn=disabled version=3.1.3 X-Original-To: caml-list@yquem.inria.fr Delivered-To: caml-list@yquem.inria.fr Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by yquem.inria.fr (Postfix) with ESMTP id 52A2FBC6C for ; Wed, 11 Jul 2007 13:02:40 +0200 (CEST) Received: from server2.thinkcrime.de (server2.thinkcrime.de [213.133.110.149]) by concorde.inria.fr (8.13.6/8.13.6) with ESMTP id l6BB2dBQ031509 for ; Wed, 11 Jul 2007 13:02:40 +0200 Received: from hod-sarge-2005-10.lan.m-e-leypold.de (dslb-088-072-196-085.pools.arcor-ip.net [88.72.196.85]) (using TLSv1 with cipher DHE-RSA-AES256-SHA (256/256 bits)) (No client certificate requested) by server2.thinkcrime.de (Postfix) with ESMTP id 7ED35488016 for ; Wed, 11 Jul 2007 13:02:38 +0200 (CEST) Received: by hod-sarge-2005-10.lan.m-e-leypold.de (Postfix, from userid 1003) id 3A95E3793C; Wed, 11 Jul 2007 13:13:10 +0200 (CEST) To: caml-list@yquem.inria.fr Subject: Re: [Caml-list] Pattern matching over lazy lists References: <200707102338.47010.jon@ffconsultancy.com> Organization: Leypold, Software-Dienstleistungen und -Beratung From: "Markus E.L." Date: Wed, 11 Jul 2007 13:13:10 +0200 In-Reply-To: <200707102338.47010.jon@ffconsultancy.com> (Jon Harrop's message of "Tue, 10 Jul 2007 23:38:46 +0100") Message-ID: User-Agent: Some cool user agent (SCUG) MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii X-Miltered: at concorde with ID 4694B8CF.000 by Joe's j-chkmail (http://j-chkmail . ensmp . fr)! X-Spam: no; 0.00; markus:01 computed:01 parsers:01 parsers:01 tokens:01 markus:01 token:01 caml-list:01 arbitrary:01 tail:01 tail:01 algorithm:01 grammar:02 lazy:02 lazy:02 > What's the best way to do this? > > I was thinking of forcing the first few elements of a lazy list before pattern > matching and then looking for forced values in the lists as patterns but I > don't think you can deconstruct a lazy value in a pattern match... I'll put in my 2 cents here, since I've been working on something like this. Yes, I think you're right: A lazy list when forced, gives a list (so the complete list is produced). On the other side a List of lazy elements still is a complete list -- among other things the number of elements is fixed when the list is computed. Both situations are unsuitable for things like parsers, which I assume is the thing you're aiming at. As far as I understand it, streams and stream parsers are not completely functional, so not suitable for arbitrary back tracking (which I sometimes would like to do). If I had a lazy list, I could write match lazy_list with Plus :: tail -> (parse_term_list n tail) Minus :: tail -> - (parse_term_list (-n) tail) _ :: -> raise (Parse_Error "expected + or - here") [] -> n Unfortunately there are no lazy lists in this sense. The solution I'm presently aiming at, works like this instead: match (prefix 5 token_stream) with .... where (prefix k) gives you a list of at least k tokens from the stream (if available) or less (if not available). 'token_stream' and 'prefix' can be implemented a way that is more efficient than just creating the prefix list every time, but there still is a certain amount of overhead, because, at the end, there always is a point where the algorithm needs to append at the list. Not the high art of programming, I know, but I didn't find any other non-camlp4 solution that allows me to read the grammar clearly from source. Regards -- Markus