Proposal: make liftA2 an Applicative method?

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
3 messages Options
Reply | Threaded
Open this post in threaded view
|

Proposal: make liftA2 an Applicative method?

David Feuer
Since most of the feedback on my suggestion has been positive, I figured I'd upgrade it to an official proposal. Let's do this!

On Jan 14, 2017 4: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





_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Proposal: make liftA2 an Applicative method?

Kris Nuttycombe
+1, strongly in favor.

On Thu, Jan 19, 2017 at 12:07 PM, David Feuer <[hidden email]> wrote:
Since most of the feedback on my suggestion has been positive, I figured I'd upgrade it to an official proposal. Let's do this!

On Jan 14, 2017 4: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





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

Re: Proposal: make liftA2 an Applicative method?

Mario Blažević
In reply to this post by David Feuer
On 2017-01-19 02:07 PM, David Feuer wrote:
> Since most of the feedback on my suggestion has been positive, I figured
> I'd upgrade it to an official proposal. Let's do this!

I didn't pipe up before, +1.


_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries