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

[Will Ness]

Bas van Dijk <v.dijk.bas <at> gmail.com> writes:

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

So you've discovered an inefficiency in GHC, which should probably improve on 
its deforestation skills. :)

"Smart" compiler would NOT allocate any extra storage in the three cases above, 
only altering the access to it. The meaning of all the three is the same - they 
are all rewritable one into another - it's a loop around on access past end.

The "very bright" compiler would just translate 

sum $ take 30000000 [1..1000]

into

sum [1..1000]*30000

producing the same result:

Prelude> sum [1..1000]*30000
15015000000


Cheers,