[Haskell-cafe] What really happens

[Andrew Coppin]

Hi everybody.

Conceptually, all "ordinary" data structures in Haskell are immutable. 
For example, map (2*) takes a list and generates a completely separate, 
*new* list.

And conceptually, SELECT * FROM customer, order WHERE order.cid = 
customer.cid; computes the extended Cartesian product of the two tables 
and then restricts the result according to the predicate. Which is, of 
course, *absurdly* inefficient. However, no sane database engine in 
Creation actually *does* it this way. ;-) It's just that conceptually, 
that's how the result is defined.

Is there any circumstances under which an expression like map (2*) would 
perform an in-place update rather than generating a new list? (Obviously 
this depends on which compiler we're talking about. I'm implicitly 
assuming GHC.) Assuming the old list isn't needed again, an in-place 
update is obviously significantly cheaper. (Less RAM used, less time 
allocating RAM, less GC time, etc.) For something like an integer which 
can be "unboxed", you could write a very tight loop of machine code to 
perform a multiplication by 2 over a single-linked list.


Similarly, according to the rules, something like length . filter odd 
will take a list, generate a new list containing only the odd elements, 
and then proceed to count the size of that list and throw the list 
itself away. I might hope that this would be "optimized" into a tight 
loop of machine code that actually just traverses the original linked 
list and increments a CPU register with the count of odd elements found. 
But is GHC actually that cleaver?


I spend lots of time telling people that Haskell compilers can actually 
make big optimizations like this, and coding my own stuff as if this 
will happen, but is it actually so? Am I assuming the optimizer is 
all-powerful when in fact it's not?

Similarly, I could ask lots of other, related questions to the above. 
(E.g., can all types be optimized like this, or is it only built-in 
lists?) And I know of no way of finding answers, other than pestering 
the people on this mailing list. (Certainly I don't know enough about 
IA32 assembly to take apart the actual compiled code and see what it does.)


Anybody have anything useful to say on the matter?