Quantcast

Discussion: should we make liftA2 an Applicative method?

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
9 messages Options
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Discussion: should we make liftA2 an Applicative method?

David Feuer
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
|  
Report Content as Inappropriate

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

David Menendez-2
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 <[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
|  
Report Content as Inappropriate

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

David Feuer
In reply to this post by David Feuer
Sorry for the confused traversal. That should've been

traverse f (Leaf x) = Leaf <$> f x

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
|  
Report Content as Inappropriate

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

David Feuer
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 <[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
|  
Report Content as Inappropriate

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

Conal Elliott
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 (<*>).

-- Conal

On Sat, Jan 14, 2017 at 1: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
|  
Report Content as Inappropriate

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

M Farkas-Dyck-2
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
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

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

Kris Nuttycombe
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 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




_______________________________________________
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
|  
Report Content as Inappropriate

Re: 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
<[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
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

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

Bardur Arantsson-2
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
Loading...