"高阶可穿越"课程应该是什么样的？

Question

在这个答案中,我在现场制作了一些看起来有点像"更高阶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因为它似乎是正确的,但是当我坐下来写作时,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问题-我需要走了一路索引的单子？"从Functor类别到Hask的可穿越仿函数"的类应该是什么样的？这样的事情甚至存在吗？

Answer 1

在第一顺序,我们有sequence = traverse id.

这里是htraversehas类型的第一个参数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