什么应该是“高阶可穿越”类看起来像？ [英] What should a "higher order Traversable" class look like?

问题描述

在这个答案我当场做了一件看起来有点像更高的订单 Traversable ：类似于 Traversable ，但是对于Hask和Hask中的endofunctors类别的函子

  { - ＃LANGUAGE RankNTypes＃ - } 
导入Data.Functor.Compose 
导入Data.Functor.Identity 
 
 class HFunctor t其中
 hmap ::（forall x。fx  - > gx） - > t f  - > t g 
 
 class HFunctor t => HTraversable t其中
 htraverse :: Applicative g => （全部x，f x  - > g x） - > t f  - > g（t身份）
 htraverse eta = hsequence。 hmap eta 
 hsequence :: Applicative f => t f  - > f（t Identity）
 hsequence = htraverse id 
  

我做了 HFunctor 超类 HTraversable ，因为它看起来不错，但是当我坐下来写 hmapDefault 我被卡住了。

  hmapDefault :: HTraversable t => （全部x，f x  - > g x） - > t f  - > t g 
 hmapDefault eta = runIdentity。 htraverse（Identity。eta）
 
  - •无法将类型'x'与'g x'匹配
  - 预期类型：f x  - >身份x 
  - 实际类型：f x  - >身份（g x）
  

身份。 eta 的类型为 forall y。 f y - >身份（gy），所以当我将它传递给 htraverse g 与身份和 x 必须与 y 和 gy ，所以它失败了，因为遍历函数不是自然转换。

我试图用
$ b $ $ $ $ $ $ $ $ hmapDefault :: HTraversable t => （全部x，f x - > g x） - > t f - > t g
hmapDefault eta = runIdentity。 getCompose。 htraverse（Compose。Identity。eta）


现在撰写。身份。 eta 是一个自然转换，但您不能 htraverse ，因为您不知道 Applicative g 。即使你可以这样做， runIdentity 调用返回 g（t Identity）将 g 放回到 t 中的方法。

---

然后我意识到我的 htraverse 并不类似于普通的遍历。 遍历的遍历函数将新值放入中，并将 Applicative 效果，使得类型表达更大。因此 htraverse 应该如下所示：

  class HFunctor t => ; HTraversable t其中
 htraverse :: Applicative a => （其中x.f x→a（g x））→> t f  - > a（tg）
  

很有希望这个定义看起来更像 Traversable 和 hmapDefault 顺利结束，

  hmapDefault :: HTraversable t => （全部x，f x  - > g x） - > t f  - > t g 
 hmapDefault eta = runIdentity。 htraverse（Identity。eta）
  

但我很努力地为<$提供了一个很好的模拟C $ C> sequenceA 。我试过了：



  hsequence ::（HTraversable t，Applicative f）=> t f  - > f（t身份）
 hsequence = htraverse（fmap身份）
  

但我不能按照 hsequence 提出一种实现 htraverse 的方法。与以前一样， f 不是自然转换。



  htraverse f =顺序。 hmap f 
 
  - •无法将类型'x'与'g x'匹配
  - 预期类型：f x  - > a x 
  - 实际类型：f x  - > a（gx）
  

我怀疑我的 hsequence 输入签名错误。是 Applicative 问题 - 我是否需要一直到索引单子？ 从 Functor 类别到Hask的遍历函数类应该是什么样子？这样的事情是否存在？

解决方案

第一步，我们有 sequence = traverse id < code $。



这里 htraverse 的第一个参数的类型是 forall x 。 f x - >一个（g x），我们不能有 id ，但我们可以尝试一个同构。为使 fx 与 a（gx）同构，我们可以选择 f〜Compose ag 。

  htraverse = hsequence。 hmap（Compose。eta）
 
 hsequence :: Applicative a => t（构成g） - > a（t g）
 hsequence = htraverse getCompose 
  




In this answer I made up on the spot something which looks a bit like a "higher order Traversable": like Traversable but for functors from the category of endofunctors on 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

I made HFunctor a superclass of HTraversable because it seemed right, but when I sat down to write hmapDefault I got stuck.

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 has a type forall y. f y -> Identity (g y), so when I pass it into htraverse g unifies with Identity and x has to unify with both y and g y, so it fails because the traversal function is not a natural transformation.

I attempted to patch it up using Compose:

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

Now Compose . Identity . eta is a natural transformation, but you can't htraverse with it because you don't know Applicative g. And even if you could do that, the runIdentity call returns g (t Identity) and you're left with no way to put the g back inside the t.

---

I then realised that my htraverse isn't really analogous to plain old traverse. The traversal function of traverse puts the new value inside an Applicative effect, making the type expression bigger. So htraverse should probably look like this:

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

It's promising that this definition looks more like Traversable, and hmapDefault goes off without a hitch,

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

but I'm struggling to come up with a good analogue for sequenceA. I tried

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

but I can't come up with a way of implementing htraverse in terms of hsequence. As before, f is not a natural transformation.

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)

I suspect I have my hsequence type signature wrong. Is Applicative the problem - do I need to go all the way up to indexed monads? What should a class for "traversable functors from the Functor category to Hask" look like? Does such a thing even exist?

解决方案

In first order, we have sequence = traverse id.

Here the first argument of htraverse has type forall x. f x -> a (g x), we can't have id, but we can try with an isomorphism instead. For f x to be isomorphic to a (g x), we can pick f ~ Compose a g.

htraverse = hsequence . hmap (Compose . eta)

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

这篇关于什么应该是“高阶可穿越”类看起来像？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！