February 2007 - Haskell-Cafe

Re: [Haskell-cafe] What inhabits this type: (forall a. a -> b) -> (forall a. m a -> m b)
by Bryan Burgers 28 Feb '07

28 Feb '07

> Since my last query was answered so quickly, let's try another. > > I have looked on Hoogle. I would have asked Djinn, but I don't have it > around. So, can someone find a term that inhabits > (forall a. a -> b) -> (forall a. m a -> m b) > ? I think of this as the type of functions that, given a function from > any boxed-up a to a b, will give me a function from a boxed-up ma to a m > b -- m does not have to be a Monad!. > > Jacques (Jacques, sorry you got this twice--I forgot to send it to the list.) How about this one? f g x = return $ g x Since 'g' can, by definition, take any type and return a 'b', then it should be able to take some 'm a' and return something of type 'b', which we just return. I'm not really familiar with foralls, but the two explicit foralls make the two a's different, right? (After reading the other responses, I must be wrong, but can somebody explain why?) Bryan Burgers

2 1

Re: [Haskell] [Fwd: Re: Computer Language Shootout]
by Claus Reinke 28 Feb '07

28 Feb '07

> I hoped at least to stimulate interest in repeating GP experiment with latest GHC version. until that happens, I'd be wary to draw too many conclusions for today's applications from this paper. two orders of magnitude difference would seem to imply programming problems to me (though the authors did have the problem/ excuse of lack of profiling tools). > (the experiment: > http://www.dcs.ed.ac.uk/home/stg/sfpw/book/Garmendia-Doval/cameraready.ps) not only is it old (ghc-4.08), it doesn't show much code, and what it shows, looks suspiciously like a case of ML-mindset programming in Haskell (the kind that people get help with on the various Haskell lists nearly every day, nowadays). according to 3.5, the Haskell version came first, was used for experiments, and errors in design were corrected, then came the ML version, which was at this point already substantially faster (from which i would be tempted to conclude that the coding style was a better fit for ML than for Haskell; cf also 3.5.1, third para). the ML version was then profiled and improved, after which these improvements were backported from the ML to the Haskell version! okay, profiling was not available for the Haskell version back then, but using ML profiling to improve a Haskell version sounds highly dangerous to me, even more so if the authors do not even mention any awareness of this danger. in 3.5.1, we see Alleles as a BoolVector, which sounds fine until we see it converted to its list of associations, which is then foldl-ed (!) over with a non-strict function (good that those chromosome lengths appear to be only 60..), for every evaluation. this is the main evaluation function for fitness, so it should be very much inner loop, with population sizes and generations ranging to 7500/700 and 50/150000. . of course, the same function in the ML version just means running a loop over a vector, with a strict accumulator.. that is just the code shown in the paper - and it is the only piece of code, apart from structure declarations. perhaps inlining and strictness analysis caught this particular problem, and perhaps calling out to C for random numbers didn't slow down the program, either - the paper just doesn't give enough information to tell. "So far, we have found the Standard ML version to out-perform the Haskell version by over two orders of magnitude. Despite extensive study of the Haskell version, no clear reason has emerged for this poor performance." note that they do not say "any Haskell version would have to be slow because of..", they say they don't know. well, enough of this fud!-) i hope it is fair to say that not just todays compilers are different, but also the user communities. i cannot imagine anyone experiencing this level of performance difference in a concrete application without asking questions about it on one of the Haskell lists, nor would i expect such questions to remain unanswered for long enough to merit a paper (at least not about the question; Data.ByteString shows that there are still papers to be written about answers;-). and if it is too complicated for a public discussion, the project in question could always hire Haskell expertise, in the form of consulting (although i see that most entries have disappeared from the Haskell consultants list, probably because they tend to answer questions for free on the mailing lists?-). claus

2 2

Re: [Haskell] [Fwd: Re: Computer Language Shootout]
by Andrzej Jaworski 28 Feb '07

28 Feb '07

On 2/26/07, Kirsten Chevalier honored me with his attention: >Can you clarify what you mean by this? How do you formally prove that >a programming language (rather than a specific implementation of one) >performs better for a given problem? (..) It is about my saying:"SML was exhaustively proved to predict this logic much better." Formal proof requires a theory. So you might use Copernicus model to formally prove that Australia is on the other side of Earth against Europe. Exhaustive prove might require you to dig a very deep hole in the ground;-) In case of proving softspots of Haskell, a couple of very knowledgeable people here and there dug through exhaustive set of alternatives. That's it. In case of formal proves over programming languages aspirations are limited to program correctness and probably will never address performance. (see http://unit.aist.go.jp/cvs/Agda/) Unfortunately I spend most of my time doing first kind of proofs, I am not sure how it is with you;-) >I've read a few of your posts and I still don't understand what you >mean by a compiler "address[ing] specific properties of a program". >Can you give an example of the kinds of program properties you're >talking about, and explain how C compilers exploit them in a way that >Haskell compilers currently fail to do? My posts were intentionally motivational because I wanted to get feedback on the problem. As to "address[ing] specific properties of a program". In ADP a program deals with DNA and molecular structures. Because the program is a sort of inference engine and simulator at the same time it is desirable to introduce likelihood function as low as possible to avoid blowing up search spaces when everything is constructed and reconstructed at the same time. C is low so that's it. However that is done at a cost - the routines that access the pre-calculated data are no longer identical to those that access the routines that initially calculated the data. In Prolog or Haskell they could remain the same. Have a good time, -Andrzej

