Why doesn't `iterate` from the Prelude tie the knot?

Question

Why isn't iterate defined like

iterate :: (a -> a) -> a -> [a]
iterate f x = xs where xs = x : map f xs

in the Prelude?

Answer 1

Tying the knot like that doesn't appear to increase sharing.

Contrast with:

cycle xs = let x = xs ++ x in x

Tying the knot here has the effect of creating a circular linked list in memory. x is its own tail. There's a real gain.

Your suggested implementation doesn't increase sharing over the naive implementation. And there's no way for it to do so in the first place - there's no shared structure in something like iterate (+1) 0 anyway.

Answer 2

The Prelude definition, which I include below for clarity, has no overhead needed to call map.

iterate f x =  x : iterate f (f x)

Just for fun, I made a small quick program to test your iterate vs the Prelude's - just to reduce to normal form take 100000000 $ iterate (+1) 0 (this is a list of Ints). I only ran 5 tests, but your version ran for 7.833 (max 7.873 min 7.667) while the Prelude's was at 7.519 (max 7.591 min 7.477). I suspect the time difference is the overhead of map getting called.

Second reason is simply: readability.

Answer 3

There is no knot tying going on in your version, it just maintains a pointer one notch back on the produced list, to find the input value there for the next iteration. This means that each list cell can't be gc-ed until the next cell is produced.

By contrast, the Prelude's version uses iterate's call frame for that, and since it's needed only once, a good compiler could reuse that one frame and mutate the value in it, for more optimized operation overall (and list's cells are independent of each other in that case).