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