May 2012 - Beginners - Haskell.org

How to solve this using State Monad?
by kak dod 02 Jun '12

02 Jun '12

Hello, A very good morning to all. I am a Haskell beginner. And although I have written fairly complicated programs and have understood to some extent the concepts like pattern matching, folds, scans, list comprehensions, but I have not satisfactorily understood the concept of Monads yet. I have partially understood and used the Writer, List and Maybe monads but the State monad completely baffles me. I wanted to write a program for the following problem: A DFA simulator. This I guess is a right candidate for State monad as it mainly deals with state changes. What the program is supposed to do is: ====================== It should read a description of a DFA given as a 5 tuple (q, sigma, delta, q0, finals) where - q: a finite set of states - sigma: a finite set of input symbols called the alphabet - delta: a transition function (delta : Q × S -> Q) - q0: start state (q0 belongs-to Q) - finals: a set of accept states (F belongs-to Q) def taken from wikipedia<http://en.wikipedia.org/wiki/Deterministic_finite_automaton#Formal_definiti…> and it should also read an input string (over alphabet sigma) and then it should run the input string on the DFA which it should build from the given description and should output (produce) a list of states through which the DFA has passed as it consumed the input string. You can assume that 'q' the set of state is of integers only. Also you can assume that sigma consist only of single character English alphabets ( ['A'..'Z']). The delta will be given as a list of 3-tuple. You don't need to do file IO. Sample input is following 2-tuple: input = (dfa, input-string) where dfa = ([0,1], ['A','B'], [(0,'A',0), (0,'B',1), (1,'A',1), (1,'B',0) ], 0, [1]) input-string = "AAABBABBAABBBABAAAB" Expected output: output = runDFA input -- output = [0,0,0,1,0,0,1,0,0,0,1,0,1,1,0,0,0,0,1] ====================== I wrote a recursive program to do this without using any monads. I simply send the entire dfa, the input string and its partial result in the recursive calls. How to do this using State Monad? Sorry, I may be a block-head but even after reading many tutorials on monads, I am still confused about the state monad. Either the tutorials give a very complicated example or they don't give a complete example that loads and runs properly in the GHCi . Again sorry to say, but the Random number generation example given in RealWorldHaskell didn't help me either. And yes, I have read Brent Yorgey's article on Monad tutorial fallacy too. So, you Monad gurus over here can consider me a block-head, but let me assure you people that I am a sincere person trying to learn this beautiful but difficult concept. I sincerely hope that a monadic solution (that uses Control.Monad.State ) to the DFA problem I gave, will help me understand the working of State Monad. Please note that I wish your solution to use the Control.Monad.State. Thanks in advance. kak

8 21

GHCi won't allow type declaration as shown in LYAHFGG
by Stan Kulp 31 May '12

31 May '12

