- Beginners - Haskell.org

Re: [Haskell-beginners] Dynamic Programming in Haskell
by Ali Razavi 08 Jul '10

08 Jul '10

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? Ali > Date: Wed, 07 Jul 2010 11:30:28 +0200 > From: Heinrich Apfelmus <apfelmus(a)quantentunnel.de> > Subject: [Haskell-beginners] Re: Dynamic Programming in Haskell > To: beginners(a)haskell.org > Message-ID: <i11hfk$828$1(a)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 >

3 2

Dynamic Programming in Haskell
by Ali Razavi 08 Jul '10

08 Jul '10

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. Best, Ali import Data.Array pp = [30,35,15,5,10,20,25] para p = let n = length p - 1 msij = array ((1,1),(n,n)) ([((i,j), (0,0)) | i <-[1..n], j <-[1..n]] ++ [((i,j), (m, s))| l<-[2..n] , i<-[1..n-l+1] , let j = i + l - 1 , let qs = [q|k<-[i..j-1] , let q = fst (msij!(i,k)) + fst (msij!(k+1, j)) + p!!(i-1)*p!!k*p!!j] , let (m, s, c) = foldl (\(mz,sz,ind) x-> if x < mz then (x,ind,ind+1) else (mz,sz,ind+1)) (head qs, i, i) qs ]) in msij chainSolve p = let sol = para p n = length p - 1 in do print $ fst $ sol!(1,n) putStrLn $ printSol sol 1 n "" where printSol s i j o = if i == j then o ++ "A" ++ (show i) else o ++ "(" ++ (printSol s i (snd (s!(i,j))) o) ++ (printSol s ((snd (s!(i,j)))+1) j o) ++ ")"

4 5

Evaluate behaviour
by Tom Hobbs 08 Jul '10

08 Jul '10

Hi guys, Thanks to everyone who helped me, I hit a milestone this evening and finally got the (small) bit of functionality I was working on, working! A huge "thank you" to everyone who has taken the time to use very small words to explain things to me! (I just need to sort out some nicer error handling now...) Just one more question... for today. Here's my code; import Network import System.IO (hGetLine,hClose,hPutStrLn,hSetBuffering,BufferMode(..),Handle,stdout) import Data.Bits import Data.Binary import Data.Binary.Put import Data.Binary.Get import qualified Data.ByteString.Lazy as L import qualified Data.ByteString.UTF8 as UTF import Control.Monad import Control.Exception (evaluate) ping a t = do h <- connectTo a (PortNumber t) hSetBuffering h NoBuffering L.hPut h (encode (0xFAB10000 :: Word32)) numStrings <- fmap (fromIntegral . runGet getWord64be) $ L.hGet h 8 names <- (fmap (runGet $ readStrings numStrings) $ L.hGetContents h) evaluate names hClose h return names readStrings :: Int -> Get [String] readStrings n = replicateM n $ do len <- getWord32be name <- getByteString $ fromIntegral len return $ UTF.toString name This works in GHCi exactly as I want it to. Note the call to "evaluate" in the ping function which allows me to close the handle before returning the IO [String]. This behaviour prints out the list of Strings as read from the handle in GHCi, exactly what I wanted it to do. Here's the strange part; If I remove the evalute line, and instead have; names <- evaluate (fmap (runGet $ readStrings numStrings) $ L.hGetContents h) GHCI claims that this is okay, but when I call ping I don't get any output. I don't get any errors either, but I would expect to see the same list of Strings as before. Can anyone explain to me why that happpens? I'm assuming it's something to do with the "<-" magic, but I don't know what. Thanks, Tom -- Using Opera's revolutionary e-mail client: http://www.opera.com/mail/

2 2

reverse 'lookup'
by Patrick LeBoutillier 07 Jul '10

07 Jul '10

Hi, The lookup function can locate something in a a-list: lookup :: Eq a => a -> [(a,b)] -> Maybe b is there an easy way to do a reverse lookup: rlookup :: Eq b => b -> [(a,b)] -> Maybe a or perhaps a builtin function to flip a pair: (a, b) -> (b, a) Thanks, Patrick -- ===================== Patrick LeBoutillier Rosemère, Québec, Canada

