Right now, we define liftA2 :: Applicative f => (a -> b -> c) -> f a -> f b -> f c liftA2 f x y = f <$> x <*> y liftA2 f (ZipList xs) (ZipList ys) = ZipList $ zipWith id (map f xs) ys 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 liftA2 f (ZipList xs) (ZipList ys) = ZipList $ zipWith f xs ys The fmap problem shows up a lot in Traversable instances. Consider a binary leaf tree: data Tree a = Bin (Tree a) (Tree a) | Leaf a The obvious way to write the Traversable instance today is instance Traversable Tree where traverse _f Tip = pure Tip traverse f (Bin p q) = Bin <$> traverse f p <*> traverse f q 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.confusing[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! traverse f (Bin p q) = liftA2 Bin (traverse f p) (traverse f q) The complication with Traversable instances boils down to an efficiency asymmetry in <*> association. According to the "composition" law, (.) <$> u <*> v <*> w = u <*> (v <*> w) 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: 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 _______________________________________________ Libraries mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries |
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. 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. Overall, I am weakly in favor.
_______________________________________________ Libraries mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries |
In reply to this post by David Feuer
Sorry for the confused traversal. That should've been traverse f (Leaf x) = Leaf <$> f x On Jan 14, 2017 4:49 PM, "David Feuer" <[hidden email]> wrote:
_______________________________________________ Libraries mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries |
In reply to this post by David Menendez-2
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. On Jan 14, 2017 9:58 PM, "David Menendez" <[hidden email]> wrote:
_______________________________________________ Libraries mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries |
In reply to this post by David Feuer
+1. I also sometimes define a specialized liftA2 and then use it to define (<*>), which then gets used to define the real liftA2. I think of liftA2 as playing a role similar to foldMap and traverse, while (<*>) corresponds to fold and sequenceA. The first three self-compose nicely: liftA2.liftA2.liftA2, foldMap.foldMap.foldMap, and traverse.traverse.traverse. With functor composition, it's so much nicer to write liftA2.liftA2 (in the style of Functor, Foldable, and Traversable) rather than liftA2 (<*>). -- Conal On Sat, Jan 14, 2017 at 1:49 PM, David Feuer <[hidden email]> wrote:
_______________________________________________ Libraries mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries |
On 14/01/2017, Conal Elliott <[hidden email]> wrote:
> The first three self-compose > nicely: liftA2.liftA2.liftA2, foldMap.foldMap.foldMap, and > traverse.traverse.traverse. Very true! I often use the `liftA` functions thus. _______________________________________________ Libraries mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries |
In reply to this post by David Feuer
I'm in favor of this change. From my perspecive, liftA2 is actually the fundamental Applicative operation, an <*> is merely a convenient isomorphism. When I'm teaching, showing the symmetry between the following always seems to help students: fmap :: (a -> b) -> f a -> f b liftA2 :: (a -> b -> c) -> f a -> f b -> f c flip (>>=) :: (a -> f b) -> f a -> f b <*> is obviously exceptionally useful in practice. But liftA2 seems like the more essential shape of that operation. Kris On Sat, Jan 14, 2017 at 2:49 PM, David Feuer <[hidden email]> wrote:
_______________________________________________ Libraries mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries |
I'm also all for adding liftA2 to the class and have noticed this
inefficiency/asymmetry when working on the class hierarchies for other languages On Sun, Jan 15, 2017 at 8:11 AM, Kris Nuttycombe <[hidden email]> wrote: > I'm in favor of this change. From my perspecive, liftA2 is actually the > fundamental Applicative operation, an <*> is merely a convenient > isomorphism. When I'm teaching, showing the symmetry between the following > always seems to help students: > > fmap :: (a -> b) -> f a -> f b > liftA2 :: (a -> b -> c) -> f a -> f b -> f c > flip (>>=) :: (a -> f b) -> f a -> f b > > <*> is obviously exceptionally useful in practice. But liftA2 seems like the > more essential shape of that operation. > > Kris > > On Sat, Jan 14, 2017 at 2:49 PM, David Feuer <[hidden email]> wrote: >> >> Right now, we define >> >> liftA2 :: Applicative f >> => (a -> b -> c) -> f a -> f b -> f c >> liftA2 f x y = f <$> x <*> y >> >> For some functors, like IO, this definition is just dandy. But for others, >> it's not so hot. For ZipList, for example, we get >> >> liftA2 f (ZipList xs) (ZipList ys) = >> ZipList $ zipWith id (map f xs) ys >> >> 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 >> >> liftA2 f (ZipList xs) (ZipList ys) = >> ZipList $ zipWith f xs ys >> >> The fmap problem shows up a lot in Traversable instances. Consider a >> binary leaf tree: >> >> data Tree a = Bin (Tree a) (Tree a) | Leaf a >> >> The obvious way to write the Traversable instance today is >> >> instance Traversable Tree where >> traverse _f Tip = pure Tip >> traverse f (Bin p q) = Bin <$> traverse f p <*> traverse f q >> >> 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.confusing[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! >> >> traverse f (Bin p q) = liftA2 Bin (traverse f p) (traverse f q) >> >> The complication with Traversable instances boils down to an efficiency >> asymmetry in <*> association. According to the "composition" law, >> >> (.) <$> u <*> v <*> w = u <*> (v <*> w) >> >> 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: >> >> 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 >> >> >> [1] >> https://hackage.haskell.org/package/lens-4.15.1/docs/Control-Lens-Traversal.html#g:11 >> >> [2] http://comonad.com/reader/2015/free-monoids-in-haskell/ >> >> _______________________________________________ >> Libraries mailing list >> [hidden email] >> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries >> > > > _______________________________________________ > Libraries mailing list > [hidden email] > http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries > -- Live well, ~wren _______________________________________________ Libraries mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries |
In reply to this post by David Feuer
On 2017-01-14 22:49, David Feuer wrote:
> Right now, we define > +1 _______________________________________________ Libraries mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries |
Free forum by Nabble | Edit this page |