- Beginners - Haskell.org

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

Missing some functions in Hoogle
by Ken Kawamoto 26 May '12

26 May '12

Hi, I'm looking for a way to search Hoogle for Yesod related functions, say, renderRoute in Yesod.Routes.Class. First I confirmed the Hoogle site doesn't have it in index. http://www.haskell.org/hoogle/?hoogle=renderRoute Then, after installing hoogle via cabal, I built index over all packages that I have by "hoogle data -l -v all". Below is an excerpt of the output, looks like yesod-routes is imported to database, or indexed, correctly. However, local Hoogle still doesn't return any entry when I searched for "renderRoute". ---- "hoogle data -l -v all" output Starting yesod Starting yesod-auth Starting yesod-core Starting yesod-routes Skipped 1 warnings in yesod-routes Parse error 11:48: Parse error: family Converting yesod-routes... done Finished yesod-routes Skipped 4 warnings in yesod-core Parse error 683:77: Parse error in expression: _ Parse error 710:48: Parse error: family Parse error 803:1: Can't translate Parse error 806:1: Can't translate Converting yesod-core... done Finished yesod-core Now I'm wondering if I'm missing something, or Hoogle supports only a predefined set of functions. Any advise would be appreciated. -- Ken

2 3

Re: [Haskell-beginners] Stymied by mutable arrays in the ST monad
by Matthew Moppett 25 May '12

25 May '12

Brilliant. I think I've got it now. Thanks heaps, Tobias. On Sat, May 26, 2012 at 4:01 AM, Tobias Brandt <tob.brandt(a)googlemail.com>wrote: > On 25 May 2012 19:43, Matthew Moppett <matthewmoppett(a)gmail.com> wrote: > > About the extra type info needed -- what part of the type "ST s (STArray > s > > Int Int)" is the compiler unable to infer? > > It doesn't know which array type to use, because 'newListArray' is > polymorphic > in the type of array it returns. This type is not mentioned in > the signature of idST because the array is immediately consumed again by > 'getElems'. > > You can try it out in ghci (':t expr' gives you the type of an expression): > > :m +Data.Array.ST > let xs = [1,2,3 :: Int] > > :t xs > [Int] > > :t newListArray (1, length xs) xs > MArray a Int m => m (a Int Int) > > Applying getElems gets you this: > :t (newListArray (1, length xs) xs) >>= getElems > MArray a Int m => m [Int] > > From the 'runST' in your program, the compiler knows that m = ST s, > for some s, but there is nothing constraining 'a' further. > Any 'a' fulfilling the constraint 'MArray a Int (ST s)' will do. > Therefore we have to fix 'a' to some type, e.g. 'STArray s', but > 'STUArray s' would work too, in this case. >

1 0