3 ms·
> Probably the most language agnostic algorithm Are you sure about this point? I'd like to see a purely functional implementation of this, e.g. in Haskell with
by 0-_-0 8y ago
> Probably the most language agnostic algorithm
Are you sure about this point? I'd like to see a purely functional implementation of this, e.g. in Haskell without monoids. I believe it's significantly harder than a C implementation (which is indeed a few lines)
- jaspervdj 8y agoNot really, if you wanted to do a version using only immutable arrays: import Data.Array fw :: Int -> Array (Int, Int) Int -> Array (Int, Int) Int fw 0 graph0 = graph0 fw k graph0 = let fw' = fw (k - 1) graph0 in array (bounds graph0) [ ((i, j), min (fw' ! (i, j)) ((fw' ! (i, k)) + (fw' ! (k, j)))) | (i, j) <- range (bounds graph0) ] The only difference with a mutable implementation is that you use a new array for every k, whereas in a mutable version you would reuse these.
- andrewflnr 8y agoIIRC you can express it with matrix multiplication, but there might be some big caveats on that.