- Haskell-Cafe - Haskell.org

SCC accounting
by Andrew Pimlott 02 Feb '06

02 Feb '06

We've been trying to track down a memory leak, and by adding SCC annotations, pinned it down to a very brief expression. Unfortunately, the expression is just a variable! We even looked at the generated core: (case ([Soutei.Term Logic.BodyVar] -> (...) -> Logic.Frame -> Logic.QState -> FBackTrackT.Stream m_aYsk Logic.QState) lookup_aYPK pred_aXVH ctxIdx_aYpI of wild_B1 { Data.Maybe.Nothing -> GHC.Err.patError ... Data.Maybe.Just x_aXVL -> __scc {pqzifoozq Assertions} x_aXVL }); Note the __scc annotation just before x_aXVL at the end of the expression. Yet in the time and allocation profile, this SCC is charged for a lot of time and allocations in the "individual" column; individual inherited COST CENTRE no. entries %time %alloc %time %alloc pq.foo' 466 50001 8.0 12.1 8.0 13.2 and in the heap profile, it is a major memory leak. The Haskell code looks like predQuery pred = case lookup pred ctxIdx of Just f -> {-# SCC "pq.foo'" #-} f Note that f is a function, which we expect to be expensive when it is called. However, that should be charged to the definition of the function, right? We tried pretty hard to reproduce this in a small test case, but never succeeded. Always, the cost was accounted to the definition of the function in the intuitive way. We're using ghc 6.4.1 and compiling without optimization. Can any ghc hacker suggest how this could happen, or give us any hints on what to try next? Andrew [1] http://haskell.org/ghc/docs/latest/html/users_guide/profiling.html

2 3

unary pattern matching
by John Meacham 01 Feb '06

01 Feb '06

I have often wanted a shorthand syntax for testing if a value matches a given pattern. I want to implement such an extension for jhc but can't decide an appropriate syntax so I thought I'd ask the group. basically I want something like /Left (Just _)/ expands to \x -> case x of Left (Just _) -> True _ -> False so you can do things like when (/Just _/ x) $ putStrLn "x is something" or map /Left (Foo _ 'x')/ xs to get a list of booleans saying whether the xs match or not. however, the '/' syntax clearly doesn't work, nor would anything that conflicts with normal haskell syntax. does anyone have any better ideas? John -- John Meacham - ⑆repetae.net⑆john⑈

7 8

RE: [Haskell-cafe] Known Unknowns
by Simon Peyton-Jones 01 Feb '06

01 Feb '06

| Here's a brief introduction. I intend to write up (on the performance page on | the wiki) a list of things we've done to improve the shootout entries. Yes, do put what you wrote before on the Wiki. (The performance-advice page seems to have vanished but it should be on the user-documentation wiki somewhere. I'm sure we'll find it.) | Multiple calls to sin. Hmm :/ And similar for cos, as well as k*k. Not sure | why GHC isn't removing these (SimonM?), so let's do that by hand GHC doesn't do full CSE. It'd be a relatively easy pass for someone to add, but it can cause space leaks. And it can replace two strictly-evaluated calls with one lazy thunk: let { x = case e of ....; y = case e of .... } in ... ==> let { v = e; x = case v of ...; y = case v of ... } in ... Instead GHC does "opportunistic CSE". If you have let x = e in .... let y = e in .... then it'll discard the duplicate binding. But that's very weak. I've added this to the GHC FAQ Simon

1 0

point-free simplification algoritm.
by Nuno Pinto 31 Jan '06

31 Jan '06

Since it's my first post, hi all! I have been reading this for some days but only now i decided to write something. I am researching a to build a computer assisted simplification algorithm used to simplify pointfree expression.. Example. If i give the program: fst . snd . id . id it will return: fst . snd. it wil also show all steps it made to reach that goal. to do this we must have the laws (such as f. id = f) that help us doing this defined. the program uses a datatype such as: data ExpTree v c = Var v | Term c [ExpTree] exp :: Exp Char PF exp = Term Comp [Term Comp [Term Fst [], Term Comp [Term Snd [], Term Id []]], Term Id []] I have previously defined the catamorphism, hylo and anamorphism for this data type, so recursion is insured. I have also implemented a generic calculador that, given a list of functions will try to aply them and returns the best simplification aswell as the steps made to reach it. I am now trying to implement such functions in a "decent" way, but i am however interested in the theory behind all this. I am looking for algorithms that will help me efficiently simplify the expression to the fullest. I am also interested in knowing what zygomorphisms and paramorphisms are? and how can u build a gcata?? (a cata for all datatypes). I head about "proof-by-exhaustion" and "four color theorem" beeing used to make mathematical proves such as this ones, but i have never seen any example of such and would like to see it, if possible, in haskell.. If anyone can help me find what im looking for, a decent mathematical proofing algoritm.. or just tell me what it is that im looking for :P. or even contribute with any ideas, it would be very much aprecciated. :) TY, and Hi all :D :) and have fun coding haskell :) _________________________________________________________________ Don't just search. Find. Check out the new MSN Search! http://search.msn.click-url.com/go/onm00200636ave/direct/01/

2 1

Correct usage of MonadError, ErrorT?
by Daniel 31 Jan '06

31 Jan '06

Hi, I've got some functions in MonadError with different Error types. I would like to map errors of one Error type onto the other Error type. It seems that the only facility for doing this is mapErrorT, but that seems to force me to work in ErrorT rather than any old instance of MonadError. Am I barking up the wrong tree trying to keep the functions generalised over MonadError? Is there some other paradigm I should use for passing errors across system layers in haskell? I would like to do something like the following, but I don't know how to achieve the 'mapError errMap' part of g. instance Error Int where strMsg s = 0 f :: (MonadError Int m, MonadIO m) => Int -> m String f 0 = do liftIO $ putStrLn "The int is 0, that'll be an error." throwError (-27) f i = do liftIO $ putStrLn ("The int is " ++ show i ++ ", we'll do the division.") return $ show (100 `div` i) g :: (MonadError String m, MonadIO m) => Int -> m String g i = do liftIO $ putStrLn ("Will try to divide by " ++ show i) mapError errMap (f i) h :: (MonadIO m) => Int -> m String h i = (runErrorT (g i)) >>= either (\e -> return ("had an error: " ++ e)) return Thanks Daniel

4 4

RE: [Haskell-cafe] arr f
by Sven Biedermann 30 Jan '06

30 Jan '06

Hello Chris, Many thanks for your input. arr _ = error ... Doesn't work, because it will not be possible to use arrow notation. Today I learned that the function type is abstract and so has no constructor I can pattern match against. I don't know, why. Does something break, if Haskell would offer such a constructor? Since I want to use the arrow notation, I had a close look at the following description, taken from http://www.haskell.org/ghc/docs/latest/html/users_guide/arrow-notation.h tml And revised my problem again (sorry): ------------------------------------------------------------------------ ---- 7.7.1. do-notation for commands Another form of command is a form of do-notation. For example, you can write proc x -> do y <- f -< x+1 g -< 2*y let z = x+y t <- h -< x*z returnA -< t+z You can read this much like ordinary do-notation, but with commands in place of monadic expressions. The first line sends the value of x+1 as an input to the arrow f, and matches its output against y. In the next line, the output is discarded. The arrow returnA is defined in the Control.Arrow module as arr id. The above example is treated as an abbreviation for arr (\ x -> (x, x)) >>> first (arr (\ x -> x+1) >>> f) >>> arr (\ (y, x) -> (y, (x, y))) >>> first (arr (\ y -> 2*y) >>> g) >>> arr snd >>> arr (\ (x, y) -> let z = x+y in ((x, z), z)) >>> first (arr (\ (x, z) -> x*z) >>> h) >>> arr (\ (t, z) -> t+z) >>> returnA Note that variables not used later in the composition are projected out. After simplification using rewrite rules (see Section 7.10, "Rewrite rules ") defined in the Control.Arrow module, this reduces to arr (\ x -> (x+1, x)) >>> first f >>> arr (\ (y, x) -> (2*y, (x, y))) >>> first g >>> arr (\ (_, (x, y)) -> let z = x+y in (x*z, z)) >>> first h >>> arr (\ (t, z) -> t+z) ------------------------------------------------------------------------ --- The arrow I want to create is one to track down dependencies. This doesn't seem to work with arrow notation, because in the example above g -< 2*y isn't used in the following statements but is bound to the next arrow: first g >>> arr (\ (****here==> _ ***, (x, y)) -> let z = x+y in (x*z, z)) >>> So, when tracking down dependencies, the result will depend on g. But it does not! In my eyes, it would be better that the whole proc x delivers an arrow of type a b (c,d) instead of a b c with d being piggy backed from g. So I can see on the wrong type of proc x that I missed out connecting something to some other bits. Another solution would be just to skip g. Can somebody tell me, why the arrow notation is as it is? Greetings Sven -----Original Message----- From: Chris Kuklewicz [mailto:haskell@list.mightyreason.com] Sent: Samstag, 28. Januar 2006 18:01 To: Sven Biedermann Cc: haskell-cafe(a)haskell.org Subject: Re: [Haskell-cafe] arr f Sven Biedermann wrote: > Hello Henrik & Ross, > > Man thanks for your input. I have realised that I should have > explained my problem better. > > So, I try... > > I want to create a datatype like this: > > data D a b = DepVoid (a->b) | -- a = () > DepSingle (a->b) | -- a = a simple ones > DepPair (a->b) | -- a = (c,d) > DepTriple (a->b) | -- a = (c,d,e) > ... > DepFun (a->b) -- a = (c->d) > ... You have a serious typing problem in Haskell with that. Every constructor could be replaced with DepSingle. > Its easy to construct them: > > mkArrVoid :: (() -> c) -> D () c > mkArrVoid f = DepVoid f > > mkArrPair :: ((a,b) -> c) -> D (a,b) c > mkArrPair f = DepPair f > > ... > > Now I want to make D an instance of Arrow: > > instance Arrow (D) where -- my problems stems from > arr f = ??? > > I have no clue to glue the mkArr* functions together to reach what I > want: a different Dep* for different functions f. > What can I pattern match, here? What can I do else? This is not easily fixable, since (arr = DepSingle ) is always a valid choice for the compiler to make. Thus typeclass solutions badly overlap. > > Greetings > > Sven > I can come closer with a GADT. The serious typing problem is still there. So I made arr and pure into error messages. {-# OPTIONS -farrows -fglasgow-exts #-} import Control.Arrow -- GADT style data D x y where DepVoid :: (()->b) -> D () b DepSingle :: (a->b) -> D a b DepPair :: ((a1,a2)->b) -> D (a1,a2) b DepFun :: ( (a1->a2) -> b ) -> D (a1->a2) b -- And these are the constructors, so we could skip them mkArrVoid = DepVoid mkArrSingle = DepSingle mkArrPair = DepPair mkArrFun = DepFun -- The destructor is more annoying (template haskell would help) -- http://haskell.org/hawiki/GADT_20with_20record_20syntax might make this easier getF :: D x y -> (x -> y) getF (DepVoid f) = f getF (DepSingle f) = f getF (DepPair f) = f getF (DepFun f) = f -- This is useful for diagnosing which constructor you have, for testing getF' :: D x y -> Int getF' (DepVoid f) = 1 getF' (DepSingle f) = 2 getF' (DepPair f) = 3 getF' (DepFun f) = 4 instance Arrow D where arr _ = error "Use Dep* instead" -- or arr = DepSingle pure _ = error "Use Dep* instead" -- or pure = DepSingle first arrD = let toPair :: (x->y) -> D (x,d) (y,d) toPair f = DepPair (\(b,d) -> (f b,d) ) in toPair (getF arrD) -- (template haskell would help with defining >>>) (>>>) arr1 arr2 = let comp f = (getF arr2) . f in case arr1 of DepVoid f -> DepVoid (comp f) DepSingle f -> DepSingle (comp f) DepPair f -> DepPair (comp f) DepFun f -> DepFun (comp f) -- This >>> loses the constructor info of arr1 but is simpler (>>>>) arr1 arr2 = DepSingle ( (getF arr2) . (getF arr1) )

2 1

library(s) for numeric constant folding?
by Robert Dockins 29 Jan '06

29 Jan '06

Does anyone know of a good library or libraries which will allow me to perform arithmetic operations on 1) binary integers (signed and unsigned) of various fixed sizes? 2) IEEE 754 floating point numbers (single and double precision). Pure Haskell is preferable, but I'll make do with C bindings. I need to do constant folding for integral and floating point types for a compiler front-end, and I'm hoping that I don't have to write this stuff myself.... Why not just use Float and Double for 2) you ask? Because I need to to EXACTLY IEEE 754 computation, and the Haskell report is pretty dodgy about what implementations are required to provide. Thanks Rob Dockins Speak softly and drive a Sherman tank. Laugh hard; it's a long way to the bank. -- TMBG

