[Haskell-beginners] Re: Dynamic Programming in Haskell

[Heinrich Apfelmus]

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