Sebastian Sylvan wrote:
Dynamic programming is actually quite neat in Haskell.
You can express it quite directly using arrays.
arr = array (1,n) [ (k, foo k) | k <- [1..n]]
foo k = ...
now, foo would reference arr in some way, it it should probably
contain some base case for k=1. So you basically just let "foo k" be
the actual algorithm in question, and then arr!x (x = n most likely)
would be your final result.
Laziness is really neat here you see. You can define the array 'arr'
such that its elements actually reference 'arr' in their definition
(no need to obfuscate the algorithm with bottom-up construction like
in imperative languages).
Anyone interested in the above style of programming should check out the
SCP paper "A discipline of dynamic programming over sequence data" or
related articles on "algebraic dynamic programming" by Giegerich and
colleagues. The heart of their DSL (embedded in Haskell) is very much
like the above self-referential array idea.
Ciao, Janis.
--
Dr. Janis Voigtlaender
http://wwwtcs.inf.tu-dresden.de/~voigt/
mailto:[EMAIL PROTECTED]
_______________________________________________
Haskell-Cafe mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/haskell-cafe
