[Haskell-beginners] Re: folds again -- myCycle

[Daniel Fischer]

Am Sonntag, 15. März 2009 22:14 schrieb Bas van Dijk:
> On Sun, Mar 15, 2009 at 7:35 PM, Will Ness <will_n48 at yahoo.com> wrote:
> > which is then just rewritable as:
> >
> > myCycle xs = ys where ys = foldr (:) ys xs
> >
> > or (arriving at the same result)
> >
> > myCycle xs = foldr (:) (myCycle xs) xs
>
> Note that, because 'ys' only has to be calculated once, GHC makes the
> most efficient code for the former one. In the latter 'myCycle xs' has
> to be calculated each time 'xs' runs empty.
>
> Here are some efficiency tests:
>
> (All programs are compiled with GHC with -O2. I excluded the first run
> of each program because of possible initialisation overhead.)
>
> ------------------------------------------------------------
> module Main where
>
> import System.Environment (getArgs)
>
> myCycle1 xs = ys where ys = foldr (:) ys xs
> myCycle2 xs = foldr (:) (myCycle2 xs) xs
> myCycle3 xs = ys where ys = xs ++ ys
>
> main = do ns:ms:_ <- getArgs
>           print $ sum $ take (read ns) (myCycle1 [1..read ms])
>
> ------------------------------------------------------------
> Summary:
>
> cycle1: 3.94
> cycle2: 4.79
> cycle3: 4.17
>
> regards,
>
> Bas
Somewhat more stable timings on my box. Since it's slower, I did only take 
10000000 instead of 30000000:
myCycle1: myCycle1 xs = ys where ys = foldr (:) ys xs
5005000000

real    0m2.972s
user    0m2.920s
sys     0m0.000s
5005000000

real    0m2.978s
user    0m2.920s
sys     0m0.010s
5005000000

real    0m2.952s
user    0m2.890s
sys     0m0.010s
5005000000

real    0m2.968s
user    0m2.910s
sys     0m0.010s
5005000000

real    0m2.997s
user    0m2.940s
sys     0m0.010s
5005000000

real    0m2.944s
user    0m2.890s
sys     0m0.000s
myCycle2: myCycle2 xs = foldr (:) (myCycle2 xs) xs
5005000000

real    0m4.267s
user    0m4.220s
sys     0m0.000s
5005000000

real    0m4.320s
user    0m4.220s
sys     0m0.000s
5005000000

real    0m4.227s
user    0m4.160s
sys     0m0.020s
5005000000

real    0m4.194s
user    0m4.130s
sys     0m0.010s
5005000000

real    0m4.297s
user    0m4.190s
sys     0m0.010s
5005000000

real    0m4.229s
user    0m4.180s
sys     0m0.000s
myCycle3: myCycle3 xs = ys where ys = xs ++ ys
5005000000

real    0m2.974s
user    0m2.900s
sys     0m0.020s
5005000000

real    0m2.954s
user    0m2.900s
sys     0m0.010s
5005000000

real    0m2.950s
user    0m2.900s
sys     0m0.000s
5005000000

real    0m2.959s
user    0m2.890s
sys     0m0.020s
5005000000

real    0m2.973s
user    0m2.910s
sys     0m0.010s
5005000000

real    0m2.965s
user    0m2.890s
sys     0m0.000s

Summary:
myCycle1: 2.9116s
myCycle2: 4.1833s
myCycle3: 2.8983s