Re: [Haskell-cafe] Textbook example of instance Foldable ((,)a)

newer
Amazonka, conduit and sockets not...

older
network v3.1.2.1

Barak A. Pearlmutter

25 Nov 2020 25 Nov '20

9:05 a.m.

On Tue, 24 Nov 2020, Henning Thielemann wrote:

...

If people would use custom pair types we would not need Foldable on pairs, at all.

To be fair, if people would use custom pair types we would not need *pairs* at all. --Barak Pearlmutter

Show replies by date

Zemyla

25 Nov 25 Nov

12:26 p.m.

New subject: Textbook example of instance Foldable ((,)a)

Except we would, because we need to be able to express instances like first in Arrow using builtin pairs, rather than try and write some sort of combination for every pair and arrow. And I'm pretty sure there are other libraries which depend on pairs too. On Wed, Nov 25, 2020, 08:07 Barak A. Pearlmutter wrote:

...

On Tue, 24 Nov 2020, Henning Thielemann wrote:

...
If people would use custom pair types we would not need Foldable on pairs, at all.

To be fair, if people would use custom pair types we would not need *pairs* at all.

--Barak Pearlmutter _______________________________________________ Haskell-Cafe mailing list To (un)subscribe, modify options or view archives go to: http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe Only members subscribed via the mailman list are allowed to post.

Viktor Dukhovni

12:52 p.m.

New subject: Textbook example of instance Foldable ((,)a)

...

On Nov 25, 2020, at 3:26 PM, Zemyla wrote:

Except we would, because we need to be able to express instances like first in Arrow using builtin pairs, rather than try and write some sort of combination for every pair and arrow. And I'm pretty sure there are other libraries which depend on pairs too.

This is why I posted the not terribly ergonomic: newtype T2 a b = T2 { _unT2 :: (a, b) } which has a free coercion to a pair, so you can pass a pair to any library that needs one, without any runtime overhead. This of course takes much discipline to use when refactoring data types, in order to avoid missing needed changes obscured by unwanted instances of the built-in pair. Wherever you need a pair, you'd have to write "(coerce t2)", rather than "t2". -- Viktor.

Barak A. Pearlmutter

2:56 p.m.

New subject: Textbook example of instance Foldable ((,)a)

True. And their use in Arrow is a great example of pairs that do *not* work well as instances of Foldable as currently defined. Arrow is using pairs as abstract Cartesian products, and the natural isomorphism A×B≅B×A is used implicitly all the time. The Foldable definition for pairs breaks that symmetry inappropriately. Cheers, --Barak.

Viktor Dukhovni

3:16 p.m.

New subject: Textbook example of instance Foldable ((,)a)

On Wed, Nov 25, 2020 at 07:56:49PM +0000, Barak A. Pearlmutter wrote:

...

True. And their use in Arrow is a great example of pairs that do *not* work well as instances of Foldable as currently defined. Arrow is using pairs as abstract Cartesian products, and the natural isomorphism A×B≅B×A is used implicitly all the time. The Foldable definition for pairs breaks that symmetry inappropriately.

The "symmetry breaking" is not a result of the perhaps regrettable Foldable instance, rather it is a basic consequence of the fact that given: data Foo a b = Foo a b we immediately get a Functor "Foo a :: * -> *" for each a, of which "(,) a" is but one example. I find nothing objectionable in the Functor instance "(,) a" or the Bifunctor instance "(,)". It is only the Traversable and Foldable instances of "(,) a" that have the noted unexpected behaviour. -- Viktor.

amindfv＠mailbox.org

4:15 p.m.

New subject: Textbook example of instance Foldable ((,)a)

On Wed, Nov 25, 2020 at 03:16:22PM -0500, Viktor Dukhovni wrote:

...

On Wed, Nov 25, 2020 at 07:56:49PM +0000, Barak A. Pearlmutter wrote:

