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?

Dysteleology

It's worth remembering that your link is GHC's implementation. You could very feasibly write a compiler that implements iterate that way. The people behind GHC simply chose not to. – Vaud

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.

Ashford

Thanks. But there is shared structure in, say, iterate (0:) []. Does this iterate handle this case properly? – Dysteleology

sometimes sharing is not a gain but a loss, when it causes retention of structure in memory which could otherwise be discarded (when there's only one consumer, like e.g. print). if that's the case, recursion is preferable over corecursion. – Oval

@WillNess iterate always produces an infinite list. It's going to always depend on corecursion. – Ashford

@user3237465 Yes, iterate (0:) [] shares tails. That has nothing to do with tying the knot, though. It's just because in iterate f x = x : iterate f (f x), the variable x is shared between the two uses. – Ashford

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

Oval

Answer 3

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.

Counterweight