为张量类型定义函子实例 (Idris)

Question

我最近一直在学习 Idris，并决定尝试编写一个简单的张量库。我从定义类型开始。

data Tensor : Vect n Nat -> Type -> Type
  Scalar : a -> Tensor [] a
  Dimension : Vect n (Tensor d a) -> Tensor (n::d) a

如您所见，类型 Tensor 由描述张量维度的 Vect 个 Nat 和描述其内容的类型参数化。到目前为止，一切都很好。接下来，我决定尝试将 Tensor 类型设为 Functor.

instance Functor (Tensor d) where
  map f (Scalar x)    = f x
  map f (Dimension x) = map f x

而且 Idris 给了我以下错误。

Unifying `b` and `Tensor [] b` would lead to infinite type

好的。从错误中，我认为问题可能在于 map 的第一个模式过于具体（即，仅当 map 的类型声明接受任何张量时才接受标量）。这看起来很奇怪，但我想我会尝试使用 with 语句重写它。

dimensions : {d : Vect n Nat} -> Tensor d a -> Vect n Nat
dimensions {d} _ = d

instance Functor (Tensor d) where
  map f t with (dimensions t)
    map f (Scalar x)    | []     = f x
    map f (Dimension x) | (_::_) = map f x

但是我得到了同样的错误。我在 Haskell 方面有相当多的经验，但我仍然不太习惯一般依赖类型编程中使用的行话，尤其是 Idris，所以如果能帮助理解错误消息，我将不胜感激。

Answer 1

（注意：从 Idris 0.10 开始，instance 关键字已弃用，应该简单地忽略掉）。

任务是将函数应用于 Scalar 构造函数中的所有元素，但保持结构不变。因此，我们需要将 Scalar 映射到 Scalar 并将 Dimension 映射到 Dimension，并且由于 Dimension 包含递归出现的向量，我们应该使用 Vect 的 map 访问它们。

Functor (Tensor d) where
  map f (Scalar x)     = Scalar (f x)
  map f (Dimension xs) = Dimension (map (map f) xs)

因此，在map (map f) xs中，第一个map用于映射Vect，而map f是递归调用。

为张量类型定义函子实例 (Idris)

Defining Functor Instance for Tensor Type (Idris)

idris