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

On 6 March 2018 9:25:43 am AEDT, Andrew Martin 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 wrote:

...

...

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

Am 05.03.2018 um 13:40 schrieb Li-yao Xia: 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.