On Fri, 8 Oct 2004, Marcin 'Qrczak' Kowalczyk wrote:
If the representation of some lists was changed, it would complicate all code which works on lists. Or maybe only polymorphic code, but it's still much. I don't believe it would be practical.
That's true in OCaml but not in the STG-machine, where heap objects are accessed through a method-call interface. Adding new representations is easy because the caller doesn't know what the representation is anyway. GHC already uses a special packed representation for static Strings, and I see no reason why the garbage collector couldn't in principle compact lists as it copied them. I don't even see any reason why there couldn't be a packing-aware (++), or a listGetBuf :: [a] -> Int -> (Array Int a, [a]) which noticed when a list was packed and used memcpy() as appropriate. None of these optimizations would complicate or slow down other code which used lists, though they would complicate the run-time system of course. -- Ben