On 11 Apr 2013, at 10:47, Benjamin Edwards <edwards.benj@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.

Thanks

Tom Davie