Steffen Mazanek wrote:
apfelmus wrote
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
Note that there are very systematic and natural ways to derive dynamic
programming algorithms in functional languages. In a sense, much of the
work of R. Bird centers this topic. The book Algebra of Programming
http://web.comlab.ox.ac.uk/oucl/research/pdt/ap/pubs.html#Bird-deMoor96:Algebra
Steffen Mazanek wrote:
I have two questions regarding a Cocke, Younger, Kasami parser.
type NT = Char -- Nonterminal
type T = Char -- Terminal
-- a Chomsky production has either two nonterminals or one terminal on its
right-hand side
type ChomskyProd = (NT, Either T (NT, NT))
-- a
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
