6

在这个答案中，我当场编造了一些看起来有点像“高阶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有一个 type forall y. f y -> Identity (g y)，所以当我将它传递给htraverse gunifies withIdentity并且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)，你将无法将gback 放入t.

然后我意识到 myhtraverse并不是真的类似于普通的 old 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的可遍历函子”的类应该是什么样的？这样的事情还存在吗？

4

1 回答 1

7

首先，我们有sequence = traverse id.

htraverse这里has type的第一个参数forall x. f x -> a (g x)，我们不能 have 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
于 2017-05-25T20:26:30.093 回答