[Haskell-cafe] List algorithm

[Steffen Mazanek]

Thank you for your responses.

My algorithm that needs the described function performs
so horribily bad that I understand now the need for CNF :-)

The idea was to write a CYK-style parser for an arbitrary
context-free grammar without transformation to CNF.
To compute derivations for a span of length i
I wanted to iterate over all productions p, counting
the number n of Nonterminals at the right-hand side of p,
computing all lists with n numbers whose sum is i and
split the span accordingly. It works, however, the strings
have to be very, very short *g*

Ciao and Thx,
Steffen

2007/5/22, Jules Bean <jules at jellybean.co.uk>:
>
> Matthew Brecknell wrote:
> > This seems to work, but presumably only because it's a boxed array, and
> > the construction makes no circular references.
>
>
> Yes, AIUI the boxed arrays are strict in indices but lazy in values.
> Therefore they can be used for this kind of memoization trick as long as
> you're access the elements in 'some sensible order' (that is the
> calculation dependencies are well-ordered).
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>



-- 
Dipl.-Inform. Steffen Mazanek
Institut für Softwaretechnologie
Fakultät Informatik

Universität der Bundeswehr München
85577 Neubiberg

Tel: +49 (0)89 6004-2505
Fax: +49 (0)89 6004-4447

E-Mail: steffen.mazanek at unibw.de
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20070522/1028d936/attachment.htm