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

[Ben]

On 6 March 2018 9:25:43 am AEDT, Andrew Martin <andrew.thaddeus at gmail.com> wrote:
>Actually, it is likely that neither of the examples you gave will end
>up traversing the spine of the list. The definition of ys would almost
>certainly be inlined, and then the rule would fire.
>
>Sent from my iPhone
>
>> On Mar 5, 2018, at 5:18 PM, Ben Franksen <ben.franksen at online.de>
>wrote:
>> 
>>> Am 05.03.2018 um 13:40 schrieb Li-yao Xia:
>>>> On 03/05/2018 07:13 AM, Ben Franksen wrote:
>>>> Okay, okay, I got it. I did not think about strictness when I
>asked. The
>>>> funny thing is that the two fusion rules combined, as explained by
>>>> Josef, seem to cause this shortcut to be taken. But that can't be
>true
>>>> because (++) really is non-strict, I tested that, with -O2. How do
>you
>>>> explain that?
>>> 
>>> Rewrite rules apply at compile time and don't force any computation.
>>> The second rule fires only if the second argument of (++) is
>>> syntactically []. Otherwise the code doesn't change, and strictness
>is
>>> preserved.
>> 
>> Thanks, yet another thing learned. So
>> 
>>  let ys = [] in xs ++ ys
>> 
>> will traverse the spine of xs but
>> 
>>  xs ++ []
>> 
>> will not. Interesting.
>> 
>> (But who writes something like "xs ++ []" in a real program?)
>> 
>> 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.
>_______________________________________________
>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.

For determining whether xs is traversed, it doesn't really matter whether or not the rule fires and replaces zs = xs ++ ys with just zs = xs. In either case if you traverse the spine of zs to a given depth, it'll force the spine of xs to the same depth. Just having xs ++ ys in the code doesn't traverse the spine of xs, and even evaluating it to WHNF only evaluates xs to the same degree as evaluating xs to WHNF directly.

The question is whether it's allocating a new list spine as it goes on top of evaluating the spine of xs, but there shouldn't be any impact on what is evaluated when.