In response to this, I drew on the spot something similar to a “higher Traversable order”: for example, Traversable , but for functors from the Hask to Hask endofunction category.
{-# LANGUAGE RankNTypes #-} import Data.Functor.Compose import Data.Functor.Identity class HFunctor t where hmap :: (forall x. fx -> gx) -> tf -> tg class HFunctor t => HTraversable t where htraverse :: Applicative g => (forall x. fx -> gx) -> tf -> g (t Identity) htraverse eta = hsequence . hmap eta hsequence :: Applicative f => tf -> f (t Identity) hsequence = htraverse id
I made the HFunctor superclass from HTraversable because it seemed right, but when I sat down to write hmapDefault , I was stuck.
hmapDefault :: HTraversable t => (forall x. fx -> gx) -> tf -> tg hmapDefault eta = runIdentity . htraverse (Identity . eta) -- • Couldn't match type 'x' with 'g x' -- Expected type: fx -> Identity x -- Actual type: fx -> Identity (gx)
Identity . eta Identity . eta is of type forall y. fy -> Identity (gy) forall y. fy -> Identity (gy) , so when I pass it to htraverse g , it combines with Identity , and x must combine with both y and gy , so it does not work because the bypass function is not a natural conversion.
I tried to fix it using Compose :
hmapDefault :: HTraversable t => (forall x. fx -> gx) -> tf -> tg hmapDefault eta = runIdentity . getCompose . htraverse (Compose . Identity . eta)
Now Compose . Identity . eta Compose . Identity . eta Compose . Identity . eta is a natural transformation, but you cannot htraverse with it because you do not know Applicative g . And even if you can do this, calling runIdentity returns g (t Identity) , and you cannot put g back inside t .
Then I realized that my htraverse not like a regular old traverse . The traverse traversal function places the new value in the Applicative effect, making the type expression larger. Therefore, htraverse should look like this:
class HFunctor t => HTraversable t where htraverse :: Applicative a => (forall x. fx -> a (gx)) -> tf -> a (tg)
Having promised that this definition is more like Traversable , and hmapDefault disabled without hesitation,
hmapDefault :: HTraversable t => (forall x. fx -> gx) -> tf -> tg hmapDefault eta = runIdentity . htraverse (Identity . eta)
but I struggle to find a good analogue for sequenceA . I tried
hsequence :: (HTraversable t, Applicative f) => tf -> f (t Identity) hsequence = htraverse (fmap Identity)
but I can't think of a way to implement htraverse in terms of hsequence . As before, f not a natural transformation.
htraverse f = hsequence . hmap f -- • Couldn't match type 'x' with 'g x' -- Expected type: fx -> ax -- Actual type: fx -> a (gx)
I suspect that I have the wrong signature of type hsequence . Applicative task - do I need to go all the way to indexed monads ? What should the class look like for "passing functions from the Functor to Hask category"? Is there such a thing?