2

Lets say you've got a list l = [0, 2..] and you want to get the nth 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?

  • 1
    Downvote without a comment. Care to explain? – MartinHaTh May 24 '14 at 8:44
  • 1
    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 May 29 '14 at 14:05
8

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. – MartinHaTh May 24 '14 at 8:59
  • 1
    @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 May 24 '14 at 12:29
  • 1
    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. – MartinHaTh May 24 '14 at 12:41
2

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..]. – MartinHaTh May 24 '14 at 8:50
  • 1
    @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 May 24 '14 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. – MartinHaTh May 24 '14 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 May 24 '14 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! – MartinHaTh May 24 '14 at 13:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.