Discussion: should we make liftA2 an Applicative method?

Conal Elliott conal at conal.net
Sun Jan 15 06:40:58 UTC 2017


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 <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/
> _______________________________________________
> Libraries mailing list
> Libraries at haskell.org
> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/libraries/attachments/20170114/f5dfc1ab/attachment.html>

More information about the Libraries mailing list