Add Foldable / Traversable instances for tuples

[Bodigrim]

(This was originially submitted by @Topsii as a part of #93 / !9489, but I think it's worth its own discussion)

At the moment we have instance Functor (x,y,), instance Bifunctor (x,,), instance Bifoldable (x,,) and instance Bitraversable (x,,), but neither instance Foldable (x,y,) nor instance Traversable (x,y,). This is extremely inconsistent. Thus the proposal is to add them, and similar for all tuples up to 7 elements.

(7 is not an arbitrary number, Haskell Report suggests that standard functions should be implemented for tuples up to 7 elements)

[tomjaguarpaw]

Although I appreciate the push for greater consistency I am very skeptical about this. The proposed Foldable instances mean that we enlarge the set of circumstances where people get confused about length _.

[mixphix]

I wonder what the potential breakage from removing tuple instances of Functor/Foldable/Traversable would be. Given that it is widely agreed that length (x, y) == 1 is meaningless, perhaps we ought to remove the footgun instead of adding more?

[phadej]

There is nothing wrong with Functor ((,) a) nor Traversable ((,) a. These are not footguns (except if latter is used to define Foldable-like combinators).

Similarly one can argue that Foldable (Map k) and Foldable Set are footguns as elem @Set @a and elem @(Map k) @v are O(n), not O(log n). However removing Traversable (Map k) will break a lot of code.

---

Removing Traversable ((,) a breaks GHC itself already.

--- a/libraries/base/Data/Traversable.hs
+++ b/libraries/base/Data/Traversable.hs
@@ -314,8 +314,8 @@ instance Traversable (Either a) where
 deriving instance Traversable Solo
 
 -- | @since 4.7.0.0
-instance Traversable ((,) a) where
-    traverse f (x, y) = (,) x <$> f y
+-- instance Traversable ((,) a) where
+--     traverse f (x, y) = (,) x <$> f y
 
 -- | @since 2.01
 instance Ix i => Traversable (Array i) where

results in failure to compile GHC:

compiler/GHC/Utils/Monad.hs:196:22: error: [GHC-39999]
    • Could not deduce ‘Traversable ((,) a)’
        arising from a use of ‘traverse’
      from the context: (Applicative m, Traversable f)
        bound by the type signature for:
                   mapSndM :: forall (m :: * -> *) (f :: * -> *) b c a.
                              (Applicative m, Traversable f) =>
                              (b -> m c) -> f (a, b) -> m (f (a, c))
        at compiler/GHC/Utils/Monad.hs:195:1-81

I actually was expecting the transformers to fail to compile already, but its writer and state are defined in a swapped way:

newtype WriterT w m a = WriterT { runWriterT :: m (a, w) }

instance (Traversable f) => Traversable (WriterT w f) where
    traverse f = fmap WriterT . traverse f' . runWriterT where
       f' (a, b) = fmap (\ c -> (c, b)) (f a) -- strict first @(,) f

so they inline first (and don't use traverse).

[mpickering]

Foldable ((,) a) was already a mistake, I am strongly opposed to adding any more instances for the other tuple sizes.

[Topsii]

(This was originially submitted by @Topsii as a part of #93 / !9489, but I think it's worth its own discussion)

I have moved the tuple instance definitions to a separate commit for the case that this is approved. The merge request is !11538.

[s-and-witch]

Hello there.

I'm working on codebase with high usage of high order functions that do something with monad M. These helpers change some environment for inner computation, catch errors and perform other complicated actions. A lot of them use tuples to return some additional stuff, so they may have such types:

M a -> M a
M a -> M (A, a)
M a -> M (A, B, a)

I didn't see more than 3 return values, however I can't say they can't be found in the future.

I had to write a wrapper monad under M, let's say SM, that can be defined as StateT S M. Furthermore, I need high-order helpers to work with my monad, i.e. I need to lift all these helpers into my monad:

(forall a. M a -> M a) -> SM a -> SM a
(forall a. M a -> M (A, a)) -> SM a -> SM (A, a)
(forall a. M a -> M (A, B, a)) -> SM a -> SM (A, B, a)

I need to use RankNTypes here because I'm passing M (a, S) inside.

This helper should treat state carefully and perform some steps to fill M's environment to work properly, so I wish to define it only once. After a lot of work I come with generalization of all the functions that I may need:

Traversal t => (forall a. M a -> M (t a)) -> SM a -> SM (t a)

edit: Traversable t here

I started to use my helper function in the codebase, and, after hard work, I updated all the subsystem of my interest to my new monad. Updated and found that

Could not deduce ‘Traversable ((,,) A B)’

Thanks to everyone who participated in the discussion 🙏.

[tomjaguarpaw]

I guess you mean

Traversable t => (forall a. M a -> M (t a)) -> SM a -> SM (t a)

I'm not sure if you're saying you're stuck, but if so I see two possible ways to proceed:

1. Define newtype TupleWrapper a b c = TupleWrapper (a, b, c). Then you can give it a Traversable instance.

2. Instead of taking a Traversable as a constraint, take the traverse operation as an argument:

    (forall a b f. Applicative f => (a -> f b) -> t a -> f (t b)) -> (forall a. M a -> M (t a)) -> SM a -> SM (t a)
   

[s-and-witch]

I understand that there are low-tech workarounds, that doesn't allow me to use one function in all cases, however I want to give you a motivational example about what may happen in the wild.

I've never had no desire to use length or minimum on a tuple and don't feel a problem here, but I want to be able to write a polymorphic function that can work with widely used types.

[mixphix]

low-tech workarounds

Okay.

Once again, I think that if users need Foldable or Traversable tuples, that they're Doing It Wrong, but that custom types and writing their own instances gives them the power to do so if they choose. I am against adding these instances and would much prefer we remove the existing ones for pairs instead.

[Bodigrim]

The proposed Foldable instances mean that we enlarge the set of circumstances where people get confused about length _.

@tomjaguarpaw could you possibly unpack this argument? What's exactly confusing?

As we discussed at https://discourse.haskell.org/t/in-retrospect-was-burning-bridges-a-mistake/8188/46, it's not like Foldable in general is confusing for users. And certainly length of tuple is no worse than length of Identity, Maybe and Either.

[tomjaguarpaw]

I mean that length (1, 2) == 1 is confusing. This proposal suggests allowing length (1, 2, 3) (which would also equal 1), which is also confusing. I don't think that's a good idea. I would say that we should never have had all of these conditions pertain at the same time

• instance Foldable ((,) a)
• length a method of Foldable
• The length exported from the Prelude being the one from Foldable

But sadly all three do pertain. Let's not make things worse by allowing length (1, 2, 3) == 1 to hold from the Prelude.

I disagree that length (Identity 1) == 1, length Nothing == 0 or length (Just 1) == 1 are confusing. I do find length (Right 1) == 1 combined with length (Left 2) == 0 confusing.

(I agree that Foldable length is in principle a meaningful operation, but it shouldn't be the length we get from Prelude. Oh well. Too late now.)

[Bodigrim]

I disagree that length (Identity 1) == 1, length Nothing == 0 or length (Just 1) == 1 are confusing.

What about length (Identity [1,2,3]) == 1 and same for Just? Is it not confusing?

[tomjaguarpaw]

There's a difference of degree. length (1, 2, 3) == 1 is much more confusing than length (Identity [1, 2, 3]) == 1 (or length [[1, 2, 3]] == 1, for that matter).