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

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).