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

[michael rice]

Hi Dan,

I wasn't aware of the third option, at least this particular variant of the *as* pattern. I've only seen it like this

 f s@(x:xs)  = ...

 i.e., outside the parens.

The cost question arose as I was deciding which way to write it.

Thanks,

Michael

--- On Fri, 9/10/10, Dan Doel <dan.doel at gmail.com> wrote:

From: Dan Doel <dan.doel at gmail.com>
Subject: Re: [Haskell-cafe] Cost: (:) vs head
To: haskell-cafe at haskell.org
Cc: "michael rice" <nowgate at yahoo.com>
Date: Friday, September 10, 2010, 11:29 PM

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



      
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20100911/0e7ff3ca/attachment.html