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?
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
