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.