Subject: Graphical Programming Environments (was: ANNOUNCE: Release of Vit al, an interactive visual programming environment for Haskell) - msg#00089

Previous Message by Date: click to view message preview

RE: Why doesn't GHC do the following optimisation?

It's a while since I paid serious attention to making sure that GHC's transformations are all working right. Things are usually more complicated than one might hope. In this case, * foldl is defined in the prelude using explicit recursion, as it happens * you've defined foldl' using foldr, and that has the potential to do list fusion with the [1..n] * but you've exported sum2, so the inlining doesn't happen. If you keep sum2 private module Main( main ) ... you'll see quite different code * there's an awkwardness with eta-expanding foldl, which I have never fully dealt with -- needs a kind of analysis. It's described in 3.2.3 of Gill's thesis (see also 4.4). http://www.cse.ogi.edu/~andy/ I wish it were all more predictable! Simon | -----Original Message----- | From: haskell-cafe-bounces@xxxxxxxxxxx [mailto:haskell-cafe-bounces@xxxxxxxxxxx] On Behalf Of | andrew cooke | Sent: 12 November 2003 17:40 | To: haskell-cafe@xxxxxxxxxxx | Subject: Why doesn't GHC do the following optimisation? | | | Hi, | | This question is purely out of curiousity - I'm no expert on this. I | wrote the following code: | | sum1 :: [Int] -> Int | sum1 = foldl (+) 0 | | foldl' :: (a -> b -> a) -> a -> [b] -> a | foldl' f v l = foldr (\x -> \fld -> \v' -> fld $ f v' x) id l v | | sum2 :: [Int] -> Int | sum2 = foldl' (+) 0 | | main :: IO () | main = do n <- readLn; | print $ sum1 [1..n]; | print $ sum2 [1..n] | | and ran it through ghc with: ghc Folds.hs -ddump-simpl -O | | I was expecting the two calls to be optimized to something equivalent, or | even for the result of a single calculation to be printed twice. However, | peering at the Core output, it seems that the two sum functions exist | separately and have different structure (sum1 appears to have a simple | recursive definition, while sum2 involves two lamba expressions). | | I did all this because I read a paper introducing folds that showed how | you can express foldl in terms of foldr and giving the derivation. | Unfortunately I don't have the paper/derivation, but I believe my foldl' | is correct (that may be the problem, of course - that sum1 and sum2 are | not equivalent either because of a coding error, or because of some | subtlety in the types, although I carefully gave them explicit types to | try and avoid that). | | The derivation wasn't that complicated (althugh I find it simpler to | simply write the fold down). If it's not an error on my part, why doesn't | ghc do the same kind of transformation itself? Or am mistaken in | thinking that if derivation is easy then the revrese transformation as an | optimisation should also be easy? | | Thanks, | Andrew | | -- | http://www.acooke.org/andrew | _______________________________________________ | Haskell-Cafe mailing list | Haskell-Cafe@xxxxxxxxxxx | http://www.haskell.org/mailman/listinfo/haskell-cafe

Next Message by Date: click to view message preview

Hypothetical reasoning in type classes

Hello, Has anyone thought about adding hereditary Harrop formulas, in other words hypothetical reasoning and universal quantification, to the instance contexts in the Hsakell type class system? Just today (and not only today) I wanted to write instance definitions like instance (forall a. C a => D a) => E [a] where ... This is analogous to wanting to write a rank-2 dictionary constructor (forall a. C a -> D a) -> E [a] at the term level, but with type classes, this dictionary constructor should be applied automatically, in a type-directed fashion, at compile time. The theory behind such instance contexts doesn't seem so intractable; indeed it looks decidable to my cursory examination. The opreational intuition is that we would like the type checker to generate an eigenvariable "a" and perform hypothetical reasoning. I would also like to quantify universally over type classes; in other words, if "?" is the kind of a type class constraint (aka a dictionary type; perhaps "o" would be a better choice of notation), then I would like to define not just types of kind "*->*->?" (aka type classes) or kind "(*->*)->?" (aka constructor classes), but also types of kind "(*->?)->(*->?)". But that's for another day... Ken -- Edit this signature at http://www.digitas.harvard.edu/cgi-bin/ken/sig "Hi, my name is Kent, and I let people change my .sig on the internet." "Hi, Ken!" "Put midgets back in midget porn!" -- Not authorized by Ken Shan. Supported by the association of midget porn workers, Local 9823. signature.asc Description: Digital signature _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@xxxxxxxxxxx http://www.haskell.org/mailman/listinfo/haskell-cafe

Previous Message by Thread: click to view message preview

Programming style (or: too clever by half?)

I just spotted a possible idiom for something that seems to pop up from time to time: foldr const But I can't help feeling that this code is perversely obscure. Does it have any advantages over the more obvious form suggested below? [[ headOrSomething = foldr const headOrSomething1 _ (x:_) = x headOrSomething1 x [] = x h = headOrSomething -- h = headOrSomething1 test1 = h 0 [1,2,3] == 1 test2 = h 0 [] == 0 test3 = h 0 (repeat 42) == 42 ]] This suggests, e.g., an alternative coding of Maybe.listToMaybe: [[ altListToMaybe = foldr (const . Just) Nothing ]] Opinions? #g ------------ Graham Klyne For email: http://www.ninebynine.org/#Contact

Next Message by Thread: click to view message preview

Re: Graphical Programming Environments (was: ANNOUNCE: Release of Vit al, an interactive visual programming environment for Haskell)

W liście z czw, 13-11-2003, godz. 10:34, Markus.Schnell@xxxxxxxxxxxx pisze: > If 'graphical' isn't taken too literally, > you can think of a dialog per function with the possibility to specify > pre and post conditions, tests, comments, etc. I still doubt it would be more convenient. Maybe it's just me, but I prefer to be able to scroll across many function bodies which are grouped and ordered manually, to using a Smalltalk browser where I must click to expand everything and the grouping is dictated by classes the functions operate on and by the environment. An additional "overview" browser showing just headers for quickly locating functions is fine, as long as it doesn't take away the ability to view all the information with minimal navigation (only scrolling) and the ability to use standard text tools on the source (e.g. grep, diff, perl). -- __("< Marcin Kowalczyk \__/ qrczak@xxxxxxxxxx ^^ http://qrnik.knm.org.pl/~qrczak/