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

[Josef Svenningsson]

The rule "foldr/id" will replace 'foldr (:) [] xs' with 'xs'.

Cheers,

Josef

On Sun, Mar 4, 2018 at 10:34 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.
>
> Is this somehow magically taken care of by the
>
> {-# RULES
> "++"    [~1] forall xs ys. xs ++ ys = augment (\c n -> foldr c n xs) ys
>   #-}
>
> ? No, inlining @augment g xs = g (:) xs@ gives me
>
> (\c n -> foldr c n xs) (:) ys
>
> = foldr (:) ys xs
>
> which still traverses xs even if ys=[].
>
> Any thoughts?
>
> [1]
>
> http://hackage.haskell.org/package/base-4.10.1.0/docs/src/GHC.Base.html#%2B%2B
>
> Cheers
> Ben
>
> _______________________________________________
> 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/f1576807/attachment.html>