1 0

Re: Trouble with record syntax and classes
by Thomas Nelson 28 Feb '07

28 Feb '07

Thank you all for your advice so far. I went back and tried to simplify my code, but I'm still stuck. The basic idea I want is something like an arbitrary tree structure, where MetaSines are the branches containing Sines, and Sines are the leaves containing strings. I want to recurse through the tree and pick up all the leaf strings, but only if that branch/leaf is "on" for that time. Here's my second attempt at the code: data ISine = Sine Integer Integer Integer String | MetaSine Integer Integer Integer [ISine] letter (Sine _ _ _ l) = l sub_sines (MetaSine _ _ _ xs) = xs period p _ _ _ = p offset _ o _ _ = o threshold _ _ t _ = t on :: Integer->ISine->Bool on time (p o t x) = (mod (time-(offset p o t x)) (period p o t x)) < (threshold p o t x) act time (MetaSine p o t s) |on time (p o t s) = foldr (++) (map (act time) (sub_sines p o t s)) |otherwise = [] act time (Sine p o t l) |on time p o t l = [letter p o t l] |otherwise = [] the on, period, offset, and threshold functions should work exactly the same for Sine and MetaSine, so I'd prefer to only write them once. But the act function needs to differentiate: for a Sine, it just returns a singleton list if on is true, or an empty list otherwise; but for a Metasine, it needs to get the list of all the strings in Sine objects in it's sub_sines field. It only does this if it's on. For example, let's say A / | \ B C D / | / | \ E F G H I If A, C, D, E, F and I are all on, only the strings of Sines C and I should be joined to make a to element list. If everything is on, C, E, F, G, H, I will all be joined. Anyway, the above code still doesn't work; there's a parse error for the definition of on. I don't think my arguments are right somehow. I appreciate your collective patience and expertise, and hope you can put me on the right track. Thomas

3 2

Declaring variance of class parameters?
by Jacques Carette 28 Feb '07

28 Feb '07

If I have a class, say class Symantics repr where int:: Int -> repr Int and so on, I would like to *require* that 'repr' be covariant. Is there any way to do that? Jacques

2 1

overlapping instances, selecting if type a does not belong to class?
by Marc Weber 28 Feb '07

28 Feb '07