...
True. And their use in Arrow is a great example of pairs that do *not* work well as instances of Foldable as currently defined. Arrow is using pairs as abstract Cartesian products, and the natural isomorphism A×B≅B×A is used implicitly all the time. The Foldable definition for pairs breaks that symmetry inappropriately.

The "symmetry breaking" is not a result of the perhaps regrettable Foldable instance, rather it is a basic consequence of the fact that given:

data Foo a b = Foo a b

we immediately get a Functor "Foo a :: * -> *" for each a, of which "(,) a" is but one example. I find nothing objectionable in the Functor instance "(,) a" or the Bifunctor instance "(,)". It is only the Traversable and Foldable instances of "(,) a" that have the noted unexpected behaviour.

This is almost incidental, though, right? I.e. it's just a result of typeclass "currying" syntax, but it's not hard to imagine a Haskell where similar to how foo :: a -> b -> c gives you both: foo a :: b -> c i.e. (\b -> foo a b) :: b -> c and (\a -> foo a b) :: a -> c we're also allowed to write something like: instance Functor (\a -> Foo a b) instance Functor (\a -> (a, b)) Mirroring the current (implicit) instance Functor (\b -> Foo a b) instance Functor (\b -> (a, b)) If that were the case, the instances favoring the last paramater wouldn't seem natural at all, and we'd be sensibly asking on what basis "(+1) <$> (2, 4)" equals (2, 5) but not (3, 4). Tom

Viktor Dukhovni

6:13 p.m.

New subject: Textbook example of instance Foldable ((,)a)

On Wed, Nov 25, 2020 at 04:15:18PM -0500, amindfv--- via Haskell-Cafe wrote:

...

...
The "symmetry breaking" is not a result of the perhaps regrettable Foldable instance, rather it is a basic consequence of the fact that given:

data Foo a b = Foo a b

we immediately get a Functor "Foo a :: * -> *" for each a, of which "(,) a" is but one example. I find nothing objectionable in the Functor instance "(,) a" or the Bifunctor instance "(,)". It is only the Traversable and Foldable instances of "(,) a" that have the noted unexpected behaviour.

This is almost incidental, though, right? I.e. it's just a result of typeclass "currying" syntax,

Yes, the last type variable gets the "for free" functor instance.

...

but it's not hard to imagine a Haskell where [...]

we're also allowed to write something like:

instance Functor (\a -> Foo a b) instance Functor (\a -> (a, b))

Mirroring the current (implicit)

instance Functor (\b -> Foo a b) instance Functor (\b -> (a, b))

If that were the case, the instances favoring the last paramater wouldn't seem natural at all, and we'd be sensibly asking on what basis "(+1) <$> (2, 4)" equals (2, 5) but not (3, 4).

