Discussion: should we make liftA2 an Applicative method?

[wren romano]

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
<kris.nuttycombe at gmail.com> 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 <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
>>
>
>
> _______________________________________________
> Libraries mailing list
> Libraries at haskell.org
> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
>



-- 
Live well,
~wren