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

[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])

------------------------------------------------------------
$ for i in 1 2 3 4 5 6; do time ./cycle1 30000000 1000; done;
15015000000

real	0m4.854s
user	0m4.801s
sys	0m0.017s
15015000000

real	0m3.921s
user	0m3.870s
sys	0m0.016s
15015000000

real	0m3.861s
user	0m3.806s
sys	0m0.023s
15015000000

real	0m3.857s
user	0m3.806s
sys	0m0.018s
15015000000

real	0m4.382s
user	0m4.331s
sys	0m0.022s
15015000000

real	0m3.976s
user	0m3.923s
sys	0m0.020s

(3.870 + 3.806 + 3.806 + 4.331 + 3.923) / 5 = 3.9471999999999996

------------------------------------------------------------
$ for i in 1 2 3 4 5 6; do time ./cycle2 30000000 1000; done;
15015000000

real	0m4.675s
user	0m4.629s
sys	0m0.016s
15015000000

real	0m5.076s
user	0m5.024s
sys	0m0.022s
15015000000

real	0m4.735s
user	0m4.687s
sys	0m0.015s
15015000000

real	0m4.727s
user	0m4.676s
sys	0m0.021s
15015000000

real	0m4.677s
user	0m4.632s
sys	0m0.018s
15015000000

real	0m5.023s
user	0m4.971s
sys	0m0.016s

(5.024 + 4.687 + 4.676 + 4.632 + 4.971) / 5 = 4.798

------------------------------------------------------------
$ for i in 1 2 3 4 5 6; do time ./cycle3 30000000 1000; done;
15015000000

real	0m4.150s
user	0m4.102s
sys	0m0.018s
15015000000

real	0m3.823s
user	0m3.784s
sys	0m0.014s
15015000000

real	0m4.918s
user	0m4.863s
sys	0m0.021s
15015000000

real	0m3.807s
user	0m3.769s
sys	0m0.015s
15015000000

real	0m4.129s
user	0m4.082s
sys	0m0.016s
15015000000

real	0m4.420s
user	0m4.366s
sys	0m0.021s

(3.784 + 4.863 + 3.769 + 4.082 + 4.366) / 5 = 4.1728000000000005

------------------------------------------------------------

Summary:

cycle1: 3.94
cycle2: 4.79
cycle3: 4.17

regards,

Bas