[Haskell-cafe] Cost: (:) vs head

[Dan Doel]

On Friday 10 September 2010 11:13:50 pm michael rice wrote:
> Which of these would be more costly for a long list?
> 
> f :: [Int] -> [Int]
> f [x] = [x]
> f (x:xs) = x + (head xs) : f xs
> 
> f :: [Int] -> [Int]
> 
> f [x] = [x]
> f (x:y:xs) = x + y : f (y:xs)

Another option would be:

  f [x] = [x]
  f (x:xs@(y:_)) = (x + y) : f xs

However, I believe I've done tests in the past, and your second example 
generates the same code when optimizations are on (that is, it doesn't build a 
new y:xs, but reuses the existing one), and that should perform the same as 
your first implementation.

All that said, I'm not sure you'd be able to see the difference anyway.

-- Dan