为具有翻转类型参数的用户定义版本的 Vect 实现 Foldable

Question

我自己定义的Vect数据类型如下

data MyVect : (n : Nat) -> (t : Type) -> Type where
  Nil  : MyVect Z t
  (::) : (x : t) -> (xs : MyVect n t) -> MyVect (S n) t

然后开始实现数据类型的Foldable接口

Foldable MyVect where
  foldr = ?res2

然而，当重新加载文件时，Idris 抱怨

When checking argument t to type constructor Prelude.Foldable.Foldable:
        Type mismatch between
                Nat -> Type -> Type (Type of MyVect)
        and
                Type -> Type (Expected type)

        Specifically:
                Type mismatch between
                        Nat
                and
                        TypeUnification failure

摸索了一下，我猜想我可以通过编写

来满足 Idris 对类型构造函数的要求

Foldable (MyVect n) where
  foldr = ?res2

然后我开始思考"what if I had defined MyVect with the type parameters flipped?..."

data MyVect : (t : Type) -> (n : Nat) -> Type where
  Nil  : MyVect t Z
  (::) : (x : t) -> (xs : MyVect t n) -> MyVect t (S n)

是否可以为 MyVect 的 'parameter-flipped' 版本实现 Foldable 接口？（以及如何？）

Answer 1

您看到的类型错误来源是 Foldable 的类型：

Idris> :t Foldable 
Foldable : (Type -> Type) -> Type

而您的 MyVect 的第一个版本具有类型：

Idris> :t MyVect 
MyVect : Nat -> Type -> Type

第二个有：

Idris> :t MyVect 
MyVect : Type -> Nat -> Type

你是对的，你可以部分应用类型，就像你可以使用普通的旧函数一样。

因此 Foldable (MyVect n) 有效，因为 MyVect n 具有类型 Type -> Type，这正是 Foldable 接口想要的类型。

在我们说服自己类型的行为类似于函数之后，您可以为 MyVect 提供翻转的类型别名，一切都会起作用：

FlippedVect : Nat -> Type -> Type
FlippedVect n t = MyVect t n

Foldable (FlippedVect n) where

您也可以使用已经定义的函数来实现类似的东西：

Idris> :t flip
flip : (a -> b -> c) -> b -> a -> c
Idris> :t flip MyVect
flip MyVect : Nat -> Type -> Type

现在你可以写：

Foldable (flip MyVect n) where

您甚至可以为匿名函数定义实例。这是完整版本：

Foldable (\a => MyVect a n) where
  foldr f z Nil = z
  foldr {n=S k} f z (x :: xs) = x `f` foldr {t=\a => MyVect a k} f z xs

  foldl = believe_me  -- i'm on Idris-0.12.3, I got type errors for `foldl`
                      -- but you can implement it in the same way

在写了所有这些信息来教你如何去做之后，我应该说在任何情况下你绝对不应该这样做。

为具有翻转类型参数的用户定义版本的 Vect 实现 Foldable

Implementing Foldable for a user defined version of Vect with flipped type parameters

idris