3 2

modules
by Michael Mossey 07 Jul '10

07 Jul '10

So I created the following directory structure: home /MusDoc/MusDoc.hs home /MusDoc/FromXML.hs home /MusDoc/Timing.hs home /Midi/FromMusDoc.hs I set -i to "home" referred to above, so I import these modules with commands like import MusDoc.MusDoc import Midi.FromMusDoc etc.. What do I do to import everything in MusDoc via import MusDoc ? I suspect this has something to do with packages... don't feel a need to explain it all---point me to a good explanation and I'll probably figure it out. Mike

2 1

Some beginning questions for Haskell
by Liu shuping 07 Jul '10

07 Jul '10

Hi, I am new to Haskell, currently I am doing .Net development on windows platform. I began to know about Haskell for the reason when I knew some C# lambda features come from functional language. I am interested in Haskell from the very beginning when I saw it. For I am really a very beginner, I get some basic questions: 1. Can you have some very general information to explain why use Haskell or functional language. 2. Is it a right choice of Haskell if I want to develop some geology software which mainly doing some huge numerical computation which takes long long time? 3. How about user interface, is Haskell capable to build application with complex user interface? or should I just use Haskell to build the core engine and user other language to build the user interface? 4. Is Haskell cross-platform? I mean if the Haskell source code is "code once and build everywhere?" 5. Are there any successful applications built with Haskell? they can give me a direct scene of what Haskell can do. I appreciated any of your information or comments. -- Sincerely, Liu Shuping Ocean University of China Email: lsp.lhh(a)gmail.com

3 2

what's a proper way to make a Set typeclass? and why is it not done already?
by Markus Läll 07 Jul '10

07 Jul '10

I started like this: {-# LANGUAGE MultiParamTypeClasses, FlexibleInstances #-} import qualified Data.List as L class (Eq e) => Set s e where empty :: s e fromList :: [e] -> s e ... ..and started to implement it on a list: instance (Eq e) => Set [] e where empty = [] fromList xs = L.nub xs But I can't understand, why there has to be a (Eq a) context to the Set instance of a list, when the class definition seems to already say it? It won't compile without it.. Secondly, why do I need FlexibleInstances -- it gives me an eror which I don't understand ("all instance types must be of the form T a1 ... an" and so on, and recommends to add the flexible instances.) Also I couldn't find other elaborate Set typeclasses -- there seems to be only the "Set a" type. Why is that(?), because you could use other datastructures, better and worse in various ways, than the balanced binary tree.. Markus

2 3

type of pattern matching
by Michael Mossey 07 Jul '10

07 Jul '10

What if I want to check if a variable uses a particular constructor, but I don't want to unpack it. For example: data Item = Note Int Float Rational [Int] [Float] | Dynamic Int And I want to write doSomething :: Maybe Result doSomething item = case item of note@(Note _ _ _ _ _) -> Just $ process note _ -> Nothing But I don't like writing "Note _ _ _ _ _" Thanks, Mike

4 4

reading and playing music openAL
by Maria Gabriela Valdes 06 Jul '10

06 Jul '10

Hi ! We have a question about about openAL. We would like to know if anybody knows how to read a WAV file by chunks of a determined size, and after doing some processing with a specific chunk send that same chunk back to the sound card so we can play the whole WAV continiously (just like a music player). Thanks in advance, -- Maria Gabriela Valdes G. Linux Registered User #485743

1 0

playing music openAL
by Maria Gabriela Valdes 06 Jul '10

06 Jul '10

Hi ! We have a question about about openAL. We would like to know if anybody knows how to read a WAV file by chunks of a determined size, and after doing some processing with a specific chunk send that same chunk back to the sound card so we can play the whole WAV continiously (just like a music player). Thanks in advance, -- Maria Gabriela Valdes G. Linux Registered User #485743

1 0