Re: [Haskell-cafe] missing optimization for (++)

On Mar 4, 2018, at 4:32 AM, Ben Franksen wrote:

I found that in base [1] we have

(++) [] ys = ys (++) (x:xs) ys = x : xs ++ ys

I had expected there to be a clause

(++) xs [] = xs

at the top, which would avoid the list traversal in this common case.

[...]

which still traverses xs even if ys=[].

Any thoughts?

Haskell is lazy, the traversal of x happens only when the combined list is actually traversed, and only for as many elements as requested, so the construction of the concatenated list carries little additional cost. And as pointed out, needlessly forcing the first element of y can have unintended consequences. For example: GHCi, version 8.0.2: http://www.haskell.org/ghc/ :? for help Prelude> let x = [1..] Prelude> let y = [1..] Prelude> let z = x ++ y Prelude> take 20 z [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20] -- Viktor.