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

On 11 Apr 2013, at 10:47, Benjamin Edwards 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. Thanks Tom Davie