Idris：为长度为 Fin 而不是 Nat 的向量编写初始段函数

Question

我正在尝试为向量编写一个初始段函数，它将向量的长度存储为 Fin 而不是 Nat，如下所示：

vectorsInits : Vect n t -> Vect n (p ** Vect (finToNat p) t)
vectorsInits Nil = Nil
vectorsInits (x::xs) = ((FS FZ) ** (x::Nil)) :: map (\(p ** ys) => ((FS p) ** x::ys)) (vectorsInits xs)

这个定义不起作用，因为我收到以下类型错误：

When checking right hand side of vectorsInits with expected type

    Vect (S len) (p : Fin n ** Vect (finToNat p) t)

When checking argument pf to constructor Builtins.MkDPair:

    Type mismatch between

            Vect 1 t (Type of [x])

    and

            Vect (finToNat (FS FZ)) t (Expected type)

    Specifically:

            Type mismatch between

                    1

            and

                    finToNat (FS FZ)

但是finToNat的定义很明确，finToNat (FS FZ) 等于1,。即使我编写以下函数来尝试让 idris 意识到它们相等，我也会收到错误消息：

intproof : Vect 1 t -> Vect (finToNat (FS FZ)) t 
intproof x = x
...
vectorsInits (x::xs) = ((FS FZ) ** intproof (x::Nil)) :: map (\(p ** ys) => ((FS p) ** x::ys)) (vectorsInits xs)

给我错误：

When checking right hand side of vectorsInits with expected type
        Vect (S len) (p : Fin n ** Vect (finToNat p) t)
When checking argument pf to constructor Builtins.MkDPair:
    Type mismatch between
            Vect (finToNat (FS FZ)) t (Type of intproof [x])
    and
            (\p => Vect (finToNat p) t) (FS FZ) (Expected type)
    Specifically:
            Type mismatch between
                    1
            and
                    finToNat (FS FZ)

连写：

intproof : Vect 1 t -> (\p => Vect (finToNat p) t) (FS FZ)
intproof x = x

得到与上面相同的错误

我有 %default total 并且我正在文件开头导入 Data.Vect。

有没有办法强制Idris识别finToNat(FS FZ)等于1（即S Z））？

谢谢

Answer 1

您有问题：

vectorsInits : Vect n t -> Vect n (p ** Vect (finToNat p) t)

p 的类型是什么？你还没给，结果居然是

vectorsInits : Vect n t -> Vect n (p : Fin m ** Vect (finToNat p) t)

也就是说，你数据旁边的Fins 运行的类型，与输入完全无关。那是不对的。它应该（至少）是

vectorsInits : Vect n t -> Vect n (p : Fin n ** Vect (finToNat p) t)

然而，这也不完全正确。应该发生的是 Fins 在您向下输出时从 FZ 计数到 last，但您当前的实现不会那样做。如果你改变它这样做，你会注意到每个输出向量最终的长度比索引大一：

vectorsInits : Vect n t -> Vect n (p : Fin n ** Vect (S (finToNat p)) t)
vectorsInits [] = []
vectorsInits (x :: xs) = (FZ ** [x]) :: map (\(idx ** ixs) => (FS idx ** x :: ixs)) (vectorsInits xs)

或者，您可以在输出的开头附加一个 []（毕竟，[] 是每个列表的前缀），从而得到一个符合身份的版本 index n (vectorInits xs) = take n xs（省略了一些修改）：

vectorsInits : Vect n t -> Vect (S n) (p : Fin (S n) ** Vect (finToNat p) t) 
vectorsInits [] = [(FZ ** [])] 
vectorsInits (x :: xs) = (FZ ** []) :: map (\(idx ** ixs) => (FS idx ** x :: ixs)) (vectorsInits xs)

Idris：为长度为 Fin 而不是 Nat 的向量编写初始段函数

Idris: Writing an initial segments function for vectors with length as a Fin rather than a Nat

idris