Haskell List Concatenation vs. (head : tail) format

Question

I always wrote my list-producing recursive functions in this format:

recursiveFunc :: [a] -> [b]
recursiveFunc (x:xs) = [change x] ++ resursiveFunc xs where
    change :: a -> b
    change x = ...

I realize any function like the above could be written for the a -> b case and then simply maped over a set [a], but please take this watered-down situation as an example.

HLint suggests replacing [change x] ++ recursiveFunc xs with change x : recursiveFunc xs.

Is this suggestion purely aesthetic, or is there some effect on how Haskell executes the function?

Answer 1

When using [change x] ++ recursiveFunc xs you create a superfluous one-element list, which is then taken apart by the ++ function. Using : that doesn't happen.

Plus ++ is a function which then will use the : constructor. When you use : directly, there's no need to invoke a function.

So using : is more efficient in theory (the compiler might optimize those differences away, though).

Answer 2

The line

recursiveFunc (x:xs) = [change x] ++ resursiveFunc xs

is a bit confusing since it is not in normalform. That means that ++ can be replaced directly with one right hand side of its definition:

(++) (a:as) bs = a:((++) as bs)
(++) [] bs = bs

-- =>

recursiveFunc (x:xs) = (change x):((++) [] resursiveFunc xs)

-- =>

recursiveFunc (x:xs) = (change x):(resursiveFunc xs)

A Haskell compiler automatically applies such transformation.

But since it is so trivial it makes your code harder to read. One looks at it and asks 'wait ... what?'

Answer 3

The primary advantage is that change x : blah is clearer -- (:) is precisely what you are trying to do (add one element to a list). Why call two functions when one will do?

The suggested way is also marginally more efficient -- your way creates a 1-element list and then throws it away and replaces it with a different list link. The other way just creates one list link. That said, the difference is small enough to be unimportant 99% of the time.