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:voigt@tcs.inf.tu-dresden.de