haskell - "higher order Traversable"类应该是什么样？

在this answer中，我当场制作了一个看起来有点像“高阶Traversable”的东西:类似于Traversable，但适用于从Hask到Hask的endofunctors类别的仿函数。

{-# LANGUAGE RankNTypes #-}
import Data.Functor.Compose
import Data.Functor.Identity

class HFunctor t where
    hmap :: (forall x. f x -> g x) -> t f -> t g

class HFunctor t => HTraversable t where
    htraverse :: Applicative g => (forall x. f x -> g x) -> t f -> g (t Identity)
    htraverse eta = hsequence . hmap eta
    hsequence :: Applicative f => t f -> f (t Identity)
    hsequence = htraverse id

因为看起来正确，所以我使HFunctor成为HTraversable的父类(super class)，但是当我坐下来写hmapDefault时，我陷入了困境。

hmapDefault :: HTraversable t => (forall x. f x -> g x) -> t f -> t g
hmapDefault eta = runIdentity . htraverse (Identity . eta)

-- • Couldn't match type ‘x’ with ‘g x’
--   Expected type: f x -> Identity x
--     Actual type: f x -> Identity (g x)

Identity . eta的类型为forall y. f y -> Identity (g y)，因此当我将其传递给htraverse时，g与Identity统一，而x必须与y和g y统一，因此它失败了，因为遍历函数不是自然的转换。

我试图使用Compose对其进行修补:

hmapDefault :: HTraversable t => (forall x. f x -> g x) -> t f -> t g
hmapDefault eta = runIdentity . getCompose . htraverse (Compose . Identity . eta)

现在Compose . Identity . eta是自然的转换，但是您不可以使用htraverse，因为您不知道Applicative g。即使可以这样做，runIdentity调用也会返回g (t Identity)，您将无法将g放回t内。

然后，我意识到我的htraverse确实不像普通的旧traverse。 traverse的遍历函数将新值放入Applicative效果内，从而使类型表达式更大。所以htraverse应该看起来像这样:

class HFunctor t => HTraversable t where
    htraverse :: Applicative a => (forall x. f x -> a (g x)) -> t f -> a (t g)

可以肯定的是，此定义看起来更像Traversable，并且hmapDefault顺利实现，

hmapDefault :: HTraversable t => (forall x. f x -> g x) -> t f -> t g
hmapDefault eta = runIdentity . htraverse (Identity . eta)

但是我在努力为sequenceA提供一个很好的模拟。我试过了

hsequence :: (HTraversable t, Applicative f) => t f -> f (t Identity)
hsequence = htraverse (fmap Identity)

但我无法想出一种根据htraverse实现hsequence的方法。和以前一样，f不是自然的转换。

htraverse f = hsequence . hmap f

-- • Couldn't match type ‘x’ with ‘g x’
--   Expected type: f x -> a x
--     Actual type: f x -> a (g x)

我怀疑自己的hsequence类型签名错误。 Applicative是问题吗？我需要一直坚持到indexed monads吗？ “从Functor类别到Hask的可遍历仿函数”的类应该是什么样的？这样的事情甚至存在吗？

最佳答案

首先，我们有sequence = traverse id。

这里htraverse的第一个参数的类型为forall x. f x -> a (g x)，我们不能使用id，但是我们可以尝试使用同构。为了使f x与a (g x)同构，我们可以选择f ~ Compose a g。

htraverse = hsequence . hmap (Compose . eta)

hsequence :: Applicative a => t (Compose a g) -> a (t g)
hsequence = htraverse getCompose