I have been working my way through "Learn You a Haskell for Greater Good" and am stumped when I get to the "Syntax in Functions - Pattern Matching" section. The book shows the following expression... ghci> lucky :: (Integral a) => a -> String ...but when I try to execute it in GHCi I get the following error... <interactive>:1:1: Not in scope: `lucky' What am I missing? Stan Kulp 4421 W North Pinebrook Lane Columbia, MO 65203 Home: 573-234-2065 Work: 573-522-5075 Cell: 573-864-6051

4 4

Performance problem
by Radosław Szymczyszyn 30 May '12

30 May '12

Hello! I've had a similar problem with text processing discussed on the list some time ago (a topic about implementing a spellchecker). To keep things short'n'simple: built-in Haskell Strings are inefficient as they're simply lists of Chars, i.e. a String is in fact just a [Char]. The usually suggested solution to this problem is using the ByteString type which comes from bytestring package. It's probably all nice when you only need ASCII/Latin encodings, but it bite me when processing Unicode (e.g. Data.ByteString.UTF8 doesn't have a words function, though Data.ByteString has one). However, the performance is good. The best solution as far as I have researched is the text package and type Text. It ought to support Unicode as far as I remember and has got all the useful list-like functions. As I hadn't yet had an occasion to play with it before, I took your code and adapted it to use Text and Text.IO. Let me know what are the results, as I haven't got any test set to compare the speed before and after the modifications. === CODE -- Problem id: HASHADQI import qualified Data.List as List import qualified Data.IntMap as Map import Data.Maybe import Data.Text (Text) import qualified Data.Text as T import qualified Data.Text.IO as T type Person = (Text,Text,Text,Text) type IntPersonMap = Map.IntMap Person main = do input <- T.getContents seqAction Map.empty $ T.lines input seqAction :: IntPersonMap -> [Text] -> IO IntPersonMap seqAction m [] = return m seqAction m (l:ls) = do m' <- doAction m l seqAction m' ls doAction :: IntPersonMap -> Text -> IO IntPersonMap doAction m cmd = do case T.unpack (T.take 1 cmd) of "a" -> doInsert m $ T.words cmd "d" -> doDelete m $ T.words cmd "i" -> doInfo m $ T.words cmd "q" -> doQuery m $ T.words cmd [] -> return m doInsert :: IntPersonMap -> [Text] -> IO IntPersonMap doInsert m [_, idText, fn, ln, bd, pn] = do let id = read (T.unpack idText) :: Int if Map.member id m then do putStrLn $ "ID " ++ show id ++ " ja cadastrado." return m else return (Map.insert id (fn, ln, bd, pn) m) doDelete :: IntPersonMap -> [Text] -> IO IntPersonMap doDelete m [_, idText] = do let id = read (T.unpack idText) :: Int if Map.member id m then return (Map.delete id m) else do putStrLn $ "ID " ++ show id ++ " nao existente." return m doInfo :: IntPersonMap -> [Text] -> IO IntPersonMap doInfo m [_, idText] = do let id = read (T.unpack idText) :: Int case Map.lookup id m of Just (fn, ln, bd, pn) -> do putStrLn . show $ T.unwords [fn, ln, bd, pn] return m Nothing -> do putStrLn $ "ID " ++ show id ++ " nao existente." return m doQuery :: IntPersonMap -> [Text] -> IO IntPersonMap doQuery m (_:qs) = do let test = (\x -> foldl (&&) True $ map ($x) $ makePredicate qs) result = Map.filter test m putStrLn $ unwords . map show $ Map.keys result return m makePredicate :: [Text] -> [(Person -> Bool)] makePredicate [] = [] makePredicate (q:qs) = case (\(a,b) -> (T.unpack a, b)) (T.break (==':') q) of ("fn", x) -> (\(fn,_,_,_) -> fn == (T.drop 1 x)) : (makePredicate qs) ("ln", x) -> (\(_,ln,_,_) -> ln == (T.drop 1 x)) : (makePredicate qs) ("bd", x) -> (\(_,_,bd,_) -> bd == (T.drop 1 x)) : (makePredicate qs) ("pn", x) -> (\(_,_,_,pn) -> pn == (T.drop 1 x)) : (makePredicate qs) === END CODE Regards, Radek Szymczyszyn

2 1

Performance problem
by Jefferson Andrade 30 May '12

30 May '12

Hi! I have a basic knowledge about Haskell and I am trying to put this knowledge to work with a few exercises. The one I am trying now is basically the following. 1. I must read from the standard input a series of text lines. Each line represents a command that must be performed. The possible commands are: add <id> <first-name> <last-name> <birth-date> <phone-number> del <id> info <id> query (key:value)+ 2. Each command may or may not generate an output on the standard output according to a series of conditions (if an entry with the same ID already exists, if the id of a del does not exists, if the id of an info does not exists). Also, the info and query command also generate output on the normal working. 3. The program is working, I suppose, but when I submit it for testing and ranking on spoj.pl I get a timeout. The maximum allowed time for this problem is 6s. My code is the following: ===== Begin of source code ===== -- Problem id: HASHADQI import qualified Data.List as List import qualified Data.IntMap as Map import Data.Maybe type Person = (String,String,String,String) type IntPersonMap = Map.IntMap Person main = do input <- getContents seqAction Map.empty $ lines input seqAction :: IntPersonMap -> [String] -> IO IntPersonMap seqAction m [] = return m seqAction m (l:ls) = do m' <- doAction m l seqAction m' ls doAction :: IntPersonMap -> String -> IO IntPersonMap doAction m cmd = do case cmd of 'a':cs -> doInsert m (words cmd) 'd':cs -> doDelete m (words cmd) 'i':cs -> doInfo m (words cmd) 'q':cs -> doQuery m (words cmd) [] -> return m doInsert :: IntPersonMap -> [String] -> IO IntPersonMap doInsert m [_, idText, fn, ln, bd, pn] = do let id = read idText :: Int if Map.member id m then do putStrLn $ "ID " ++ show id ++ " ja cadastrado." return m else return (Map.insert id (fn, ln, bd, pn) m) doDelete :: IntPersonMap -> [String] -> IO IntPersonMap doDelete m [_, idText] = do let id = read idText :: Int if Map.member id m then return (Map.delete id m) else do putStrLn $ "ID " ++ show id ++ " nao existente." return m doInfo :: IntPersonMap -> [String] -> IO IntPersonMap doInfo m [_, idText] = do let id = read idText :: Int case Map.lookup id m of Just (fn, ln, bd, pn) -> do putStrLn $ unwords [fn, ln, bd, pn] return m Nothing -> do putStrLn $ "ID " ++ show id ++ " nao existente." return m doQuery :: IntPersonMap -> [String] -> IO IntPersonMap doQuery m (_:qs) = do let test = (\x -> foldl (&&) True $ map ($x) $ makePredicate qs) result = Map.filter test m putStrLn $ unwords . map show $ Map.keys result return m makePredicate :: [String] -> [(Person -> Bool)] makePredicate [] = [] makePredicate (q:qs) = case List.break (==':') q of ("fn", ':':x) -> (\(fn,_,_,_) -> fn == x) : (makePredicate qs) ("ln", ':':x) -> (\(_,ln,_,_) -> ln == x) : (makePredicate qs) ("bd", ':':x) -> (\(_,_,bd,_) -> bd == x) : (makePredicate qs) ("pn", ':':x) -> (\(_,_,_,pn) -> pn == x) : (makePredicate qs) ===== End of source code ===== Can any one explain where is the source(s) of inefficiency and suggest how to make this program more efficient? Thanks in advance, Jeff.

1 0

State and GUI's / external interfaces / events
by Henry Lockyer 29 May '12

29 May '12

Hi all, I'm trying to straighten out my basic understanding around state-based IO handling in Haskell. I've been reading around in several places but it hasn't clicked yet, and the input buffer is now cluttered with new things to assimilate ;-) The basic question is about what ways there are to implement state-based decisions, where an external event of some kind results in some Haskell function/s being called depending on the particular event and the current state, then perhaps some new external action initiated, and new state set. Basic state machine type of logic. As a starting point I include down at the bottom of this mail a little example program which implements something like this for terminal IO. The state/logic could be made arbitrarily more complex. It's a simple 'event loop' that blocks on getChar until a Char is input, with a separate pure event/state query function. One could also implement the per-Char state-based handling using the State monad by mapping over the Char inputs as a string, for example something like: main = do hSetBuffering stdin NoBuffering interact \str -> evalState ( mapM charfunc str ) initstate where charfunc :: Char -> State Char Char . . . I'm not sure how I would implement the exit case if I used this approach for the 'aha!' game below though. Anyway, a few interrelated questions running out from this general starting point: 1. I've not really played with monad transformers yet, but I guess one could use monad transformers to make a combined IO/State monad as an alternative to the basic solution down below. Assuming there is no lurking problem with doing that, does it help? (I can't see much advantage, in this case where explicitly manipulating the state at each step is the main activity.) 2. The 'event loop' in IO in the example below drives the state lookup/branching logic, but how can you separate the sequential state logic from the polling process? This is really the nub of my question. I'm not familiar with the FFI or the GUI libraries, so with apologies in advance for misunderstanding it all... say for example we want to implement a Haskell program that responds to events arriving as external function calls via the FFI where the state-based logic is in Haskell but the events are not polled for, they just arrive (for example could be driven by some main loop in external functionality, eg. GUI). We want the Haskell implementation to respond in a sequential state-based manner so that if the external events/calls 'a', 'a', 'h' arrive this could produce different responses (to the second and third events) compared to the event sequence 'a', 'h', 'a'. How/can you do this in Haskell? The events could come from some completely independent and/or uncontrollable sources but we require the Haskell program to respond according to arrival sequence. My intuition says that this is not possible if the events arrive simply as independent function calls on an external interface, but that they must be collected somehow into a single sequential entity such as a file, list, 'stream' or somesuch and then they can be mapped over or some kind of read loop can pull them off in sequence as in the example below. But I am probably wrong :) ? 3. What state/event handling model do the GUI solutions like whhaskell or gtk2hs use? I read that they use callbacks, which makes sense, but does it mean that the callbacks must be manipulated (or some associated widget attributes) so as to encode the state back into the GUI at every step? In other words the first 'a' in the above "aah" vs "aha" example would have to, as a minimum, initiate a change in the callback/attributes of the 'a' generator so that the second 'a' will actually be a different 'a' ( 'a2' perhaps) or carry some additional parameter info so that the correct function in the receiving Haskell is invoked? This could be horrible if there are, say, 50 different widgets that could generate the next event and they would all have to be updated to reflect each state change. I feel it must be better than this somehow.. So how does it work? Any help appreciated. Thanks/ Henry -- -- "aha!" -- -- An exciting game that requires the string "aha!" to -- be entered in order to reach the exit. -- import System.IO type MyState = Char initstate, exitstate :: MyState initstate = 'a' exitstate = 'z' main :: IO () main = do hSetBuffering stdin NoBuffering stateIO initstate stateIO :: MyState -> IO () stateIO s = do c_in <- getChar let (c_out, s') = stateMC c_in s putStrLn $ ' ':c_out:[] if s' /= exitstate then stateIO s' else putStrLn "Bye..." stateMC :: Char -> MyState -> (Char, MyState) stateMC 'a' 'a' = ('Y', 'b') stateMC 'h' 'b' = ('Y', 'c') stateMC 'a' 'c' = ('Y', 'd') stateMC '!' 'd' = ('*', 'z') stateMC _ _ = ('N', 'a')

1 1

Re: [Haskell-beginners] Category question
by Manfred Lotz 29 May '12

29 May '12

On Mon, 28 May 2012 10:57:11 -0400 Brent Yorgey <byorgey(a)seas.upenn.edu> wrote: > On Mon, May 28, 2012 at 04:14:40PM +0200, Manfred Lotz wrote: > > > > For me id: A -> A could be defined by: A morphism id: A -> A is > > called identity morphism iff for all x of A we have id(x) = x. > > This is not actually a valid definition; the notation id(x) = x does > not make sense. It seems you are assuming that morphisms represent > some sort of function, but that is only true in certain special > categories. > Ok, it is a valid definition only in a certain context. In the far wider context of category theory this indeed makes no sense. > > My point is that in the books about category theory those two > > statements are stated as axioms, and id is (in many books) just > > self understood or defined as I have defined it above. > > > > If in a book about category the author would say that for each > > object A there must exist a morphism id: A -> A (called identity > > morphism) which is defined by idB . f = f and f . idA = f then this > > would be clearer (and better, IMHO). > > This is exactly what category theory books do (or should) say. Do you > have a particular example of a book which does not state things in > this way? > In 'Conceptual Mathematics' by F. William Lawvere, Stephen H. Schanuel they define an identity map with fa = a for each a in A. Then on page 17 they define category and say ... Identity Maps: (one per object) 1A: A -> A ... Rules for a category 1. The identity laws: where they say g . 1A = g and 1B . f = f 2. associatlve laws ... It seems that this definition of a category is not as general as it could be. Here 1. is something which follows easily from the definition of an identity map. I guess that this made me think of idA as idA(x) = x for each x of A. Later when I saw other (more general) definitions I did not read carefully to realize the difference. Thanks a lot for making this clear to me. -- Manfred

3 4

monad transformer show help
by rickmurphy 29 May '12

29 May '12

Hello All: Over the past few days I got my first exposure to monad transformers. I worked through the sample below. The witness w displays IC 0 as expected, but even after providing the instance of show for type O I a, witness w' causes ghci to display No instance for (Num (I' a0)) arising from a use of w' Possible fix: add an instance declaration for (Num (I' a0)) Would someone be able to explain why after providing the instance of show on O I a, w' does not print the expected result (OC (IC 0)) ? BTW - You will notice the sample intentionally avoids the use of deriving (Show) on newtype I. -- Rick {-# LANGUAGE NoMonomorphismRestriction, DatatypeContexts, FlexibleContexts, FlexibleInstances #-} module Main where import Control.Monad import Control.Monad.Trans.Class <snip> -- |A parameterized new type I representing an "inner type" with one constructor IC newtype I a = IC a -- deriving (Show) -- |Unwraps the value in the inner type unI (IC x) = x -- |A monad instance on the inner type instance Monad I where return = IC m >>= f = f (unI m) instance Show a => Show (I a) where show (IC x) = "IC " ++ show x -- |Witness on inner type w :: Num a => I a w = (IC 0) >>= return . id -- |A parameterized new type O m a representing an "outer type" with a named constructor newtype O m a = OC {runO :: m (I a)} -- deriving (Show) -- |? instance Show a => Show (O I a) where show (OC x) = "OC (IC " ++ show (unI x) ++ "))" -- show (OC (IC 0)) -- |Unwraps the value in the outer type unO (OC (IC a)) = a -- |A monad transformer instance on type O m a instance Monad m => Monad (O m) where return = OC . return . IC m >>= f = OC $ do {v <- runO m; runO (f (unI v))} -- | Witness on monad transformer w' :: Num (I a) => O I a w' = (OC (IC 0)) >>= return . id -- | Executes addition on the zero in IC w'' :: Num a => I a w'' = liftM (+1) (IC' 0) -- |Instance of monad transformer lift on O m a instance MonadTrans O where lift m = OC (m >>= return . IC) -- |Executes addition on the zero in IC and lifts to O m a w''' :: (Num a, MonadTrans t) => t I a w''' = lift ((IC 0) >>= return . (+1))

2 1

problems with wxHaskell installation
by Miguel Negrao 28 May '12

28 May '12

Hi I had wxHaskell working but since I installed the gtk2hs, which updated some packages I’m having some trouble. I’ve installed wxWidgets and wxHaskell again following the instructions in it’s webpage. When I compile a simple wxHaskell program* I get this error: dyld: Symbol not found: _wxTheAssertHandler Referenced from: /Users/miguelnegrao/Library/Haskell/ghc-7.0.4/lib/wxc-0.90.0.3/lib/libwxc.dylib Expected in: /usr/local/lib/libwx_baseu-2.9.3.0.0.dylib in /Users/miguelnegrao/Library/Haskell/ghc-7.0.4/lib/wxc-0.90.0.3/lib/libwxc.dylib Trace/BPT trap: 5 How can I fix this ? thank you, Miguel Negrão I’m on OSX 10.7.3 haskell platform with ghc 7.0.4 brew info wxmac wxmac 2.8.12 http://www.wxwidgets.org /usr/local/Cellar/wxmac/2.9.3.1 (764 files, 26M) * Installed with: --devel https://github.com/mxcl/homebrew/commits/master/Library/Formula/wxmac.rb cabal info wx * wx (library) Synopsis: wxHaskell Versions available: 0.11.1.0, 0.11.1.2, 0.12.1.4, 0.12.1.5, 0.12.1.6, 0.13.2, 0.13.2.1, 0.90, 0.90.0.1 (and 10 others) Versions installed: 0.13.1, 0.90 Program : module Main where import Graphics.UI.WX main :: IO() main = start gui gui :: IO() gui = do f <- frame [text := "window"] txt <- staticText f [text:= "test 123"] but <- button f [text:="button", on command:=set txt [text:="clicked"]] check <- checkBox f [text:="test"] rbox <- radioBox f Vertical ["hello","wold"] [] set f [layout:= boxed "all" (row 0 [ column 0 [widget check, widget rbox], boxed "second2" $ column 0 [widget txt, widget but] ]) ] return ()

3 6

Category question
by Manfred Lotz 28 May '12

28 May '12

Hi there, I know that this might be the wrong forum to ask. In this case I would appreciate any hint where there is a good place to ask. In the definition of a (mathematical) category it is said (among other things), that for any object A there exists an identity morphism: idA: A -> A and if f: A -> B for two objects A, B then idB . f = f and f . idA = f must hold. My question: Because I cannot think of any counterexample for the last statement I would like to know if I just could omit this from the definition and formulate this as a small theorem. Or does there exist a counterexample where all conditions of a category hold but there exist two objects A, and B where we have idB . f <> f and/or f .idA <> f? -- Manfred

5 7

Linking C library with haskell in Windows
by kotshie 27 May '12

27 May '12

Hi all, I created Haskell Bindings to the NetCDF Library on linux and everything works well, bute when trying to ported to windows, I keep receiving undefined references when linking. I changed the stdcall on the FFI's, played with the cabal file to link to different libraries, both built on VC and MinGW but still can't find the solution Linking Test.exe ... .\NetCDFRaw.o:fake:(.text+0x2eb): undefined reference to `nc_create@12' .\NetCDFRaw.o:fake:(.text+0x45f): undefined reference to `nc_open@12' .\NetCDFRaw.o:fake:(.text+0x5e5): undefined reference to `nc_def_dim@16' .\NetCDFRaw.o:fake:(.text+0x787): undefined reference to `nc_inq_dimid@12' .\NetCDFRaw.o:fake:(.text+0x92e): undefined reference to `nc_def_var@24' .\NetCDFRaw.o:fake:(.text+0xb35): undefined reference to `nc_put_att_text@16' .\NetCDFRaw.o:fake:(.text+0xd0a): undefined reference to `nc_put_att_int@24' .\NetCDFRaw.o:fake:(.text+0xf32): undefined reference to `nc_put_att_double@24' .\NetCDFRaw.o:fake:(.text+0x1148): undefined reference to `nc_inq@20' .\NetCDFRaw.o:fake:(.text+0x130e): undefined reference to `nc_inq_ndims@8' Is there something I am missing? kotshie

2 2