From: "Markus E.L." <ls-ocaml-developer-2006@m-e-leypold.de>
To: caml-list@yquem.inria.fr
Subject: Re: [Caml-list] Pattern matching over lazy lists
Date: Wed, 11 Jul 2007 13:13:10 +0200 [thread overview]
Message-ID: <e94pkb6vnd.fsf@hod.lan.m-e-leypold.de> (raw)
In-Reply-To: <200707102338.47010.jon@ffconsultancy.com> (Jon Harrop's message of "Tue, 10 Jul 2007 23:38:46 +0100")
> 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
next prev parent reply other threads:[~2007-07-11 11:02 UTC|newest]
Thread overview: 4+ messages / expand[flat|nested] mbox.gz Atom feed top
2007-07-10 22:38 Jon Harrop
2007-07-11 8:44 ` [Caml-list] " Loup Vaillant
2007-07-11 11:13 ` Markus E.L. [this message]
2007-07-11 15:51 ` Martin Jambon
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=e94pkb6vnd.fsf@hod.lan.m-e-leypold.de \
--to=ls-ocaml-developer-2006@m-e-leypold.de \
--cc=caml-list@yquem.inria.fr \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).