Pattern matching over lazy lists

Pattern matching over lazy lists

[Jon Harrop]

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...

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

Re: [Caml-list] Pattern matching over lazy lists

[Loup Vaillant]

(Sorry for the double post)

2007/7/11, Jon Harrop <jon@ffconsultancy.com>:
> 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...


You are talking about streams, right? Not just the suspension of a
regular list? Camlp4 provide "functional streams", which are not
destructive. If you don't want to use that...

...At least, you can deconstruct the very first suspension :

match force l with
| Empty -> (****)
| Cons x l -> (****)

might do it. maybe :

match hd (force l) with
| 0 -> (****)
| x -> (****)

would be better for your purpose.

However, with more than one element (3 here) :

match
 hd (force l),
 hd (force (tl (force l))),
 hd (force (tl (force (tl (force l)))))
with
| 0, 0, 0 -> (****)
| x, y, z -> (****)

Quite ugly. In that case, I suggest you write a "peek_n" function
which take a stream as input, and provide you a list (or tuple, or
whatever) as output, so you can match it directly :

match peek_n 3 l with
| [0; 0; 0] -> (****)
| [x; y; z] -> (****)
| _ -> failwith "impossible error"

Did I answer your question?

Loup Vaillant

PS :

> I don't think you can deconstruct a lazy value in a pattern match...

Why not? A lazy value is a value like any other. (Whoops, I just
looked at the Lazy module, which hide some magic... compiler
optimizations?)

Re: [Caml-list] Pattern matching over lazy lists

[Markus E.L.]

> 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

Re: [Caml-list] Pattern matching over lazy lists

[Martin Jambon]

On Tue, 10 Jul 2007, Jon Harrop wrote:

>
> 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...

You can use this approach:

   http://martin.jambon.free.fr/micmatch-manual.html#htoc13

I found this convenient for "sliding window" signal analysis.

It requires micmatch and a 3.09-compatible version of camlp4.


Martin