[Haskell-cafe] Implementation of the Floyd-Warshall algorithm

[Janis Voigtlaender]

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 at tcs.inf.tu-dresden.de