[Haskell-cafe] Re: CYK-style parsing and laziness

[Steffen Mazanek]

Once again thank you apfelmus :-)

The key point of the dynamic programming algorithm is indeed to memoize
> the results gs i j for all pairs of i and j. In other words, the insight
> that yields a fast algorithm is that for solving the subproblems gs i j
> (of which there are n^2), solution to smaller subproblems of the same
> form are sufficient. Tabulation is a must.


I understand this, however I thought it would be possible to use the
automatic
collapsing of the termgraphs in some way.

Of course, you can still choose how to represent the table. There's a
> nice higher order way to do that
>
>   tabulate :: (Int -> Int -> a) -> (Int -> Int -> a)
>
>   gs = tabulate gs'
>      where
>      gs' 1 j = ... uses  gs x y  for some  x y ...
>      gs' i j = ... ditto ...


Thank you for this explanation. Your approach is not very concise either but
it does
not pollute the algorithm so much.

That would be strange. I mean, no gs i j may have more than two
> elements, namely S or A. The other key point of the CYK algorithm is
> that the sets gs i j are indeed sets and may only contain as many
> elements as there are nonterminals.


...  You are right, of course. I have tried a nub before the list
comprehension
however this is evaluated too late. I should really use sets, however, I
would
miss the list comprehension syntactic sugar sooo much. Is there something
similar for real Data.Set?

Best regards,
Steffen
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20070523/13e1573a/attachment-0001.htm