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

Am Sonntag, 15. März 2009 22:14 schrieb Bas van Dijk:

On Sun, Mar 15, 2009 at 7:35 PM, Will Ness 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