[Haskell-cafe] ANN: HLint 1.2

[Duncan Coutts]

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
  where
    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
             where
               go []     = z
               go (y:ys) = y `k` go ys

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

Duncan