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
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
