是否可以反转类型对齐的遍历？

Question

这里有很多设置。如果您以前见过类型对齐的序列，您可以浏览所有内容直到该行。

类型对齐的序列是任何看起来模糊的东西

data ConsList c x y where
  CNil :: ConsList c x x     
  Cons :: c x y -> ConsList c y z -> ConsList c x z

给定一个 class 用于 Atkey 风格的索引函子和应用函子

class IxFunctor f where
  ixmap :: (a -> b) -> f x y a -> f x y b
class IxFunctor f => IxApply f where
  ixap :: f i j (a -> b) -> f j k a -> f i k b
class IxApply f => IxApplicative f where
  ixpure :: a -> f i i a

和一个双索引 McBride 式仿函数 class:

type (f :: q -> r -> *) ~~> (g :: q -> r -> *) =
  forall (i :: q) (j :: r) . f i j -> g i j

class TFunctor t where
  tmap :: (c ~~> d) -> (t c ~~> t d)

可以描述适用于类型对齐序列的映射、折叠和遍历：

class TFoldable t where
  tfoldMap :: Category d => (c ~~> d) -> t c ~~> d
  tfoldMap f = tfoldr (\cij djk -> f cij >>> djk) id

class (TFunctor t, TFoldable t) => TTraversable t where
  ttraverse :: IxApplicative f
            => (forall x y . c x y -> f x y (d x y))
            -> (t c p q -> f p q (t d p q))

现在证明可以为类型对齐序列定义 Data.Functor.Reverse 的一个版本。具体

newtype Reverse t c x y = Reverse {unReverse :: t (Dual c) y x}

哪里

newtype Dual c x y = Dual {getDual :: c y x}

当类型 t 实际上是一个类型对齐序列时，直接给 Reverse t 类型对齐序列操作的完整补充。

实际问题

我不清楚的是 t 成为 IxTraversable 是否足以实现 IxTraversable (Reverse t)。我尝试过的一切都碰壁了。对于标准 Traversables，这可以使用 Backwards 应用程序来完成。有一个 IxBackwards 可用，但它似乎没有帮助。对于标准 Traversables，可以将容器内容转储到列表中，然后从列表中拉回。但这在这里似乎是不可能的，因为没有明显的方法来记录输出的类型并确保它们在输入时匹配。我错过了什么，或者这是不行的？

最简单的开始：

instance IxTraversable t => IxTraversable (Reverse t) where
  ttraverse f (Reverse xs) = Reverse `ixmap` _ xs

这让我得到了一个类型的洞

t (Dual c) q p -> f p q (t (Dual d) q p)

明显的挑战是我们有 t _ q p，但是 f p q _。所以如果有办法做到这一点，我们大概需要想出一个 f 来翻转事物。正如我之前所说，有一个 IxBackwards

newtype IxBackwards f y x a = IxBackwards { ixforwards :: f x y a }

但我看不出这有什么帮助。

Answer 1

您的设置很合理，IxBackwards 很有用（事实上，很关键）- 您运行遇到的问题是这两个事实Dual 和 Reverse 交换类型变量的位置，而 ttraverse 的第一个参数需要量化类型变量 (x,y) 到 'agree' 的位置感觉。您必须同时 'flip' 使用 both Dual 和 IxBackwards:

对 ttraverse 的递归调用中的这些变量

instance TTraversable t => TTraversable (Reverse t) where

  ttraverse f = 
    ixmap Reverse . ixforwards . 
    ttraverse (IxBackwards . ixmap Dual . f . getDual) . 
    unReverse

编写 TFunctor 和 TFoldable 的实例可能会提示如何找到此实现：

dualNat2 :: (c ~~> d) -> Dual c ~~> Dual d 
dualNat2 k (Dual x) = Dual $ k x 

instance TFunctor f => TFunctor (Reverse f) where 
  tmap f (Reverse q) = Reverse $ tmap (dualNat2 f) q 

instance TFoldable f => TFoldable (Reverse f) where 
  tfoldMap k (Reverse z) = getDual $ tfoldMap (dualNat2 k) z

你基本上在 TTraversable 的情况下做同样的事情，除了现在有两个索引要翻转：

