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