Send Beginners mailing list submissions to beginners@haskell.org To subscribe or unsubscribe via the World Wide Web, visit http://www.haskell.org/mailman/listinfo/beginners or, via email, send a message with subject or body 'help' to beginners-requ...@haskell.org
You can reach the person managing the list at beginners-ow...@haskell.org When replying, please edit your Subject line so it is more specific than "Re: Contents of Beginners digest..." Today's Topics: 1. Re: Dynamic Programming in Haskell (Daniel Fischer) ---------------------------------------------------------------------- Message: 1 Date: Wed, 7 Jul 2010 18:46:40 +0200 From: Daniel Fischer <daniel.is.fisc...@web.de> Subject: Re: [Haskell-beginners] Dynamic Programming in Haskell To: beginners@haskell.org Cc: Ali Razavi <ali.raz...@gmail.com> Message-ID: <201007071846.41016.daniel.is.fisc...@web.de> Content-Type: text/plain; charset="utf-8" On Wednesday 07 July 2010 18:40:07, Ali Razavi wrote: > Thanks a lot for your through and informative response. Your solution is > well-structured and pellucid. The only part I don't understand is in the > definition of Parens: > > data Parens = Mul !Cost Dimension Parens Parens > > | Matrix Dimension deriving (Show) > > What is the exclamation mark in !Cost, and what does it signify? It's a strictness annotation and signifies that a Mul-value must always be constructed with an evaluated Int and not with a reference to a computation. > > > Ali > > > Date: Wed, 07 Jul 2010 11:30:28 +0200 > > From: Heinrich Apfelmus <apfel...@quantentunnel.de> > > Subject: [Haskell-beginners] Re: Dynamic Programming in Haskell > > To: beginners@haskell.org > > Message-ID: <i11hfk$82...@dough.gmane.org> > > Content-Type: text/plain; charset=UTF-8; format=flowed > > > > Ali Razavi wrote: > > > In order to practice Haskell, I decided to program some algorithms > > > from > > > > the > > > > > CLRS book. Particularly, I tried to implement the Matrix Chain Order > > > from Chapter 15 on Dynamic Programming. > > > Here is my code. It seems to work, however, it looks ugly and it was > > > a nightmare to debug. I appreciate comments about a more elegant > > > solution, > > > > and > > > > > generally the best way to implement these kinds of algorithms in > > > Haskell. Style improvement suggestions are also welcome. > > > > Dynamic programming algorithms follow a common pattern: > > > > * Find a suitably small collection of subproblems that can be used to > > solve the original problem > > * Tabulate the solutions to the subproblems, also called *memoization* > > > > These are two separate concerns and, unlike the prototype imperative > > solutions, are best implemented separately. > > > > Thanks to lazy evaluation, memoization can be implemented very > > elegantly in Haskell. First, it should be a higher-order functions and > > second, you don't need to implement a particular order by which the > > memo table is filled, lazy evaluation will figure that out for you. > > You already know the latter trick, but here is another example: > > > > http://article.gmane.org/gmane.comp.lang.haskell.beginners/554 > > > > > > But it doesn't stop here: there are very systemic ways to tackle the > > first part of dynamic programming, i.e. to *derive* dynamic > > programming algorithms from just the problem specification! An example > > and further references are given here > > > > > > http://thread.gmane.org/gmane.comp.lang.haskell.cafe/42316/focus=42320 > > > > > > Concerning matrix chain multiplication, here is my implementation. > > Note the use of telling names and algebraic data types; there is no > > need to get lost in a maze of twisty little indexes, all alike. > > > > import Data.List > > import Data.Array > > import Data.Ord > > > > type Dimension = (Int,Int) > > type Cost = Int > > -- data type representing a parenthesization, > > -- caches cost to calculate and dimension of the result matrix > > data Parens = Mul !Cost Dimension Parens Parens > > > > | Matrix Dimension deriving (Show) > > > > -- retrieve cached vallues > > cost :: Parens -> Cost > > cost (Mul c _ _ _) = c > > cost (Matrix _) = 0 > > > > dimension :: Parens -> Dimension > > dimension (Mul _ d _ _) = d > > dimension (Matrix d) = d > > > > -- smart constructor > > mul :: Parens -> Parens -> Parens > > mul x y = Mul (cost x + cost y + n*m*p) (n,p) x y > > where > > (n,m,p) = (fst $ dimension x, snd $ dimension x, > > snd $ dimension y) > > > > -- dynamic programming algorithm > > solve :: [Int] -> Parens > > solve matrices = chain 1 n > > where > > n = length matrices - 1 > > dimensions = array (1,n) . zip [1..] $ > > zip (init matrices) (tail matrices) > > > > 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] ] > > > > best = minimumBy (comparing cost) > > > > -- memoize a function on a "square" [1..n] x [1..n] > > memoize :: Int -> (Int -> Int -> a) -> (Int -> Int -> a) > > memoize n f = \i j -> table ! (i,j) > > where > > table = array ((1,1),(n,n)) $ > > [((i,j), f i j) | i <- [1..n], j <- [1..n]] > > > > Example output: > > > > *Main> cost $ solve [10,100,5,50,1] > > 1750 > > > > 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. > > > > > > Regards, > > Heinrich Apfelmus ------------------------------ _______________________________________________ Beginners mailing list Beginners@haskell.org http://www.haskell.org/mailman/listinfo/beginners End of Beginners Digest, Vol 25, Issue 24 *****************************************