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

Question

在 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 的可遍历仿函数”的类应该是什么样的？这样的事情还存在吗？

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