But, yes, in general the problem with RTraversable is it can’t handle the polymorphic recursive case, and it can only handle cases that are non-polymorphically recursive by leaking the arguments for every intermediate state that gets threaded through the applicative.

This means that now the Traversable instance is even less canonical, because the constraint set can be written several different ways, e.g. by building up a tuple of the args, a level at a time and finally map them into the form they need to be in to (almost) avoid ever putting functions in, etc, but that gets hairy fast.

RTraversable is pretty much useless in practice as idiomatic haskell today, because as the API for applicative currently works you need to round trip almost everything with functions.

traverse f (Foo a b) = Foo traverse f a f b

incurs constraints that you are almost assuredly not going to be able to meet. Extending Applicative with a liftA2.. liftAn would partially alleviate the problem, but working in that system doesn’t appeal to me at all. =)

]]>```
class RTraversable (t :: * -> *) where
type ConT t (a :: *) :: Constraint
type ConT t a = ()
traverseR :: (ConT t a, ConT t b, Applicative f) =>
(a -> f b) -> t a -> f (t b)
```

Then we can define a “normal” instance that imposes no constraints and the polymorphic recursion does not pose a problem:

```
instance RTraversable Grow where
traverseR :: (ConT Grow a, ConT Grow b, Applicative f) =>
(a -> f b) -> Grow a -> f (Grow b)
traverseR g (Stop a) = Stop < $> g a
traverseR g (Complete aa) = Complete < $>
traverseR (\ (a1,a2) -> (,) < $> g a1 < *> g a2) aa
```

Or is this not what you meant? I agree that an instance that actually imposes a constraint would not work due to the polymorphic recursion, e.g.

```
class C a where ...
instance RTraversable Grow where
type ConT Grow a = C a
traverseR = -- as above
```

“*Could not deduce (C (b, b)) arising from a use of `traverseR’ from the context (ConT Grow a, ConT Grow b, Applicative f)*“

Did you mean:

data Grow a = Complete (Grow (a,a)) | Stop a

]]>I think this is related:

http://cs.ioc.ee/~tarmo/papers/fossacs10.pdf

Regards,

James

]]>e.g. Consider how to write the moral equivalent of a Traversable instance for

data Grow a = Grow (Complete (a,a)) | Stop a

in the presence of this kind of constraint.

Worse, you can’t even do normal Traversable instances. =(

]]>`Monad`

`m`

would break because the constraints may not, in general, be empty. Example:
```
newtype Kleisli m a b = Kleisli (a -> m b)
instance RMonad m => Category (Kleisli m) where
id :: {- Con m a => -} Kleisli m a a
id = Kleisli return
(.) :: {- (Con m b, Con m c) => -} Kleisli m b c -> Kleisli m a b -> Kleisli m a c
(Kleisli f) . (Kleisli g) = Kleisli (\ a -> g a >>= f)
```

]]>This is unfortunately just not true. Any code that relies on polymorphic recursion is irredeemably broken by this change. It doesn’t break simple code, but it makes harder cases all but impossible to write.

In the presence of polymorphic recursion using constrained monads by default means you have to limit yourself to a particular monad — or you have to provide explicit witnesses using something like the constraints package that can be used to derive the type for the constraint for the polymorphically recursive case from the previous recursion level, but that is quite horrific and its particular to each case. =(

]]>