What did I expect?

In my last post, I expressed some disappointment that my version of the map function in F# processed every element of the list.  But why should I be disappointed?  Isn't that exactly what I asked it to do?

Here's why:  In Haskell, I can use my homegrown map function against a huge list, and get the head element of that list, as follows:

head $ map' (^2) [9,19..99999999]

This returns immediately with the answer "81".  If I try something similar in F#, I get a long pause and an out-of-memory exception.

So why doesn't Haskell do exactly what I told it to, and try to process every element of the list?  I've been playing with reproducing the behavior in C#, and here is what I think is going on:

As an imperative programmer, I expect my arrays (or lists, or whatever) to be data structures in memory.  When I try to get the nth element of a list, I expect the machine to start at the head, walk n elements, and then return whatever it finds.  However, in the case of something like [9,19..99999999], that model is pointless.  The reason is that the value I find at the nth element is dependent on n, so it is really more like a function, λ n → 10n + 9.

If we treat this huge list-like thing as a function instead of a data structure, then mapping another function onto it is just a matter of composition.  That's the magic I was hoping to find hidden in the FSharpList class, but I did not find it.

One last critique of the way my F# version of map was compiled:  It compiled into a recursive method, but that will end up using space on the stack every time it is called, and it could have been done more efficiently as a loop.  It is possible that the JIT compiler will resolve this when the procedure is actually rendered into runtime code, but I am not sure about that.