[Haskell-beginners] More than one way to skin a cat question - repeat

[Brent Yorgey]

On Thu, Apr 11, 2013 at 10:53:03AM +0100, Tom Davie wrote:
> 
> On 11 Apr 2013, at 10:47, Benjamin Edwards <edwards.benj at gmail.com> wrote:
> 
> > (:) is O(1), (++) is O(n). Try and implement (++) and it should be easy to see why.
> > 
> (++) is O(n) in the length of it's first argument, which here is a constant 1, so it's O(1).
> 
> That said, the book's implementation is *margionally* better.  The
> implementation using (++) creates the list [x], and then destroys it
> again, and creates another one when it does the append.  The version
> using (:) does not do this.

Note, however, that it's quite likely the compiler will optimize this
away and they will generate identical code.  (Even if it doesn't, this
is hardly worth worrying about.)  That said, the version with (:) is
indeed more idiomatic.

-Brent