Why isn't Haskell able to optimize infinite lists?

Lets say you've got a list `l = [0, 2..]` and you want to get the `n`th number when `n` is pretty large, say `n=123456789`. So you call `l !! 123456789`. On my machine, this results in `out of memory`.

So why aren't Haskell capable of realizing that the number at index `n` is `2n`, and making a call such as `l !! 1230981237` trivial? Or a more extreme example, `[1..] !! 123456789`. Shouldn't Haskell be able to realize that every number in `[1,1..]` is `1`?

• Downvote without a comment. Care to explain? Commented May 24, 2014 at 8:44
• If you do not maintain a reference to the list somewhere else, the list generated will be garbage-collected while evaluation is taking place and should run in constant memory.
– is7s
Commented May 29, 2014 at 14:05

A sufficiently smart compiler could notice that in those cases. But for nontrivial cases, finding a closed form ranges from hard to open problem to undecidable. A compiler is a compiler, not a mathematician. There is no general procedure for turning the nth element of a sequence into a simple form that doesn't compute the preceding elements, so at best the optimizations would be a bunch of special cases (e.g. for `enumFromThen`, which is what `[0, 2, ..]` desugars to). But there is zero motivation to do that: It's trivial to do by hand, rare in real code, and it's not the sort of pattern that emerges as a result of other optimizations. If you want the nth even number fast, write `2 * n`. `evens !! n` might be cute but it's not worth a rewrite rule to make fast.

• Really? GHC didn't want me to create an infinite non-arithmetic sequence - and arithmetic sequences should be trivial to simplify? I understand this could be challenging if you don't know step at compile time, but surely GHC could handle? I don't think that the fact that it's easy to avoid this problem, nor that it is rare in 'real' code is a good argument against such an optimization, though I do understand that it would be low priority for the devs. Commented May 24, 2014 at 8:59
• @MartinHaTh For the case of `enumFromThen a b` with variable a, b, it's easy (`a + (b-a)*n` or something). But this is a special case that has to be devised by humans and implemented specifically, and it could takes some care to apply (it must fire before `enumFromThen` is inlined). All such transformations take time to implement, make compilation ever so slightly slower, result in code that has to be maintained. An optimization that adds no value has negative value because of these costs.
– user7043
Commented May 24, 2014 at 12:29
• I wouldn't say it didn't add any value (as it specifically solves my 'problem'), and it could be only used with the `-O` flag (which kind of makes sense). I do see your point, though. Commented May 24, 2014 at 12:41

Part of the job of programming is recognizing when you have added a complication that doesn't need to exist, and removing it.

In this case, what you're doing is finding the 123456789th entry in a list where the nth entry is 2*n. Constructing the list in the first place is extra work, which we should decline to do.

It wouldn't be hard for Haskell compiler writers to add an optimization that would detect such a potential improvement, but if it were added, would it ever get used on code not written specifically to point it out? I doubt it. The cases you point out would all be obvious to the programmer -- so obvious that they wouldn't ever get written in the first place.

Compilers are computer programs, they don't "realize" anything. Realizing is something humans do.

(Nitpick: not every element in `[1..]` is 1)

• You could use the 'obvious' argument against unused variables - yet gcc and clang screams in your face if you so such a thing. Oh, I meant `[1,1..]`. Commented May 24, 2014 at 8:50
• @MartinHaTh Warnings about unused variables exist because experience shows that people do that unintentionally and that it indicates bugs or poor code quality. Detecting unused variables (a subset of dead code elimination) is a useful optimization, partly because it cleans up the code after other optimizations have made the variable redundant (e.g. by replacing its use with its known-constant value).
– user7043
Commented May 24, 2014 at 12:32
• @delnan The same way developers could mistakenly think that getting a large index of an infinite list with an obvious pattern is a trivial operation, when it in fact is not. Commented May 24, 2014 at 13:00
• @MartinHaTh Unused variables aren't due to misconceptions of developers, they're mistakes that happen while coding. Any Haskell programmer (actually any programmer) worth their salt knows that linked lists need linear time for indexed access, and that compiler optimizations isn't magical fairy dust. There are certainly people who don't yet know that, but since we can't possibly optimize every (or even most) infinite list with an "obvious" pattern, we're doing these people a disservice by not correcting their misconception early and consistently.
– user7043
Commented May 24, 2014 at 13:05
• @delnan But how would anyone know that the list is implemented as a linked list? That certainly isn't obvious. It seems to me that when getting a indexed element from a generic list you would expect something close to constant runtime. I am not talking about reducing every single list to a constant expression, but when creating an infinite arithmetic list as in my question you would expect that retrieving the element of a high index isn't going to take much time, but it does! Commented May 24, 2014 at 13:12