Daniel Fischer wrote:
Heinrich Apfelmus wrote:
I didn't need to debug this code, because it's obviously correct. Put differently, instead of spending my effort on debugging, I have spent it on making the solution elegant.
Well done. Chapeau!
:) Well, apart from the fact that the "obviousness" of this code also depends on the correctness of this particular division into subproblems, there is one piece of the code that is quite error-prone, namely the definition of chain and chain' : chain = memoize n chain' chain' i j | i == j = Matrix (dimensions ! i) | otherwise = best [mul (chain i k) (chain (k+1) j) | k <- [i..j-1] ] It is really easy to accidentally write chain' instead of chain and vice versa, leading to a black hole or a loss of memoization. (Using more distinct names doesn't necessarily help because there is almost no semantic difference between the two functions.) Trouble is that the type system won't catch such mistakes because the two functions have the same type. However, we can give chain and chain' different types by using the fixed point combinator and writing: chain = fix (memoize n . chain') chain' chain i j | i == j = Matrix (dimensions ! i) | otherwise = best [mul (chain i k) (chain (k+1) j) | k <- [i..j-1] ] Shadowing the variable chain in the definition of chain' is both intentional and harmless, since both variables chain will be bound to the very same function. In any case, chain' and chain now have different types and the burden of checking whether we've used them correctly is left to the compiler. (For those who don't know the fixed point combinator yet: I have recently made a short video about it: http://apfelmus.nfshost.com/blog/2010/07/02-fixed-points-video.html ) Regards, Heinrich Apfelmus -- http://apfelmus.nfshost.com