- Beginners - Haskell.org

Parsec Monad Type Confusion
by Aleksandar Dimitrov 10 Jul '10

10 Jul '10

Hello list, I have a rather trivial question, but one that I can't seem to get my head around. In the following example function (using Text.ParserCombinators.Parsec) I'm getting an error without the type declaration, but it compiles just fine with it: > parseNumber' :: Parser LispVal > parseNumber' = do x <- many1 digit > return $ Number . read $ x The error message when compiling without the type declaration is the following: No instance for (Text.Parsec.Prim.Stream s m Char) arising from a use of `digit' at Scheme.hs:33:30-34 Possible fix: add an instance declaration for (Text.Parsec.Prim.Stream s m Char) In the first argument of `many1', namely `digit' In a stmt of a 'do' expression: x <- many1 digit In the expression: do { x <- many1 digit; return $ Number . read $ x } The function is an example in "Write yourself a Scheme in 48 hours." I'd consider myself fairly accustomed to programming with monads; and still, I can't seem to find out *why* exactly GHC ( 6.12.1 ) cannot compile this without the type signature. What does it try to build here? Why does the inferencing fail? My best guess is that it somehow doesn't get that 'x' is supposed to be a String value ([Char], not Char.) What really confuses me, though, is that adding the instance declaration makes the whole thing work! The type declaration for LispVal looks like this: > data LispVal = Number Integer So it should be pretty clear to GHC that, due to `Number . read` demanding a [Char], I actually want x to be a [Char]. I'm assuming here that I'm just in the wrong Monad, starting with `do`. Somehow, GHC assumes it's not Parser LispVal, but something more complex, possibly Text.Parsec.Prim.Stream s m LispVal or so? Thank you everybody for you help :-) This list is a truly amazing place with a lot of helpful people! Aleks

3 4

Pattern matching vs bit twiddling?
by Patrick LeBoutillier 09 Jul '10

09 Jul '10

Hi all, I recently started writing a simulator for Knuth's MIX computer in Haskell. My first attempt had the basic data types for the machine defined like this: type Byte = Word8 type Address = Word16 type Word = Word32 type FieldSpec = (Int,Int) data Register = A Word | X Word | I Address | J Address type Memory = M.Map Address Word After hitting some kind of dead end with this setup (basically getting frustrated/lost with all the bit-twiddling), I tried again with these more abstract types: data Byte = Byte Word8 data Sign = Plus | Minus data Address = Address Byte Byte data SignedAddress = SignedAddress Sign Address data Word = Word Sign Byte Byte Byte Byte Byte data FieldSpec = FieldSpec Int Int data Memory = Memory (M.Map Address Word) Now I find my code is much clearer (it almost writes itself...) and practically absent of low-level bit operations (except, for example, converting a Word into an actual Haskell Int32 to perform the actual arithmetic). However, I'm wondering about the cost of all the "packing/unpacking" via pattern-matching and/or accessors. Perhaps I should not worry about this and optimize later if required? Is this type of premature optimization (assuming the previous version was faster...) really the root of all evil? Note: I'm not far enough into the simulator to be able to actually test it out and get metrics. Patrick Thanks, Patrick -- ===================== Patrick LeBoutillier Rosemère, Québec, Canada

3 2

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