<table cellspacing="0" cellpadding="0" border="0" ><tr><td valign="top" style="font: inherit;">Hi Baz,<br><br>That's quite an analysis, one I'll keep for future reference.<br><br>So, my original coding was the fastest. Guess I should stop second guessing myself. ;-)<br><br>Michael <br><br>--- On <b>Sat, 9/11/10, Bas van Dijk <i>&lt;v.dijk.bas@gmail.com&gt;</i></b> wrote:<br><blockquote style="border-left: 2px solid rgb(16, 16, 255); margin-left: 5px; padding-left: 5px;"><br>From: Bas van Dijk &lt;v.dijk.bas@gmail.com&gt;<br>Subject: Re: [Haskell-cafe] Cost: (:) vs head<br>To: "michael rice" &lt;nowgate@yahoo.com&gt;<br>Cc: haskell-cafe@haskell.org<br>Date: Saturday, September 11, 2010, 8:46 AM<br><br><div class="plainMail">On Sat, Sep 11, 2010 at 5:13 AM, michael rice &lt;<a ymailto="mailto:nowgate@yahoo.com" href="/mc/compose?to=nowgate@yahoo.com">nowgate@yahoo.com</a>&gt; wrote:<br>&gt;<br>&gt; Which of these would be more costly for a long
 list?<br>&gt;<br>&gt; f :: [Int] -&gt; [Int]<br>&gt; f [x] = [x]<br>&gt; f (x:xs) = x + (head xs) : f xs<br>&gt;<br>&gt; f :: [Int] -&gt; [Int]<br>&gt; f [x] = [x]<br>&gt; f (x:y:xs) = x + y : f (y:xs)<br><br>Use Criterion[1] to find out:<br><br><br>module Main where<br><br>import Criterion.Main<br><br>f1, f2, f3, f4 :: [Int] -&gt; [Int]<br><br>f1 [x] = [x]<br>f1 (x:xs) = x + head xs : f1 xs<br><br>f2 [x] = [x]<br>f2 (x:y:xs) = x + y : f2 (y:xs)<br><br>f3 [x] = [x]<br>f3 (x:xs@(y:_)) = x + y : f3 xs<br><br>f4 [x] = [x]<br>f4 (x:y:xs) = x + y : go y xs<br>&nbsp; &nbsp; where<br>&nbsp; &nbsp; &nbsp; go x []&nbsp; &nbsp;&nbsp;&nbsp;= [x]<br>&nbsp; &nbsp; &nbsp; go x (y:xs) = x + y : go y xs<br><br>benchMark s f = bench s $ whnf (\n -&gt; sum $ f [1..n]) 1000000<br><br>main = defaultMain [ benchMark "f1" f1<br>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;&nbsp;&nbsp;, benchMark "f2" f2<br>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;
 &nbsp; &nbsp;&nbsp;&nbsp;, benchMark "f3" f3<br>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;&nbsp;&nbsp;, benchMark "f4" f4<br>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;&nbsp;&nbsp;]<br><br><br>now compile and run it:<br><br>$ ghc --make Benchmark.hs -O2 -o benchmark<br>...<br>$ ./benchmark<br>warming up<br>estimating clock resolution...<br>mean is 24.29944 us (40001 iterations)<br>found 1405 outliers among 39999 samples (3.5%)<br>&nbsp; 721 (1.8%) high mild<br>&nbsp; 684 (1.7%) high severe<br>estimating cost of a clock call...<br>mean is 1.844233 us (45 iterations)<br>found 2 outliers among 45 samples (4.4%)<br>&nbsp; 2 (4.4%) high severe<br><br>benchmarking f1<br>collecting 100 samples, 1 iterations each, in estimated 7.917595 s<br>bootstrapping with 100000 resamples<br>mean: 80.04258 ms, lb 79.85129 ms, ub 80.24094 ms, ci 0.950<br>std dev: 1.000711 ms, lb 878.8460 us, ub 1.179558 ms, ci 0.950<br>found 1 outliers
 among 100 samples (1.0%)<br>variance introduced by outliers: 0.990%<br>variance is unaffected by outliers<br><br>benchmarking f2<br>collecting 100 samples, 1 iterations each, in estimated 8.171391 s<br>bootstrapping with 100000 resamples<br>mean: 83.13315 ms, lb 82.93615 ms, ub 83.33348 ms, ci 0.950<br>std dev: 1.017999 ms, lb 904.5153 us, ub 1.174008 ms, ci 0.950<br>variance introduced by outliers: 0.990%<br>variance is unaffected by outliers<br><br>benchmarking f3<br>collecting 100 samples, 1 iterations each, in estimated 8.297014 s<br>bootstrapping with 100000 resamples<br>mean: 82.66586 ms, lb 82.34780 ms, ub 83.39774 ms, ci 0.950<br>std dev: 2.339937 ms, lb 976.2940 us, ub 4.133495 ms, ci 0.950<br>found 9 outliers among 100 samples (9.0%)<br>&nbsp; 7 (7.0%) high mild<br>&nbsp; 2 (2.0%) high severe<br>variance introduced by outliers: 0.998%<br>variance is unaffected by outliers<br><br>benchmarking f4<br>collecting 100 samples, 1 iterations each, in
 estimated 8.080888 s<br>bootstrapping with 100000 resamples<br>mean: 80.80089 ms, lb 80.61719 ms, ub 80.99542 ms, ci 0.950<br>std dev: 968.1706 us, lb 872.7758 us, ub 1.097217 ms, ci 0.950<br>variance introduced by outliers: 0.990%<br>variance is unaffected by outliers<br><br><br>So to summarize from fastest to slowest:<br><br>f1: mean: 80.04258 ms<br>f4: mean: 80.80089 ms<br>f3: mean: 82.66586 ms<br>f2: mean: 83.13315 ms<br><br><br>To find out why f1 is the fastest you can look at the core using ghc-core[2]:<br><br>$ ghc-core -- -O2 Benchmark.hs<br><br>f1 :: [Int] -&gt; [Int]<br>GblId<br><br>f1 =<br>&nbsp; \ (ds_d1h0 :: [Int]) -&gt;<br>&nbsp; &nbsp; case ds_d1h0 of _ {<br>&nbsp; &nbsp; &nbsp; [] -&gt; f11;<br>&nbsp; &nbsp; &nbsp; : x_a12V ds1_d1h1 -&gt;<br>&nbsp; &nbsp; &nbsp; &nbsp; case ds1_d1h1 of _ {<br>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; [] -&gt;<br>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; : @ Int x_a12V ([] @ Int);<br>&nbsp; &nbsp; &nbsp; &nbsp;
 &nbsp; : ipv_s1hv ipv1_s1hw -&gt;<br>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; :<br>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; @ Int<br>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; (case x_a12V of _ { I# x1_a1k6 -&gt;<br>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;&nbsp;&nbsp;case ipv_s1hv of _ { I# y_a1ka -&gt;<br>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;&nbsp;&nbsp;I# (+# x1_a1k6 y_a1ka)<br>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;&nbsp;&nbsp;}<br>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;&nbsp;&nbsp;})<br>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; (f1_$sf1 ipv1_s1hw ipv_s1hv)<br>&nbsp; &nbsp; &nbsp; &nbsp; }<br>&nbsp; &nbsp; }<br><br>f1_$sf1 :: [Int] -&gt; Int -&gt; [Int]<br>GblId<br><br>f1_$sf1 =<br>&nbsp; \ (sc_s1FL :: [Int]) (sc1_s1FM :: Int) -&gt;<br>&nbsp; &nbsp; case sc_s1FL of _ {<br>&nbsp; &nbsp; &nbsp; [] -&gt;<br>&nbsp; &nbsp; &nbsp; &nbsp; :<br>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; @ Int sc1_s1FM ([] @
 Int);<br>&nbsp; &nbsp; &nbsp; : ipv_s1hv ipv1_s1hw -&gt;<br>&nbsp; &nbsp; &nbsp; &nbsp; :<br>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; @ Int<br>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; (case sc1_s1FM of _ { I# x_a1k6 -&gt;<br>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;&nbsp;&nbsp;case ipv_s1hv of _ { I# y_a1ka -&gt;<br>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;&nbsp;&nbsp;I# (+# x_a1k6 y_a1ka)<br>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;&nbsp;&nbsp;}<br>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;&nbsp;&nbsp;})<br>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; (f1_$sf1 ipv1_s1hw ipv_s1hv)<br>&nbsp; &nbsp; }<br><br><br>f4 :: [Int] -&gt; [Int]<br>GblId<br><br>f4 =<br>&nbsp; \ (ds_d1gl :: [Int]) -&gt;<br>&nbsp; &nbsp; case ds_d1gl of _ {<br>&nbsp; &nbsp; &nbsp; [] -&gt; f41;<br>&nbsp; &nbsp; &nbsp; : x_a13f ds1_d1gm -&gt;<br>&nbsp; &nbsp; &nbsp; &nbsp; case ds1_d1gm of _ {<br>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; [] -&gt;<br>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; : @ Int x_a13f ([] @ Int);<br>&nbsp; &nbsp; &nbsp;
 &nbsp; &nbsp; : y_a13h xs_a13i -&gt;<br>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; :<br>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; @ Int<br>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; (plusInt x_a13f y_a13h)<br>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; (f4_go y_a13h xs_a13i)<br>&nbsp; &nbsp; &nbsp; &nbsp; }<br>&nbsp; &nbsp; }<br><br>f4_go =<br>&nbsp; \ (x_a13k :: Int) (ds_d1gu :: [Int]) -&gt;<br>&nbsp; &nbsp; case ds_d1gu of _ {<br>&nbsp; &nbsp; &nbsp; [] -&gt;<br>&nbsp; &nbsp; &nbsp; &nbsp; : @ Int x_a13k ([] @ Int);<br>&nbsp; &nbsp; &nbsp; : y_a13m xs_a13n -&gt;<br>&nbsp; &nbsp; &nbsp; &nbsp; :<br>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; @ Int<br>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; (plusInt x_a13k y_a13m)<br>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; (f4_go y_a13m xs_a13n)<br>&nbsp; &nbsp; }<br><br><br>f3 :: [Int] -&gt; [Int]<br>GblId<br><br>f3 =<br>&nbsp; \ (ds_d1gD :: [Int]) -&gt;<br>&nbsp; &nbsp; case ds_d1gD of _ {<br>&nbsp; &nbsp; &nbsp; []
 -&gt; f31;<br>&nbsp; &nbsp; &nbsp; : x_a13b ds1_d1gE -&gt;<br>&nbsp; &nbsp; &nbsp; &nbsp; case ds1_d1gE of _ {<br>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; [] -&gt;<br>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; : @ Int x_a13b ([] @ Int);<br>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; : y_a13e ds2_d1gF -&gt;<br>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; :<br>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; @ Int<br>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; (plusInt x_a13b y_a13e)<br>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; (f3_$sf3 ds2_d1gF y_a13e)<br>&nbsp; &nbsp; &nbsp; &nbsp; }<br>&nbsp; &nbsp; }<br><br>f3_$sf3 :: [Int] -&gt; Int -&gt; [Int]<br>GblId<br><br>f3_$sf3 =<br>&nbsp; \ (sc_s1G3 :: [Int]) (sc1_s1G4 :: Int) -&gt;<br>&nbsp; &nbsp; case sc_s1G3 of _ {<br>&nbsp; &nbsp; &nbsp; [] -&gt;<br>&nbsp; &nbsp; &nbsp; &nbsp; :<br>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; @ Int sc1_s1G4 ([] @ Int);<br>&nbsp; &nbsp; &nbsp; : y_a13e ds_d1gF -&gt;<br>&nbsp; &nbsp;
 &nbsp; &nbsp; :<br>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; @ Int<br>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; (plusInt sc1_s1G4 y_a13e)<br>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; (f3_$sf3 ds_d1gF y_a13e)<br>&nbsp; &nbsp; }<br><br>f2 :: [Int] -&gt; [Int]<br>GblId<br><br>f2 =<br>&nbsp; \ (ds_d1gP :: [Int]) -&gt;<br>&nbsp; &nbsp; case ds_d1gP of _ {<br>&nbsp; &nbsp; &nbsp; [] -&gt; f21;<br>&nbsp; &nbsp; &nbsp; : x_a137 ds1_d1gQ -&gt;<br>&nbsp; &nbsp; &nbsp; &nbsp; case ds1_d1gQ of _ {<br>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; [] -&gt;<br>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; : @ Int x_a137 ([] @ Int);<br>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; : y_a139 xs_a13a -&gt;<br>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; :<br>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; @ Int<br>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; (plusInt x_a137 y_a139)<br>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; (f2_$sf2 xs_a13a y_a139)<br>&nbsp; &nbsp; &nbsp; &nbsp; }<br>&nbsp; &nbsp;
 }<br><br>f2_$sf2 :: [Int] -&gt; Int -&gt; [Int]<br>GblId<br><br>f2_$sf2 =<br>&nbsp; \ (sc_s1FU :: [Int]) (sc1_s1FV :: Int) -&gt;<br>&nbsp; &nbsp; case sc_s1FU of _ {<br>&nbsp; &nbsp; &nbsp; [] -&gt;<br>&nbsp; &nbsp; &nbsp; &nbsp; :<br>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; @ Int sc1_s1FV ([] @ Int);<br>&nbsp; &nbsp; &nbsp; : y_a139 xs_a13a -&gt;<br>&nbsp; &nbsp; &nbsp; &nbsp; :<br>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; @ Int<br>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; (plusInt sc1_s1FV y_a139)<br>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; (f2_$sf2 xs_a13a y_a139)<br>&nbsp; &nbsp; }<br><br>The reason that f1 is faster than the rest is that GHC is somehow able<br>to unpack the Ints and use the more efficient +# instead of the slower<br>plusInt.<br><br>I don't immediately see the reason for the time difference between f4,<br>f3 and f2. The inner loops all seem equivalent.<br><br>Regards,<br><br>Bas<br><br>[1] <a href="http://hackage.haskell.org/package/criterion"
 target="_blank">http://hackage.haskell.org/package/criterion</a><br>[2] <a href="http://hackage.haskell.org/package/ghc-core" target="_blank">http://hackage.haskell.org/package/ghc-core</a><br></div></blockquote></td></tr></table><br>