# Discussion: should we make liftA2 an Applicative method?

9 messages
Open this post in threaded view
|

## Discussion: should we make liftA2 an Applicative method?

 Right now, we defineliftA2 :: Applicative f  => (a -> b -> c) -> f a -> f b -> f cliftA2 f x y = f <\$> x <*> yFor some functors, like IO, this definition is just dandy. But for others, it's not so hot. For ZipList, for example, we getliftA2 f (ZipList xs) (ZipList ys) =  ZipList \$ zipWith id (map f xs) ysIn 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-efficientliftA2 f (ZipList xs) (ZipList ys) =  ZipList \$ zipWith f xs ysThe fmap problem shows up a lot in Traversable instances. Consider a binary leaf tree:data Tree a = Bin (Tree a) (Tree a) | Leaf aThe obvious way to write the Traversable instance today isinstance Traversable Tree where  traverse _f Tip = pure Tip  traverse f (Bin p q) = Bin <\$> traverse f p <*> traverse f qIn 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
Open this post in threaded view
|

## Re: Discussion: should we make liftA2 an Applicative method?

 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.On Sat, Jan 14, 2017 at 4:49 PM, David Feuer wrote:Right now, we defineliftA2 :: Applicative f  => (a -> b -> c) -> f a -> f b -> f cliftA2 f x y = f <\$> x <*> yFor some functors, like IO, this definition is just dandy. But for others, it's not so hot. For ZipList, for example, we getliftA2 f (ZipList xs) (ZipList ys) =  ZipList \$ zipWith id (map f xs) ysIn 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-efficientliftA2 f (ZipList xs) (ZipList ys) =  ZipList \$ zipWith f xs ysThe fmap problem shows up a lot in Traversable instances. Consider a binary leaf tree:data Tree a = Bin (Tree a) (Tree a) | Leaf aThe obvious way to write the Traversable instance today isinstance Traversable Tree where  traverse _f Tip = pure Tip  traverse f (Bin p q) = Bin <\$> traverse f p <*> traverse f qIn 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 -- Dave Menendez <[hidden email]> _______________________________________________ Libraries mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Open this post in threaded view
|

## Re: Discussion: should we make liftA2 an Applicative method?

 In reply to this post by David Feuer Sorry for the confused traversal. That should've beentraverse f (Leaf x) = Leaf <\$> f xOn Jan 14, 2017 4:49 PM, "David Feuer" <[hidden email]> wrote:Right now, we defineliftA2 :: Applicative f  => (a -> b -> c) -> f a -> f b -> f cliftA2 f x y = f <\$> x <*> yFor some functors, like IO, this definition is just dandy. But for others, it's not so hot. For ZipList, for example, we getliftA2 f (ZipList xs) (ZipList ys) =  ZipList \$ zipWith id (map f xs) ysIn 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-efficientliftA2 f (ZipList xs) (ZipList ys) =  ZipList \$ zipWith f xs ysThe fmap problem shows up a lot in Traversable instances. Consider a binary leaf tree:data Tree a = Bin (Tree a) (Tree a) | Leaf aThe obvious way to write the Traversable instance today isinstance Traversable Tree where  traverse _f Tip = pure Tip  traverse f (Bin p q) = Bin <\$> traverse f p <*> traverse f qIn 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
Open this post in threaded view
|

## Re: Discussion: should we make liftA2 an Applicative method?

 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: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.On Sat, Jan 14, 2017 at 4:49 PM, David Feuer wrote:Right now, we defineliftA2 :: Applicative f  => (a -> b -> c) -> f a -> f b -> f cliftA2 f x y = f <\$> x <*> yFor some functors, like IO, this definition is just dandy. But for others, it's not so hot. For ZipList, for example, we getliftA2 f (ZipList xs) (ZipList ys) =  ZipList \$ zipWith id (map f xs) ysIn 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-efficientliftA2 f (ZipList xs) (ZipList ys) =  ZipList \$ zipWith f xs ysThe fmap problem shows up a lot in Traversable instances. Consider a binary leaf tree:data Tree a = Bin (Tree a) (Tree a) | Leaf aThe obvious way to write the Traversable instance today isinstance Traversable Tree where  traverse _f Tip = pure Tip  traverse f (Bin p q) = Bin <\$> traverse f p <*> traverse f qIn 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 -- Dave Menendez <[hidden email]> _______________________________________________ Libraries mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Open this post in threaded view
|

## Re: Discussion: should we make liftA2 an Applicative method?

 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 (<*>).-- ConalOn Sat, Jan 14, 2017 at 1:49 PM, David Feuer wrote:Right now, we defineliftA2 :: Applicative f  => (a -> b -> c) -> f a -> f b -> f cliftA2 f x y = f <\$> x <*> yFor some functors, like IO, this definition is just dandy. But for others, it's not so hot. For ZipList, for example, we getliftA2 f (ZipList xs) (ZipList ys) =  ZipList \$ zipWith id (map f xs) ysIn 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-efficientliftA2 f (ZipList xs) (ZipList ys) =  ZipList \$ zipWith f xs ysThe fmap problem shows up a lot in Traversable instances. Consider a binary leaf tree:data Tree a = Bin (Tree a) (Tree a) | Leaf aThe obvious way to write the Traversable instance today isinstance Traversable Tree where  traverse _f Tip = pure Tip  traverse f (Bin p q) = Bin <\$> traverse f p <*> traverse f qIn 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 _______________________________________________ Libraries mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Open this post in threaded view
|

## Re: Discussion: should we make liftA2 an Applicative method?

 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
Open this post in threaded view
|

## Re: Discussion: should we make liftA2 an Applicative method?

 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 bliftA2 :: (a -> b -> c) -> f a -> f b -> f cflip (>>=) :: (a -> f b) -> f a -> f b<*> is obviously exceptionally useful in practice. But liftA2 seems like the more essential shape of that operation.KrisOn Sat, Jan 14, 2017 at 2:49 PM, David Feuer wrote:Right now, we defineliftA2 :: Applicative f  => (a -> b -> c) -> f a -> f b -> f cliftA2 f x y = f <\$> x <*> yFor some functors, like IO, this definition is just dandy. But for others, it's not so hot. For ZipList, for example, we getliftA2 f (ZipList xs) (ZipList ys) =  ZipList \$ zipWith id (map f xs) ysIn 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-efficientliftA2 f (ZipList xs) (ZipList ys) =  ZipList \$ zipWith f xs ysThe fmap problem shows up a lot in Traversable instances. Consider a binary leaf tree:data Tree a = Bin (Tree a) (Tree a) | Leaf aThe obvious way to write the Traversable instance today isinstance Traversable Tree where  traverse _f Tip = pure Tip  traverse f (Bin p q) = Bin <\$> traverse f p <*> traverse f qIn 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 _______________________________________________ Libraries mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Open this post in threaded view
|

## Re: Discussion: should we make liftA2 an Applicative method?

 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
Open this post in threaded view
|

## Re: Discussion: should we make liftA2 an Applicative method?

 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