[Haskell-cafe] ANN: HLint 1.2

Duncan Coutts duncan.coutts at worc.ox.ac.uk
Mon Jan 12 09:01:53 EST 2009

On Mon, 2009-01-12 at 01:02 +0100, Lennart Augustsson wrote:
> Does GHC specialize map?  If it doesn't, then hand crafted version
> could be faster.

No because the current definition are recursive and ghc cannot inline
recursive functions.

map :: (a -> b) -> [a] -> [b]
map _ []     = []
map f (x:xs) = f x : map f xs

It has to be manually transformed into a version that is not recursive
at the top level:

map :: (a -> b) -> [a] -> [b]
map f = go
    go []     = []
    go (x:xs) = f x : go xs

Then the map can be inlined at the call site and the 'f' inlined into
the body of 'go'.

Obviously this is not quite the same as specialising map since it's per
use not per-function being mapped. Though specialisation would be just:

mapFoo = map foo

I'm not sure if you'd need
{-# NOINLINE mapFoo #-}

This is exactly how the ghc definitions for foldr and foldl work:

foldr k z xs = go xs
               go []     = z
               go (y:ys) = y `k` go ys

foldl f z xs = lgo z xs
                lgo z []     =  z
                lgo z (x:xs) = lgo (f z x) xs


More information about the Haskell-Cafe mailing list