"higher order Traversable" class 应该是什么样的？

Question

在中，我当场编造了一些看起来有点像 "higher order Traversable" 的东西：像 Traversable 但对于 Hask to Hask 上的内函子类别的函子。

{-# 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 的超级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 调用 returns 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)

但我无法想出一种根据 hsequence 实现 htraverse 的方法。和以前一样，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？ "traversable functors from the Functor category to Hask" 的 class 应该是什么样的？有这种东西吗？

Answer 1

首先，我们有 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

"higher order Traversable" class 应该是什么样的？

What should a "higher order Traversable" class look like?

monads

haskell

functional-programming

category-theory

traversable