Version française
Home     About     Download     Resources     Contact us    
Browse thread
Pattern matching over lazy lists
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: -- (:)
From: Markus E.L. <ls-ocaml-developer-2006@m...>
Subject: Re: [Caml-list] Pattern matching over lazy lists

> 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