<div dir="ltr"><div dir="auto" style="word-wrap:break-word;line-break:after-white-space">Disclaimer: I am not an expert on fusion.<div><br></div><div>I think it would help you to understand a little bit about how fusion works, since that makes it easier to develop an intuition for what will/won’t get fused. Here’s a crash course: fusion is implemented via <i><a href="https://downloads.haskell.org/ghc/8.8.1/docs/html/users_guide/glasgow_exts.html#rewrite-rules">rewrite rules</a></i>, which are user-defined code transformation rules applied by the GHC optimizer. The essence of list fusion is a single rewrite rule defined in the standard library, which rewrites all expressions of the shape <font face="monospace">foldr k z (build g)</font> to <font face="monospace">g k z</font>, where <font face="monospace">build</font> is a function exported by <font face="monospace">GHC.Exts</font> with the following simple definition:</div><div><br></div></div><blockquote style="margin:0 0 0 40px;border:none;padding:0px"><div dir="auto" style="word-wrap:break-word;line-break:after-white-space"><div><font face="monospace">build g = g (:) []</font></div></div></blockquote><div dir="auto" style="word-wrap:break-word;line-break:after-white-space"><div><br></div><div>How do you get fusion from that? Here’s the trick: fusable functions that consume lists are implemented using <font face="monospace">foldr</font>, while ones that build lists are implemented using <font face="monospace">build</font>. For example, <font face="monospace">sum</font> could be implemented using <font face="monospace">foldr</font> like this:</div><div><br></div></div><blockquote style="margin:0 0 0 40px;border:none;padding:0px"><div dir="auto" style="word-wrap:break-word;line-break:after-white-space"><div><font face="monospace">sum = foldr (+) 0</font></div></div></blockquote><div dir="auto" style="word-wrap:break-word;line-break:after-white-space"><div><br></div><div>…and <font face="monospace">map</font> (which both consumes and builds) could be expressed like this:</div><div><br></div></div><blockquote style="margin:0 0 0 40px;border:none;padding:0px"><div dir="auto" style="word-wrap:break-word;line-break:after-white-space"><div><font face="monospace">map f xs = build (\cons nil -> foldr (\x ys -> f x `cons` ys) nil xs)</font></div></div></blockquote><div dir="auto" style="word-wrap:break-word;line-break:after-white-space"><div><br></div><div>Now if you write <font face="monospace">sum (map f xs)</font>, and <font face="monospace">sum</font> and <font face="monospace">map</font> are both inlined, you’ll get</div><div><br></div></div><blockquote style="margin:0 0 0 40px;border:none;padding:0px"><div dir="auto" style="word-wrap:break-word;line-break:after-white-space"><div><font face="monospace">foldr (+) 0 (build (\cons nil -> foldr (\x ys -> f x `cons` ys) nil xs))</font></div></div></blockquote><div dir="auto" style="word-wrap:break-word;line-break:after-white-space"><div><br></div><div>which matches the rewrite rule from above and gets rewritten into this:</div><div><br></div></div><blockquote style="margin:0 0 0 40px;border:none;padding:0px"><div dir="auto" style="word-wrap:break-word;line-break:after-white-space"><div><font face="monospace">foldr (\x ys -> f x + ys) 0 xs</font></div></div></blockquote><div dir="auto" style="word-wrap:break-word;line-break:after-white-space"><div><br></div><div>Like magic, the intermediate list has disappeared!</div><div><br></div><div>The details are a little more complicated than that in practice, but that’s the core idea. Keeping that context in mind, let me answer some of your questions directly.</div><div><div class="m_-8905346834218773886AppleOriginalContents" style="direction:ltr"><br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex">On Sep 16, 2019, at 21:44, Hilco Wijbenga <<a href="mailto:hilco.wijbenga@gmail.com" target="_blank">hilco.wijbenga@gmail.com</a>> wrote:<br>[To start off, I want to state my, possibly incorrect, understanding<br>of fusion and how it does not (in my expectation) apply to Vector,<br>Set, et cetera. A List can essentially disappear as it's replaced by a<br>loop but a Vector would not: the executing code would create and<br>garbage collect multiple intermediate Vectors before finally returning<br>the end result.]</blockquote><blockquote type="cite"></blockquote><blockquote type="cite"></blockquote><blockquote type="cite"></blockquote><blockquote type="cite"></blockquote><blockquote type="cite"></blockquote><div class="m_-8905346834218773886AppleOriginalContents" style="direction:ltr"><br></div><div class="m_-8905346834218773886AppleOriginalContents" style="direction:ltr">Since fusion is implemented via rewrite rules, which can be defined by anyone, operations on library-defined datatypes <i>can</i> be fused if the library author provides the necessary rewrite rules. Other datatypes use different fusion strategies than the <font face="monospace">foldr</font>/<font face="monospace">build</font> fusion mentioned above, but the core ideas are similar.</div><div class="m_-8905346834218773886AppleOriginalContents" style="direction:ltr"><br></div><div class="m_-8905346834218773886AppleOriginalContents" style="direction:ltr">For the specific two types you mentioned, <font face="monospace">Vector</font> operations <i>do</i> happen to be fused, while <font face="monospace">Set</font> operations are not. <font face="monospace">Set</font> operations are hard to fuse because duplicates need to be removed from the stream, and determining if an element is already in the set fundamentally requires a data structure. You could, however, always convert a set to a list, transform the list with a sequence of fusable operations, and turn it back into a set.</div><br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex">Assume that I need my algorithm to go from initial input to<br>IntermediateResult to subsequent IntermediateResult (a few times) to<br>EndResult. In my case, each subsequent IntermediateResult is a bit<br>smaller than the previous one but that's probably irrelevant.<br></blockquote><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex"> </blockquote><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex">Should I prefer IntermediateResult to be lazy? Should I use [] instead<br>of Vector in the IntermediateResult? What about the functions that<br>actually operate on IntermediateResult, should I prefer to use [] or<br>Vector there? I'm currently able to use Data.Vector.concatMap in some<br>places, is that just as optimized?</blockquote><div><blockquote class="gmail_quote" style="margin:0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);border-right-width:1px;border-right-style:solid;border-right-color:rgb(204,204,204);padding-left:1ex;padding-right:1ex"></blockquote><blockquote class="gmail_quote" style="margin:0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);border-right-width:1px;border-right-style:solid;border-right-color:rgb(204,204,204);padding-left:1ex;padding-right:1ex"></blockquote><blockquote class="gmail_quote" style="margin:0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);border-right-width:1px;border-right-style:solid;border-right-color:rgb(204,204,204);padding-left:1ex;padding-right:1ex"></blockquote><blockquote class="gmail_quote" style="margin:0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);border-right-width:1px;border-right-style:solid;border-right-color:rgb(204,204,204);padding-left:1ex;padding-right:1ex"></blockquote><blockquote class="gmail_quote" style="margin:0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);border-right-width:1px;border-right-style:solid;border-right-color:rgb(204,204,204);padding-left:1ex;padding-right:1ex"></blockquote><blockquote class="gmail_quote" style="margin:0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);border-right-width:1px;border-right-style:solid;border-right-color:rgb(204,204,204);padding-left:1ex;padding-right:1ex"></blockquote><blockquote class="gmail_quote" style="margin:0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);border-right-width:1px;border-right-style:solid;border-right-color:rgb(204,204,204);padding-left:1ex;padding-right:1ex"></blockquote><blockquote class="gmail_quote" style="margin:0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);border-right-width:1px;border-right-style:solid;border-right-color:rgb(204,204,204);padding-left:1ex;padding-right:1ex"></blockquote></div><div class="m_-8905346834218773886AppleOriginalContents" style="direction:ltr"><br></div><div class="m_-8905346834218773886AppleOriginalContents" style="direction:ltr">Remember that fusion is based on rewrite rules, which are fundamentally transformations on the <i>code</i>. Therefore, what matters most is the structure of the code you have written, not what values are flowing around your program at runtime. If a list produced by build ends up being passed to <font face="monospace">foldr</font>, but GHC couldn’t inline definitions enough to see the <i>syntactic</i> pattern <font face="monospace">foldr k z (build g)</font>, then fusion can’t happen.</div><div class="m_-8905346834218773886AppleOriginalContents" style="direction:ltr"><br></div><div class="m_-8905346834218773886AppleOriginalContents" style="direction:ltr">Therefore, if you want fusion to happen, make sure that you use standard list operations to construct or consume lists (e.g. anything in <font face="monospace">Prelude</font> or <font face="monospace">Data.List</font>), not manually-written recursive functions that pattern-match on lists (GHC doesn’t know how to fuse those). Make sure GHC is able to inline things enough it will be able to discover chains of fusable operations. If you’re really worried about it, learn to read the GHC Core that can be dumped by the optimizer; <a href="https://www.stackbuilders.com/tutorials/haskell/ghc-optimization-and-fusion/" target="_blank">this blog post</a> is a good overview of all of these concepts. But your gut is right: you probably just shouldn’t worry about it.</div><br></div><div class="m_-8905346834218773886AppleOriginalContents" style="direction:ltr">Alexis</div><br></div></div></div>