Proposal: make liftA2 an Applicative method?
David Feuer
david.feuer at gmail.com
Thu Jan 19 19:07:41 UTC 2017
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" <david.feuer at gmail.com> 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/
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/libraries/attachments/20170119/916996c8/attachment.html>
More information about the Libraries
mailing list