I want to write a class introducing a function which should append a b resulting in a HList containing a and b (order doesn't matter) So I came up with: ============= code =================================================== class (HList c) => HListAppendArbitrary a b c | a b -> c where hAppendArbitrary :: a -> b -> c -- instance HList + HList (1) instance (HList a, HList b, HAppend a b c, HList c) => HListAppendArbitrary a b c where hAppendArbitrary a b = hAppend a b -- overlapping instance HList + value (2) instance (HList a, HList c) => HListAppendArbitrary a b c where hAppendArbitrary a b = HCons b a ============= error ================================================== hps-lib/HPS/Utils.hs|130| 0: || Duplicate instance declarations: || instance [overlap ok] (HList a, HList b, HAppend a b c, HList c) => || HListAppendArbitrary a b c -- Defined at hps-lib/HPS/Utils.hs|130| 0 || instance [overlap ok] (HList a, HList c) => || HListAppendArbitrary a b c -- Defined at hps-lib/HPS/Utils.hs|134| 0 ============= ======================================================= instance (2) should be used if b does not belong to class HList. Of course there is another opportunity by writing (HCons a x) instead of to force the first type beeing a HList... Which is the topic to read from the ghc/ haskell manual ? Marc Weber

2 3

Re: [Haskell-cafe] Trouble with record syntax and classes
by Andreas Rossberg 27 Feb '07

27 Feb '07

<ajb(a)spamcop.net> wrote: > > When you type "class Foo" in Java or C++, it does three things: > > 1. It declares a new type called "Foo". > > 2. It declares a _set_ of types (i.e. a "class"). > > 3. It declares that the type Foo (and all of its subtypes) is a member > of the set of types Foo. I would add: 4. Define a namespace, also called "Foo", for a set of values (and probably nested classes). > In Haskell, these three operations are distinct. > > 1. You declare a new type using "data" or "newtype". > > 2. You declare a new set of types using "class". > > 3. You declare that a type is a member of a class using "instance". 4. You define a new namespace using "module". Cheers, - Andreas -- Andreas Rossberg, rossberg(a)ps.uni-sb.de

1 0

Re: [Haskell] [Fwd: Re: Computer Language Shootout]
by Fawzi Mohamed 27 Feb '07

27 Feb '07

On Feb 27, 2007, at 3:51 PM, Andrzej Jaworski wrote: > [...] > Nevertheless my point is still valid: when on compiler side the > heap is > stretched and on program side you need Ockham's Razor in action > Haskell > chokes. I hoped at least to stimulate interest in repeating GP > experiment > with latest GHC version. This could make a hot publication and > save nice > people from reappearance of this thread:-) > > (the experiment: > http://www.dcs.ed.ac.uk/home/stg/sfpw/book/Garmendia-Doval/ > cameraready.ps) Thanks for the link! I had not found it. An interesting read. Indeed it would be very interesting to repeat the experiment with the actual GHC... Sincerely Fawzi

1 0

Re: [Haskell] [Fwd: Re: Computer Language Shootout]
by Fawzi Mohamed 27 Feb '07

27 Feb '07

On Feb 27, 2007, at 1:59 PM, Sven Panne wrote: > On Tuesday 27 February 2007 13:44, Andrzej Jaworski wrote: >> I have learned logic from much deeper sources;-) >> My statement was: >> Guys started in Haskell and got to conclusion that for performance >> reasons >> it is better to move to C. The guys know what they are doing. >> >> I hope that helps;-) > > Hmmm, is there any paper/blog/etc. describing exactly what the > performance > problems were? If something is too slow, usually either the language > implementor or the language user can learn something. Furthermore, > when > moving from programming language X to Y and seeing performance > improvements, > it is more often than not the case that the reason for this is not > that Y is > faster than X, but that one has learned a lot about the problem when > implementing in X. So in general you see an improvement even when X > == Y, > i.e. dump your old Haskell code and start from scratch. I could not find references for the other stuff, but for Algebraic Dynamic Programming I found this http://bibiserv.techfak.uni-bielefeld.de/adp/adplit.html and citing my previous message ;) >>> they went from an embedded haskell implementation to a direct >>> compiler implementation. >>> >>> From what I understood I believe that mis-performance in that >>> case came from the embedded nature of the DSL >>> 1) not having a specialized parsing step (making the usage more >>> difficult) >>> 2) no abstract representation of the program that could be >>> optimized with special transformations relative to the DSL >>> 3) not fully optimized kernel methods >>> >>> writing a real compiler for that language made sense, and also >>> the choice of c as language for it, but I think that it would >>> have been possible to write it in haskell without a big >>> performance hit. I haven't seen that haskell compiler >>> significantly worse than others except in really low level >>> computational code, which (with more effort than with C) can be >>> optimized so that it is not really so terribly worse. >>

