<div dir="auto">2 is a bit special. The Semigroup, Monoid, and Num classes define <>, mappend, +, and *. Some instances could surely be more efficient working with larger collections, but 2 can at least get the job done. Defining <*> rather than liftA2 seems to make Applicative *gratuitously* inefficient.</div><div class="gmail_extra"><br><div class="gmail_quote">On Jan 14, 2017 9:58 PM, "David Menendez" <<a href="mailto:dave@zednenem.com">dave@zednenem.com</a>> wrote:<br type="attribution"><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div>Back before Applicative was standardized, I would usually define it using liftA2 instead of <*>, since liftA2 in terms of <*> requires two traversals of a structure, while <*> in terms of liftA2 only needs one.</div><div><br></div><div>As I recall, there was a similar proposal to add liftA2 to Applicative a few years back, and there was an objection that 2 shouldn’t be a special case. It is true that using liftA2 becomes less of an advantage at larger arities.</div><div><br></div><div>Overall, I am weakly in favor.</div><div><br></div>On Sat, Jan 14, 2017 at 4:49 PM, David Feuer <span dir="ltr"><<a href="mailto:david.feuer@gmail.com" target="_blank">david.feuer@gmail.com</a>></span> wrote:<br><div class="gmail_extra"><div class="gmail_quote"><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="auto"><div dir="auto">Right now, we define</div><div dir="auto"><br></div><div dir="auto">liftA2 :: Applicative f</div><div dir="auto">  => (a -> b -> c) -> f a -> f b -> f c<br></div><div dir="auto">liftA2 f x y = f <$> x <*> y</div><div dir="auto"><br></div>For some functors, like IO, this definition is just dandy. But for others, it's not so hot. For ZipList, for example, we get<div dir="auto"><br></div><div dir="auto">liftA2 f (ZipList xs) (ZipList ys) =</div><div dir="auto">  ZipList $ zipWith id (map f xs) ys</div><div dir="auto"><br></div><div dir="auto">In this particular case, rewrite rules will likely save the day, but for many similar types they won't. If we defined a custom liftA2, it would be the obviously-efficient</div><div dir="auto"><br></div><div dir="auto">liftA2 f (ZipList xs) (ZipList ys) =</div><div dir="auto">  ZipList $ zipWith f xs ys</div><div dir="auto"><br></div><div dir="auto">The fmap problem shows up a lot in Traversable instances. Consider a binary leaf tree:</div><div dir="auto"><br></div><div dir="auto">data Tree a = Bin (Tree a) (Tree a) | Leaf a</div><div dir="auto"><br></div><div dir="auto">The obvious way to write the Traversable instance today is</div><div dir="auto"><br></div><div dir="auto">instance Traversable Tree where</div><div dir="auto">  traverse _f Tip = pure Tip</div><div dir="auto">  traverse f (Bin p q) = Bin <$> traverse f p <*> traverse f q</div><div dir="auto"><br></div><div dir="auto">In this definition, every single internal node has an fmap! We could end up allocating a lot more intermediate structure than we need. It's possible to work around this by reassociating. But it's complicated (see Control.Lens.Traversal.confusi<wbr>ng[1]), it's expensive, and it can break things in the presence of infinite structures with lazy applicatives (see Dan Doel's blog post on free monoids[2] for a discussion of a somewhat related issue). With liftA2 as a method, we don't need to reassociate!</div><div dir="auto"><br></div><div dir="auto">traverse f (Bin p q) = liftA2 Bin (traverse f p) (traverse f q)</div><div dir="auto"><br></div><div dir="auto">The complication with Traversable instances boils down to an efficiency asymmetry in <*> association. According to the "composition" law,</div><div dir="auto"><div dir="auto" style="font-family:sans-serif"><br></div><div dir="auto" style="font-family:sans-serif">(.) <$> u <*> v <*> w = u <*> (v <*> w)<br></div><div dir="auto" style="font-family:sans-serif"><br></div><div dir="auto" style="font-family:sans-serif">But the version on the left has an extra fmap, which may not be cheap. With liftA2 in the class, we get a more balanced law:</div><div dir="auto" style="font-family:sans-serif"><br></div><div dir="auto" style="font-family:sans-serif">If for all x and y, p (q x y) = f x . g y, then liftA2 p (liftA2 q u v) = liftA2 f u . liftA2 g v</div><div dir="auto" style="font-family:sans-serif"><br></div></div><div dir="auto"><br></div><div dir="auto">[1] <a href="https://hackage.haskell.org/package/lens-4.15.1/docs/Control-Lens-Traversal.html#g:11" target="_blank">https://hackage.haskell.or<wbr>g/package/lens-4.15.1/docs/Con<wbr>trol-Lens-Traversal.html#g:11</a></div><div dir="auto"><br></div><div dir="auto">[2] <a href="http://comonad.com/reader/2015/free-monoids-in-haskell/" target="_blank">http://comonad.com/reader/<wbr>2015/free-monoids-in-haskell/</a></div></div>
<br>______________________________<wbr>_________________<br>
Libraries mailing list<br>
<a href="mailto:Libraries@haskell.org" target="_blank">Libraries@haskell.org</a><br>
<a href="http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries" rel="noreferrer" target="_blank">http://mail.haskell.org/cgi-bi<wbr>n/mailman/listinfo/libraries</a><br>
<br></blockquote></div><br><br clear="all"><div><br></div>-- <br><div class="m_8477313188498235179gmail_signature" data-smartmail="gmail_signature">Dave Menendez <<a href="mailto:dave@zednenem.com" target="_blank">dave@zednenem.com</a>><br><<a href="http://www.eyrie.org/~zednenem/" target="_blank">http://www.eyrie.org/~<wbr>zednenem/</a>></div>
</div></div>
</blockquote></div></div>