f                                      :: forall x y . c x y -> f x y (d x y)   
ixmap Dual . f . getDual               :: forall x y . Dual c y x -> f x y (Dual d y x)
IxBackwards . f                        :: forall x y . c x y -> IxBackwards f y x (d x y)
IxBackwards . ixmap Dual . f . getDual :: forall x y . Dual c y x -> IxBackwards f y x (Dual d y x)

请注意，如果您只翻转其中一个索引，函数的类型甚至与 ttraverse.

的参数类型不匹配

我将尝试使用 Typed Holes 进行逐步推导。

从这个骨架开始，我认为推导它很简单：

  ttraverse f = 
    ixmap Reverse .  
    ttraverse _trfun . 
    unReverse

这给出了类型错误：

Couldn't match type `q' with `p'
...
Expected type: Reverse t c p q -> f p q (Reverse t d p q)
Actual type: Reverse t c q p -> f p q (Reverse t d q p)
* In the expression: ixmap Reverse . ttraverse _trfun . unReverse

所以在编译之前添加更多的漏洞。我的第一直觉是在前面添加另一个洞（因为类型错误是针对整个表达式的，所以必须对整个表达式做一些事情以使其进行类型检查）：

  ttraverse f = 
    _out . ixmap Reverse .  
    ttraverse _trfun . 
    unReverse

现在我们没有类型错误（忽略 'ambiguous type' 形式的 C x 错误，其中 C 是 class - 有错误）并且报告的类型是

 _out :: f0 q p (Reverse t c0 p q) -> f p q (Reverse t d p q)

其中 f0, c0 是（当前）自由类型变量，我们利用它来发挥我们的优势！如果我们让 c0 ~ d 和 f0 ~ IxBackwards f 那么这正是 ixforwards 的类型 - 所以让我们试试看：

  ttraverse f = 
    ixforwards . ixmap Reverse .  
    ttraverse _trfun . 
    unReverse

现在我们得到一个很好的单态推断类型：

 _trfun :: Dual c x y -> IxBackwards f x y (Dual d x y)
 * Relevant bindings include
     f :: forall (x :: r) (y :: r). c x y -> f x y (d x y)

现在我也假设 _trfun 应该以某种方式使用 f 是显而易见的，所以让我们试试看。我们注意到 f 的域和范围都不完全是 _trfun 的域和范围，因此我们在两侧放置一个洞：

  ttraverse f = 
    ixforwards . ixmap Reverse .  
    ttraverse (_out . f . _in) . 
    unReverse

并得到：

_out :: f x0 y0 (d x0 y0) -> IxBackwards f x y (Dual d x y)
_in :: Dual c x y -> c x0 y0

其中 x0, y0 是自由变量。可能最明显的是 x0 ~ y, y0 ~ x，我们有 _in = getDual，所以我们尝试这样做，并得到一个新的推断类型：

_out :: f y x (d y x) -> IxBackwards f x y (Dual d x y)

现在很明显可以看到类型变量在两个不同的地方 'flipped'；一次 IxBackwards，一次 Dual。翻转第一对索引的方式最明显（大概）：

  ttraverse f = 
    ixforwards . ixmap Reverse .  
    ttraverse (_out . IxBackwards . f . getDual) . 
    unReverse

并得到：

_out :: IxBackwards f x y (d y x) -> IxBackwards f x y (Dual d x y)

现在我们有了 q A -> q B 和 IxFunctor q 形式的东西，所以设置 _out = ixmap _out 我们得到

_out :: d y x -> Dual d x y

并且有一个这种类型的简单函数 - 即 Dual - 它完成了定义：

  ttraverse f = 
    ixforwards . ixmap Reverse .  
    ttraverse (ixmap Dual . IxBackwards . f . getDual) . 
    unReverse

请注意，与原始版本相比，某些功能组合是如何翻转的 - 我假装我不知道答案先验并在 'most obvious' 中推导出它方式，首先填写最简单的东西。这两个定义是等价的（真正等价的，因为 Dual 和 IxBackwards 都是 newtype）。

是否可以反转类型对齐的遍历？

Is it possible to reverse type-aligned traversals?

haskell

dependent-type

实际问题