1 0

Evaluating arithmetic expressions at run time
by Andrew Savige 29 Jan '06

29 Jan '06

Haskell beginner using GHC. I have a function to do some simple arithmetic at run time: myeval :: Int -> Int -> String -> Int myeval x y "+" = (+) x y myeval x y "-" = (-) x y myeval x y "*" = (*) x y -- ... While that works, I'm curious to know if it can be done more elegantly. I'm thinking of something like: myeval :: Int -> Int -> String -> Int myeval x y op = (read op) x y Thanks, /-\ ____________________________________________________ Do you Yahoo!? Listen to over 20 online radio stations and watch the latest music videos on Yahoo! Music. http://au.launch.yahoo.com

7 10

RE: [Haskell-cafe] arr f
by Sven Biedermann 28 Jan '06

28 Jan '06

Hello Henrik & Ross, Man thanks for your input. I have realised that I should have explained my problem better. So, I try... I want to create a datatype like this: data D a b = DepVoid (a->b) | -- a = () DepSingle (a->b) | -- a = a simple ones DepPair (a->b) | -- a = (c,d) DepTriple (a->b) | -- a = (c,d,e) ... DepFun (a->b) -- a = (c->d) ... Its easy to construct them: mkArrVoid :: (() -> c) -> D () c mkArrVoid f = DepVoid f mkArrPair :: ((a,b) -> c) -> D (a,b) c mkArrPair f = DepPair f ... Now I want to make D an instance of Arrow: instance Arrow (D) where -- my problems stems from arr f = ??? I have no clue to glue the mkArr* functions together to reach what I want: a different Dep* for different functions f. What can I pattern match, here? What can I do else? Greetings Sven -----Original Message----- From: Henrik Nilsson [mailto:nhn@Cs.Nott.AC.UK] Sent: Freitag, 27. Januar 2006 21:46 To: Sven Biedermann Cc: haskell-cafe(a)haskell.org Subject: Re: [Haskell-cafe] arr f Hi Sven, > since this is my first post, > > "Hello all" Welcome! > I have a problem with a function taken from class Arrow. > > arr :: (b -> c) -> a b c > > To build my own arrow, i need to distinguish between different kinds > of b or c. For instance, if b has the form (d,e), i want to construct > something different as when having form (d,e,f). I'm not quite sure I understand what you mean. Are you saying that you you want the input to be either a pair or a triple? Then one possibility would be to wrap up the input in the standard Haskell type "Either". For reference, "Either" is defined like this: data Either a b = Left a | Right b Assume g :: T1 -> T2 -> T h :: T1 -> T2 -> T3 -> T for some specific types T1, T2, T3 and T. Now you can define a function "f": f :: Either (T1,t2) (T1,T2,T3) -> T f (Left (x,y)) = g x y f (Right (x,y,z)) = h x y z Thus "f" "distinguish[es] between different kinds" of input. If it is applied to what essentially is a pair, it will compute a result of type "T" using the function "g", whereas if it is applied to what essentially is a triple it will compute a result using the function "h", again of type "T". Lifting "f" into an arrow yields: arr f :: Arrow a => a (Either (T1,T2) (T1,T2,T3)) T I don't know if that was what you really ment by "construct[ing] something different" depending on the input type? Hope that helps, /Henrik -- Henrik Nilsson School of Computer Science and Information Technology The University of Nottingham nhn(a)cs.nott.ac.uk This message has been checked for viruses but the contents of an attachment may still contain software viruses, which could damage your computer system: you are advised to perform your own checks. Email communications with the University of Nottingham may be monitored as permitted by UK legislation.

2 1

arr f
by Sven Biedermann 27 Jan '06

27 Jan '06

Dear Haskellers, since this is my first post, "Hello all" I have a problem with a function taken from class Arrow. arr :: (b -> c) -> a b c To build my own arrow, i need to distinguish between different kinds of b or c. For instance, if b has the form (d,e), i want to construct something different as when having form (d,e,f). Could I get a hint how to express my needs, please! Many thanks in advance Sven Biedermann

3 2