Hi,
Johannes Waldmann wrote:
s2 :: Int - Int
s2 n = sum $ do
x - [ 0 .. n-1 ]
y - [ 0 .. n-1 ]
return $ gcd x y
This code shows some interesting behaviour: its runtime depends heavily
on the allocation area size.
For comparison, with main = print $ s1 1 I
Duncan Coutts duncan.coutts at googlemail.com writes:
This could in principle be fixed with an arity raising transformation,
Do you have a reference to arity raising transformations?
Thanks, Dominic.
___
Haskell-Cafe mailing list
It's described in Andy Gill's PhD thesis (which describes the
foldr/build fusion).
http://ittc.ku.edu/~andygill/paper.php?label=GillPhD96 Section 4.4
describes the basic ideas. There aren't any further details, though.
Max's Strict Core paper also describes it a bit (Section 6):
s1 ~ sum $ map (sum . flip map [0..n] . gcd) [0..n]
s2 ~ sum $ concatMap (flip map [0..n] . gcd) [0..n]
There are some posts from Joachim Breitner investigated fusion for
concatMap:
http://www.haskell.org/pipermail/haskell-cafe/2011-December/thread.html#97227
2012/6/25 Johannes Waldmann
I wonder why this performs really badly, though (I would expect it to be
the same as s2):
s3 :: Int - Int
s3 n = sum [gcd x y | x - [ 0 .. n-1 ], y - [ 0 .. n-1 ]]
From the links posted by Dmitry, it might be that the code generated is
made of 2 recursive calls: in fact, what I observe is a
In my test it works ~20% faster than s2 and ~20% slower than s1.
Did you use -O2 flag?
2012/6/25 Lorenzo Bolla lbo...@gmail.com
I wonder why this performs really badly, though (I would expect it to be
the same as s2):
s3 :: Int - Int
s3 n = sum [gcd x y | x - [ 0 .. n-1 ], y - [ 0 .. n-1 ]]
You are right, probably I didn't because I cannot reproduce it now.
Sorry for the noise.
(Anyway, I am still surprised that list-comprehension gives a different
result from do-notation in the list monad.)
L.
On Mon, Jun 25, 2012 at 11:55 AM, Dmitry Olshansky olshansk...@gmail.comwrote:
In my
On 25 June 2012 02:04, Johannes Waldmann waldm...@imn.htwk-leipzig.de wrote:
Dear all,
while doing some benchmarking (*)
I noticed that function s1 is considerably faster than s2
(but I wanted s2 because it looks more natural)
(for n = 1, s1 takes 20 s, s2 takes 13 s; compiled by
Dear all,
while doing some benchmarking (*)
I noticed that function s1 is considerably faster than s2
(but I wanted s2 because it looks more natural)
(for n = 1, s1 takes 20 s, s2 takes 13 s; compiled by ghc-7.4.2 -O2)
s1 :: Int - Int
s1 n = sum $ do
x - [ 0 .. n-1 ]