On Thu, Apr 11, 2013 at 10:53:03AM +0100, Tom Davie wrote:

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.

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