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

Clinton Mead clintonmead at gmail.com
Sun Mar 4 09:42:17 UTC 2018


Adding that case will require one to evaluate the second argument to check
it's empty before allowing one to examine the result.

Consider `x ++
some_list_that_takes_a_long_time_to_produce_its_first_element`.

In this case your proposal will not be an optimisation.

On Sun, Mar 4, 2018 at 8:32 PM, 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/1542e33e/attachment.html>


More information about the Haskell-Cafe mailing list