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

[Markus Läll]

Hi Viktor

What I think the OP is asking for is a case where the original list would
be returned immediately if the second is empty -- keeping the original
spine. Since that case is missing then the list is pattern-matched and then
reconstructed. Whether this actually happens after compilation is the real
question.

On Mar 4, 2018 21:24, "Viktor Dukhovni" <ietf-dane at dukhovni.org> wrote:



> On Mar 4, 2018, at 4:32 AM, Ben Franksen <ben.franksen at online.de> 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.

_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/haskell-cafe/attachments/20180304/e5e87b9b/attachment.html>