GHC's uses a many optimsations and GHC specific techniques (unboxed values, RULES pragmas, and so on) to make the heavily used Prelude code as fast as possible.
There is a lot of magic in PrelBase.lhs -
among other things, the RULES
pragmas implementing the fold/build
optimisation. The code for map is
a good example for how it all works. In the prelude code for version
4.08.1 it reads as follows:
map :: (a -> b) -> [a] -> [b]
map = mapList
-- Note eta expanded
mapFB :: (elt -> lst -> lst) -> (a -> elt) -> a -> lst -> lst
mapFB c f x ys = c (f x) ys
mapList :: (a -> b) -> [a] -> [b]
mapList _ [] = []
mapList f (x:xs) = f x : mapList f xs
{-# RULES
"map" forall f xs. map f xs = build (\c n -> foldr (mapFB c f) n xs)
"mapFB" forall c f g. mapFB (mapFB c f) g = mapFB c (f.g)
"mapList" forall f. foldr (mapFB (:) f) [] = mapList f
#-}
This code is structured as it is, because the "map" rule first
breaks the map open, which exposes it to the various
foldr/build rules, and if no foldr/build rule matches, the "mapList"
rule closes it again in a later phase of optimisation - after
build was inlined. As a consequence, the whole thing depends a bit on
the timing of the various optimsations (the map might be closed again
before any of the foldr/build rules fires). To make the timing
deterministic, build gets a {-# INLINE 2 build
#-} pragma, which delays build's inlining, and thus,
the closing of the map.
Last modified: Wed Aug 8 19:31:18 EST 2001