The intent is clear, but ultimately not as useful as one might wish, since when it comes down to evaluating terms: fmap f (x, y) at most one such instance can match, since the terms don't carry any information about whether you want to fmap on the left or right. So all you'd get to do is flip the bias from right to left. To avoid the bias we have Bifunctors: first :: Bifunctor p => (a -> b) -> p a c -> p b c second :: Bifunctor p => (b -> c) -> p a b -> p a c For selectable bias on 2-tuples, one needs newtypes: {-# LANGUAGE FlexibleContexts #-} {-# LANGUAGE FlexibleInstances #-} {-# LANGUAGE FunctionalDependencies #-} import Data.Bifunctor import Data.Coerce class Coercible c (a,b) => NewPair c a b | c -> a, c -> b where toPair :: c -> (a, b) toPair = coerce {-# INLINE toPair #-} fromPair :: (a, b) -> c fromPair = coerce {-# INLINE fromPair #-} -- RPair is redundant, except to avoid Foldable, ... instances newtype LPair b a = LPair (a, b) deriving (Eq, Ord, Read, Show) newtype RPair a b = RPair (a, b) deriving (Eq, Ord, Read, Show) instance NewPair (a, b) a b instance NewPair (LPair b a) a b instance NewPair (RPair a b) a b instance Functor (LPair a) where fmap f = fromPair . first f . toPair instance Functor (RPair a) where fmap f = fromPair . second f . toPair with the above: λ> fmap succ $ LPair (1, 10) LPair (2,10) λ> fmap succ $ RPair (1, 10) RPair (1,11) -- Viktor.

amindfv＠mailbox.org

7:23 p.m.

New subject: Textbook example of instance Foldable ((,)a)

On Wed, Nov 25, 2020 at 06:13:10PM -0500, Viktor Dukhovni wrote:

...

On Wed, Nov 25, 2020 at 04:15:18PM -0500, amindfv--- via Haskell-Cafe wrote:

...
...
The "symmetry breaking" is not a result of the perhaps regrettable Foldable instance, rather it is a basic consequence of the fact that given:

data Foo a b = Foo a b

we immediately get a Functor "Foo a :: * -> *" for each a, of which "(,) a" is but one example. I find nothing objectionable in the Functor instance "(,) a" or the Bifunctor instance "(,)". It is only the Traversable and Foldable instances of "(,) a" that have the noted unexpected behaviour.

This is almost incidental, though, right? I.e. it's just a result of typeclass "currying" syntax,

Yes, the last type variable gets the "for free" functor instance.

...
but it's not hard to imagine a Haskell where [...]

we're also allowed to write something like:

instance Functor (\a -> Foo a b) instance Functor (\a -> (a, b))

Mirroring the current (implicit)

instance Functor (\b -> Foo a b) instance Functor (\b -> (a, b))

If that were the case, the instances favoring the last paramater wouldn't seem natural at all, and we'd be sensibly asking on what basis "(+1) <$> (2, 4)" equals (2, 5) but not (3, 4).

The intent is clear, but ultimately not as useful as one might wish, since when it comes down to evaluating terms:

fmap f (x, y)

at most one such instance can match, since the terms don't carry any information about whether you want to fmap on the left or right. So all you'd get to do is flip the bias from right to left.

Not sure if we're agreeing or not :-), but this is exactly my point: The fact that (fmap f (x, y)) == (Control.Arrow.second f (x, y)) seems to only be based, essentially, on the historical accident that in Haskell the last type variable is special w.r.t. typeclass instances. It's not hard to imagine, in the absence of these instances, Haskell loosening the restriction on creating these types of instances. The restriction is certainly not innate to mathematics or type theory. My position is against having most of these instances in base, not for switching the bias from right to left. Tom

Viktor Dukhovni

11:24 p.m.

New subject: Textbook example of instance Foldable ((,)a)

On Wed, Nov 25, 2020 at 07:23:20PM -0500, amindfv--- via Haskell-Cafe wrote:

...

...
The intent is clear, but ultimately not as useful as one might wish, since when it comes down to evaluating terms:

fmap f (x, y)

at most one such instance can match, since the terms don't carry any information about whether you want to fmap on the left or right. So all you'd get to do is flip the bias from right to left.

Not sure if we're agreeing or not :-), but this is exactly my point:

We're not disagreeing. :-)

...

The fact that (fmap f (x, y)) == (Control.Arrow.second f (x, y)) seems to only be based, essentially, on the historical accident that in Haskell the last type variable is special w.r.t. typeclass instances.

Yes, basically, which makes it easy to define Functor and related instances for the partially applied two parameter type constructor: Foo a :: * -> * and these are somewhat useful, since one then gets to embelish a general thing with some additional data: a -> (decorated, a) and adding the decoration on the left comes with a built-in functor instance, which, though the left/right choice is a somewhat (but not entirely) arbitrary choice, does no harm. No surprising behaviour arises from the Functor/Applicative/Monad instances for 2-tuples. Indeed, you probably find it less surprising that with "Either a b" and "Left a" as the conventional "exception" slot, the Functor instance transforms "Right b". The overall approach is consistent in its right bias, made more convenient through currying of multi-parameter type constructors. AFAICT, it is really just the Foldable instance that can lead to unexpected and behaviour and unnoticed bugs.

...

It's not hard to imagine, in the absence of these instances, Haskell loosening the restriction on creating these types of instances. The restriction is certainly not innate to mathematics or type theory.

Type inference would get more complicated if it would have to consider all possible slots in each term when searching for the instance head.

...

My position is against having most of these instances in base, not for switching the bias from right to left.

So you'd like to see a 2-tuple with fewer built-in instances, I'm sympathetic to the case for not having Traversable/Foldable for 2-tuples, but I don't see a compelling for not having Functor/Monad. -- Viktor.

Viktor Dukhovni

26 Nov 26 Nov

3:20 p.m.

New subject: Textbook example of instance Foldable ((,)a)

On Wed, Nov 25, 2020 at 11:24:41PM -0500, Viktor Dukhovni wrote:

...

...
It's not hard to imagine, in the absence of these instances, Haskell loosening the restriction on creating these types of instances. The restriction is certainly not innate to mathematics or type theory.

Type inference would get more complicated if it would have to consider all possible slots in each term when searching for the instance head.

...
My position is against having most of these instances in base, not for switching the bias from right to left.

So you'd like to see a 2-tuple with fewer built-in instances, I'm sympathetic to the case for not having Traversable/Foldable for 2-tuples, but I don't see a compelling for not having Functor/Monad.

Would the attached module be useful to you or anyone else? It implements two newtype-wrapped types: 'LP a b' and 'RP a b'. 'LP a b' has a run-time represenation of (and is coercible to) (b, a). It is a Functor, Applicative and Monad in the left slot of the underlying 2-tuple. 'RP a b' has a run-time representation of (a, b) and is a Functor, Applicative and Monad in the right slot of the underlying 2-tuple. λ> :t LP (1, "foo") LP (1, "foo") :: Num b => OrderedPair 'BL [Char] b λ> :t RP (1, "foo") RP (1, "foo") :: Num a => OrderedPair 'BR a [Char] These share the "safe" class instances of (,) from Prelude, but omit the potentially problematic Foldable (and hence also Traversable). λ> fmap succ $ LP (1, 10) LP (2,10) λ> fmap succ $ RP (1, 10) RP (1,11) The Bifunctor instance is therefore "flipped" in the "LP" case: λ> bimap succ pred $ LP (1, 10) LP (0,11) λ> bimap succ pred $ RP (1, 10) RP (2,9) The class 'LROrder' exports zero-cost coercions to ordinary 2-tuples, and also conversions to 2-tuples that take/return (a, b) regardless of the underlying 2-tuple representation. λ> toPair $ LP (1, "foo") (1,"foo") λ> rePair $ LP (1, "foo") ("foo",1) λ> toPair $ RP (1, "foo") (1,"foo") λ> rePair $ RP (1, "foo") (1,"foo") Application code can be polymorphic in the 2-tuple order: foo :: LROrder o => ((a, b) -> x) -> OrderedPair o a b -> x foo f = f . rePair bar :: LROrder o => (b -> c) -> OrderedPair o a b -> OrderedPair o a c bar f = fmap f or when desired work with a given order using coercions to extract the underlying representation for interaction with external libraries. foo :: ((b, a) -> x) -> LP a b -> x foo f = f . toPair bar :: ((a, b) -> x) -> RP a b -> x bar f = f . toPair baz :: (b -> c) -> ((c, a) -> x) -> LP a b -> x baz f g = g . toPair . fmap f I expect that for most cases the (b, a) representation is not particularly compelling. And the order-polymorphism is not needed. In other words, the existing "bias" of Functor, Applicative and Monad to operate on the second element is a natural convention rather than an obstacle. -- Viktor.

1636

Age (days ago)

1637

Last active (days ago)

List overview

Download

9 comments

4 participants

participants (4)

amindfv＠mailbox.org
Barak A. Pearlmutter
Viktor Dukhovni
Zemyla

Re: [Haskell-cafe] Textbook example of instance Foldable ((,)a)

tags

participants (4)