- Haskell-Cafe - Haskell.org

optimization help
by jeff p 18 Oct '06

18 Oct '06

Hello, I have been trying to do some CSV-style processing. My code works fine for small input (up to 10MB), but performs poorly for moderate to large input (it can't seem to finish 100MB of input with 700MB heap space). I have gone through several optimization passes with profiler help, and now I am hoping someone else can point out some other approaches to improving the code's performance (both space and time). The code breaks a large file into smaller files all of whose entries have the same date. thanks, Jeff ------------------------ module Main where import Debug.Trace import Control.Monad import Data.List import qualified Data.ByteString.Lazy.Char8 as B import qualified Data.Map as M import System.Environment (getArgs) dataDir = "dataH/" myRead file = do v <- B.readFile file let (cols' : rows) = map (B.split ',') $ B.lines v let cols = foldl' (\mp (k,v) -> M.insert k v mp) M.empty (zip cols' [0 ..]) return (cols, rows) getColId cols col = M.lookup col cols getCol cols col row = do i <- getColId cols col return $! row!!i dates file nRows = do (cols, rows) <- myRead file let addDate mp row | mp `seq` row `seq` False = undefined | otherwise = do date <- getCol cols (B.pack "\"Date\"") row let old = M.findWithDefault [] date mp return $ M.insert date (row:old) mp res <- foldM addDate M.empty $ take nRows rows mapM_ writeDate $ M.toList res where fmt = B.unpack . B.map (\x -> if x == '-' then '_' else x) . B.takeWhile (/= ' ') writeDate (date,rows) = B.writeFile (dataDir++fmt date) (B.unlines $ map (B.join (B.pack ",")) rows) main = do args <- getArgs case args of ["dates",file,nRows] -> dates file (read nRows)

4 16

Re: Lexically scoped type variables
by apfelmus＠quantentunnel.de 18 Oct '06

18 Oct '06

I think the problem comes from the fact that let (x :: a) = rhs in expr has two interpretations: either the programmer mainly specifies a judgment (\Gamma |- rhs :: a) (f.i. as a guide for type inference) or he just introduces a new variable and sees let as a sugar for (\(x :: a) -> expr) rhs with the viewpoint that the program is a huge expression and all top-level declarations are just (somewhat superflous) lambdas which lead to a final goal. In both cases, one would assume that the main variable binder is our good old lambda. Thus, the (::) in (\(x::a) -> ..) behaves like a constructor and the type variable on the right hand side is just a pattern: f (x :: [a]) = ... is not any different from f (Cons x [a]) = ... When f is applied to an argument, it's the type checker that performs "pattern matching". Of course, one needs nonlinear "type patterns": (f :: a -> b) $ (x :: a) = f x So the type variables in lambdas behaves like normal variables and things like g :: Int -> Int g (x :: a) = x + 1 :: a are entirely fine. All in all, type variables in lambdas are real variables. The first interpretation of let amounts to the Haskell98 intuition: the code x :: a -> a x = rhs means a judgment that x has type (forall . a -> a). This also means that this does not bring any new type variables in scope, only lambdas are capable of introducing new variables. GHC 6.6 rules are not compatible with that. They somehow admit variable bindings by judgments only to discover that this doesn't work for existential types. But note that we have (x :: ...) and (x=...) as separate statements, and we may well keep the second interpretation: f :: Int -> Int (f :: a -> a) = \x -> (x+1 :: a) The intuition is that stand-alone statements (x :: ...) are exactly what they look like: judgments for the type system. The only odd thing about them is that they are stand-alone and do not add to the "main program expression". IMHO, the most natural thing would be that type judgments appear on the rhs of a let or a lambda and that type variable bindings appear on the lhs of a let or a lambda. In the definition of f above, (f :: Int -> Int) and (x+1 :: a) are judgments and (f :: a -> a) is a variable binding. Any confusion between judgment and binding is just like a confusion between constructor application and pattern. Regards, apfelmus

1 0

Re: [Haskell-cafe] Newbie and working with IO Int and Int
by Víctor A. Rodríguez 18 Oct '06

18 Oct '06

> What's wrong with doing it this way? > > -- ** UNTESTED CODE ** > > verifyAdd :: Int -> Int -> Int -> Bool > verifyAdd a b sum | a + b == sum = True > otherwise = False > > testAddMundane :: Int -> Int -> Bool > testAddMundane a b = verifyAdd a b (a + b) > > -- all the IO-dependent stuff is below this line -- > > testAddRandom :: IO Bool > testAddRandom = do a <- randomIO > b <- randomIO > return verifyAdd a b (a + b) > I discovered something worst yet :-P Using the next code and calling verifyAdd or testAddMundane it says : Program error: verifyAdd: ERROR Instead calling testAddRandom only says : :: IO Bool (55 reductions, 92 cells) ---- CODE STARTS HERE, AND IS TESTED ----- import Random verifyAdd :: Int -> Int -> Int -> Bool verifyAdd a b sum = error "verifyAdd: ERROR" testAddMundane :: Int -> Int -> Bool testAddMundane a b = verifyAdd a b (a + b) -- all the IO-dependent stuff is below this line -- testAddRandom :: IO Bool testAddRandom = do a <- randomIO b <- randomIO return ( verifyAdd a b (a+b) ) -- Víctor A. Rodríguez (http://www.bit-man.com.ar) El bit Fantasma (Bit-Man) Perl Mongers Capital Federal (http://cafe.pm.org/) GNU/Linux User Group - FCEyN - UBA (http://glugcen.dc.uba.ar/)

4 4

Re: 6.4 -> 6.6, scoped type variables
by oleg＠pobox.com 18 Oct '06

18 Oct '06

I too miss the old way of handling local type variables. Previously, local type annotations worked a lot like an additional constraint, with type variables denoting some type. The same type variable denoted the same type. Here's how it works in OCaml, for example: # let pair x y = (x,y);; val pair : 'a -> 'b -> 'a * 'b = <fun> # let pair1 (x:'a) (y:'a) = (x,y);; val pair1 : 'a -> 'a -> 'a * 'a = <fun> # let pair2 x y = ((x:'a),(y:'a));; val pair2 : 'a -> 'a -> 'a * 'a = <fun> # let pair3 x (y:int) = ((x:'a),(y:'a));; val pair3 : int -> int -> int * int = <fun> # let pair4 x (y:int) = ((x:'a list),(y:'a));; val pair4 : int list -> int -> int list * int = <fun> # let pair5 (x:'a list) (y:int) = (x,(y:'a));; val pair5 : int list -> int -> int list * int = <fun> Which of the two occurrences of the type variable |'a| a binding one? Who cares... It just works: within the same expression, the same type variable stands for the same type. > I'm looking for some tips and references regarding prescribing > poly-/mono-morphism. I know of three ways to do it: > 1) rely on the monomorphism-restriction -- kind of scary in that its > not explicitly obvious > 2) introducing scoped-type variables of interest -- explicit and modular > 3) introducing all type variables with a forall -- explicit but not modular It seems that with GCH 6.6, we are forced to go back to the fourth method -- the one that was available back in Haskell98. Use useless expressions to hint the typechecker. > bop :: forall x y z m c v . > ( SubType x v, SubType y v, SubType z v > , SubType (Fun m c v) v > , Monad m, Comonad c > ) => (x -> y -> z) -> Fun m c v > bop op = Fun fn > where fn = wrap fn' > where fn' v0 = (inj . Fun) (wrap fn'') > where fn'' v1 = inj (lazyPrj v0 `op` lazyPrj v1) > wrap :: (v -> v) -> (c v -> m v) > wrap = (return .) . (. counit) > If I leave the types to inference (i.e. drop the forall and the type > ascription for |wrap|), then I end up with this type > > bop :: ( SubType x v2, SubType y v1, SubType z v1 > , SubType (Fun m c v1) v2 > , Monad m, Comonad c > ) => (x -> y -> z) -> Fun m c v2 > Note the multiple |v|s; they wreak havoc in the rest of my code. It seems that you wish that, for example, v0 and v1 be of the same type. We have to be direct then and write where fn'' v1 = inj (lazyPrj v0 `op` lazyPrj (v1 `asTypeOf` v0) or where fn'' v1 = inj (lazyPrj v0 `op` lazyPrj v1) where useless = if True then v0 else v1 or where fn'' v1 | const True [v0,v1] = inj (lazyPrj v0 `op` lazyPrj v1) or something similar...

1 0

Type level functions (type of decreasing list)
by Greg Buchholz 18 Oct '06

18 Oct '06

I'm wondering about creating a data structure that has the type of decreasing numbers. If I want an increasing list, it is easy... > {-# OPTIONS -fglasgow-exts #-} > > data Succ a = S a deriving Show > data Zero = Z deriving Show > > data Seq' a = Cons' a (Seq' (Succ a)) | Nil' deriving Show ...which can be used like... > > zero = Z > one = S zero > two = S one > three = S two > > increasing = Cons' zero (Cons' one (Cons' two (Cons' three Nil'))) ...on the other hand, if I want the decreasing list, I can try... > > class Pre a b | a -> b > instance Pre (Succ a) a > instance Pre Zero Zero > > data (Pre a b) => Seq a = Cons a (Seq b) | Nil > > decreasing = Cons three (Cons two (Cons one Nil)) ...but that complains about "Not in scope: type variable `b'". Of course that makes perfect sense, but I'd like to know if there is a Haskell idiom that I'm missing in order to get this to work. Thanks, Greg Buchholz

3 3

Best Introduction To Monads For Newbies (& Especially Imparative Minds) I'v Ever Read!!!
by Kaveh Shahbazian 18 Oct '06

18 Oct '06

This is the best introduction to "Monads" for newbies and imparative mined that I'v ever read! For a long time I was searching for such an excellent text on monads. Ofcourse there are many good text there. But all of them are about mathematics and how clever the monads are. After all most of them are useless for a practical approach. Take a look at this http://sigfpe.blogspot.com/2006/08/you-could-have-invented-monads-and.html !! Have a good time with it!!

1 0

6.4 -> 6.6, scoped type variables, prescribing poly-/mono-morphism
by Nicolas Frisby 17 Oct '06

17 Oct '06

I've been writing some code that relies heavily on the type system. Some of my polymorphic functions end up too polymorphic. I'm looking for some tips and references regarding prescribing poly-/mono-morphism. I know of three ways to do it: 1) rely on the monomorphism-restriction -- kind of scary in that its not explicitly obvious 2) introducing scoped-type variables of interest -- explicit and modular 3) introducing all type variables with a forall -- explicit but not modular The rest of this email is a discussion of a particular problem I'm having. Scoped-type variables worked in 6.4, but no longer in 6.6. I'm sure there's good reasons for this (I think I found a Peyton-Jones message regarding it in 6.4->6.5) I just didn't quite catch on to them. The problem is in the |bop| function: class SubType a v where -- the lack of fundeps is required by design inj :: a -> v lazyPrj :: v -> Maybe a bop :: forall x y z m c v . ( SubType x v, SubType y v, SubType z v , SubType (Fun m c v) v , Monad m, Comonad c ) => (x -> y -> z) -> Fun m c v bop op = Fun fn where fn = wrap fn' where fn' v0 = (inj . Fun) (wrap fn'') where fn'' v1 = inj (lazyPrj v0 `op` lazyPrj v1) wrap :: (v -> v) -> (c v -> m v) wrap = (return .) . (. counit) The explicit forall is needed to introduce the scoped type variables so that I can prescribe the type of |wrap|. After that, the monomorphism restriction on |wrap| takes care of the rest of my worries (that there is only one |m|, only one |c|, and only one |v|). If I leave the types to inference (i.e. drop the forall and the type ascription for |wrap|), then I end up with this type bop :: ( SubType x v2, SubType y v1, SubType z v1 , SubType (Fun m c v1) v2 , Monad m, Comonad c ) => (x -> y -> z) -> Fun m c v2 Note the multiple |v|s; they wreak havoc in the rest of my code. (The monomorphism restriction still takes care of the |m| and |c|.) I'd like to not have to introduce the forall, because with that comes introducing the entire context of the type. Thus I have to maintain any changes to the context, which I would prefer to leave to inference for modularity's sake. In 6.4 I was able to fix this without having to introduce the forall; I could introduce scoped type-variables in patterns to get the job done. That felt a bit like voodoo, especially when trying to get it right for 6.6--which I gave up on doing. I can post the code that works with 6.4 if anyone would like to see it (I just can't find it at the moment). I know there's some work on introducing partial signatures (fun pat | False = ...), but I don't see how to prescribe monomorphism for particular type variables in that way. Any thoughts on how to get the preferred signature using scoped-type variables in 6.6? I'd also welcome any references you might think are relevant. Thanks for your time, Nick

1 0

Re: [Haskell-cafe] Newbie and working with IO Int and Int
by Víctor A. Rodríguez 17 Oct '06

17 Oct '06

Hi, > What's wrong with doing it this way? > > -- ** UNTESTED CODE ** > > verifyAdd :: Int -> Int -> Int -> Bool > verifyAdd a b sum | a + b == sum = True > otherwise = False > > testAddMundane :: Int -> Int -> Bool > testAddMundane a b = verifyAdd a b (a + b) > > -- all the IO-dependent stuff is below this line -- > > testAddRandom :: IO Bool > testAddRandom = do a <- randomIO > b <- randomIO > return verifyAdd a b (a + b) > First "thanks", but the problem is that I can't check if testAddRandom was sucessfull or not. If I replace (a+b) with (a+b-1) it still executes but couldn't check if it's True or False :-P -- Víctor A. Rodríguez (http://www.bit-man.com.ar) El bit Fantasma (Bit-Man) Perl Mongers Capital Federal (http://cafe.pm.org/) GNU/Linux User Group - FCEyN - UBA (http://glugcen.dc.uba.ar/)

1 0

Newbie and working with IO Int and Int
by Víctor A. Rodríguez 17 Oct '06

17 Oct '06

Hi all, I'm really newbie to Haskell, and working on a program I'm trying to make some testing. I make some test on certain know values ( e.g. adding 10 to 15 must return 25) and some test on random values (eg. adding rnd1 to rnd2 must return rnd1+rnd2). The problem that makes me mad is the random number generation. I can obtain random numbers through module Random but all of them return IO Int values (all I need are Ints) instead of Int. I know that I can adjust my own functions to use IO Int instead of Int but the call to certain functions must contain Int parameters, because these ones can't be changed to accept IO Int (I read http://haskell.org/hawiki/ThatAnnoyingIoType and know that can convert from IO Int to Int :-P). How can I deal with this problem ?? Thanks in advance. -- Víctor A. Rodríguez (http://www.bit-man.com.ar) El bit Fantasma (Bit-Man) Perl Mongers Capital Federal (http://cafe.pm.org/) GNU/Linux User Group - FCEyN - UBA (http://glugcen.dc.uba.ar/)

4 3

Error detection in GLR Happy grammar
by Iván Pérez Domínguez 16 Oct '06

16 Oct '06

Hi! I'm trying to detect parse errors in a happy GLR grammar, but I can't! I insert the special "token" 'error', and call the error function when an error is found. However, the program prints no error messages, and simply returns a ParseError at the end. Does any of you have an good example of a GLR parser with error detection and, if possible, error recovery as well?

2 2