Always check optimizations to make sure they are not pessimizations!
Actually, traversing the list twice is very cheap compared to space
leakage, and accumulating pairs requires tuple boxing and unboxing which
I don't know how to get GHC not to do.
Your avg3 (along with several attempts of mine to fix the problem) gave
stack overflows on a large list.
Only avg4 below (traversing the list twice with strict accumulation)
didn't blow up on large lists, even though avg5 and avg6 were intended
to be strict.
Prelude Control.Arrow Data.List>
let avg4 = uncurry (/) . (foldl' (+) 0 &&& foldl' (\x y -> x + 1) 0)
in avg4 [1..10000000]
5000000.5
-- This took 13 sec on my machine
Prelude Control.Arrow Data.List> let avg3 = uncurry (/) . foldr (\x
(s,n) -> (s + x,n + 1)) (0,0) in avg3 [1..10000000]
*** Exception: stack overflow
-- This fails in 1 sec
Prelude Control.Arrow Data.List>
let avg5 = uncurry (/) . foldl' (\(s,n) x -> (s + x,n + 1)) (0,0)
in avg5 [1..10000000]
*** Exception: stack overflow
-- This fails in 100 sec
Prelude Control.Arrow Data.List>
let avg6 = uncurry (/) . foldl' (\sn x -> (fst sn+x,snd sn+1)) (0,0)
in avg6 [1..10000000]
*** Exception: stack overflow
-- This fails in 30 sec
Prelude Control.Arrow Data.List>
let avg3 = uncurry (/) . foldr (\n -> (+n) *** (+1)) (0, 0)
in avg3 [1..10000000]
*** Exception: stack overflow
-- This fails in 2 sec
Tim Newsham wrote:
Just goofing around with arrows and foldr while reading Hutton's
excellent paper on folds (http://www.cs.nott.ac.uk/~gmh/fold.pdf).
Wondering if this can be done automatically and more generally?
module Main where
import Control.Arrow
import Data.List
-- sum and length expressed as foldr.
fsum = foldr (\n -> (+n)) 0
flen = foldr (\n -> (+1)) 0
-- compute average using arrows..
-- compute the sum of a list, compute the length, and do a divide.
-- this traverses the list twice using two foldrs.
avg1 = uncurry (/) . (fsum &&& flen)
avg2 = uncurry (/) . (foldr (\n -> (+n)) 0 &&& foldr (\n -> (+1)) 0)
-- But the two foldr's can be fused together
-- here we're mixing the two foldr constants 0 and 0 to (0,0)
-- and we're mixing the two functions (\n -> (+n)) and
-- (\n -> (+1)) to (\n -> (+n) *** (+1)).
avg3 = uncurry (/) . foldr (\n -> (+n) *** (+1)) (0, 0)
main = do
print $ avg1 [1,2,3,4]
print $ avg2 [1,2,3,4]
print $ avg3 [1,2,3,4]
Tim Newsham
http://www.thenewsh.com/~newsham/
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