1 0

Delaling with State StateT and IO in the same function
by Alfonso Acosta 27 Feb '07

27 Feb '07

Hello, I know StateT is exactly aimed at dealing with a state and an inner monad but I have an example in which I have to mix State and IO and in which I didn't get to an elegant solution using StateT. I have a higher order function which gets some State processing functions as input, makes some internal operations with IO and has to return a State as output. My (ugly) function interface is netlist :: DT.Traversable f => (State s (S HDPrimSignal) -> State s v ) -> -- new (State s (Type,v) -> S v -> State s ()) -> -- define State s (f HDPrimSignal) -> -- the graph StateT s IO () The returned type is a StateT and the only way in which I succesfully managed to internally work with both State and StateT is converting from the former to the later one using this function (not elegant at all) state2StateT :: Monad m => State s a -> StateT s m a state2StateT f = StateT (return.runState f) I tried avoiding to use state2StateT by changing the interface to netlist :: DT.Traversable f => (State s (S HDPrimSignal) -> State s v ) -> -- new (State s (Type,v) -> S v -> State s ()) -> -- define State s (f HDPrimSignal) -> -- the graph State s (IO ()) but the function ended up being even uglier and I had to be care full about all the internal IO actions being executed (it is aesy to formget about it), let me show a (quite stupid) example myState :: State () (IO ()) myState = (return $ putStrLn "first line") >> (return $ putStrLn "second line") > eval myState () second line The first line is obviously lost Here is the full code of my function (many type definitions are missing but I hope it is understandable anyway) import qualified Data.Traversable as DT (Traversable(mapM)) import qualified Control.Monad.Trans import Language.Haskell.TH(Type) netlist :: DT.Traversable f => (State s (S HDPrimSignal) -> State s v ) -> -- new (State s (Type,v) -> S v -> State s ()) -> -- define State s (f HDPrimSignal) -> -- the graph StateT s IO () -- Generates a netlist given: -- new: generates the new (and normally unique) tag of every node given -- the iteration state which is updated as well. -- define: given the tag of a node, -- current iteration state, its type, and the tag of its children, -- generates the netlist of that node, updating the iteration state -- pSignals: the graph itself, a traversable collection of root -- signals including the initial state of the iteration -- It returns the final iteration state and the tags of outputs -- (root primitivesignals) netlist new define pSignals = do f <- state2StateT pSignals tab <- lift table let -- gather :: State s HDPrimSignal -> StateT s IO v gather sm = do HDPrimSignal t node <- sm visited <- lift (find tab node) case visited of Just v -> return v Nothing -> do let sP = deref node v' <- state2StateT (new (return sP)) lift (extend tab node v') sV <- DT.mapM (gather.return) sP state2StateT (define (return (t,v')) sV) return v' in DT.mapM (gather.return) f >> return() ---- just in case it helps table :: IO (Table a b) find :: Table a b -> Ref a -> IO (Maybe b) extend :: Table a b -> Ref a -> b -> IO () ---- Maybe is asking too much but would anyone be able to provide a more elegant netlist function which ... option a) returns StateT but doesn't make use of state2StateT? or option b) returns State but doesnt end up being messy? Thanks in advance, Alfonso Acosta

3 5