Idris 中的向量切片列表

Question

我正在练习 Idris，我想从向量中获取切片列表。

首先，我定义了以下 window 函数，其中 returns m 个元素从索引 i 开始（即 xs[i:i+m]）：

import Data.Vect

window : (i : Nat) -> (m : Nat) -> Vect (i + (m + n)) t -> Vect m t
window i m xs = take m (drop i xs)

编译得很好：

> window 0 3 [1,2,3,4,5]
[1, 2, 3] : Vect 3 Integer

现在，例如，我希望 ys 包含 2 个大小为 3 的切片，每个切片从 i:

开始

xs : Vect 5 Int
xs = [1,2,3,4,5]

ys : List (Vect 3 Int)
ys = [window i 3 xs | i <- [0,2]]

但是，我得到以下类型不匹配：

   |
   | ys = [window i 3 xs | i <- [0,2]]
   |       ~~~~~~~~~~~~~
When checking right hand side of ys with expected type
        List (Vect 3 Int)

When checking an application of function Main.window:
        Type mismatch between
                Vect 5 Int (Type of xs)
        and
                Vect (i + (3 + n)) Int (Expected type)

        Specifically:
                Type mismatch between
                        5
                and
                        plus i (plus 3 n)

我希望 i 与 [0,2] 的值统一，即：

ys = [window 0 3 xs, window 2 3 xs]

我对window的定义错了吗？

Answer 1

由于隐式参数，这里的列表推导与直写不一样

[window 0 3 xs, window 2 3 xs]

Idris 的 elaborator 将上面的内容变成了

[window 0 3 xs {n=n1}, window 2 3 xs {n=n2}]

开放统一目标：

5 = plus 0 (plus 3 n1)
5 = plus 2 (plus 3 n2)

因为plus对左操作数是递归的，所以它减少了：

S (S (S (S (S Z)))) = S (S (S n1)
S (S (S (S (S Z)))) = S (S (S (S (S n2))))

Unifier 剥离了共享的外层，并发现了两个应用程序 n 的明确阐述。

通过理解，有效地得到：

ys: List (Vect 3 Int)
ys = [0,2] >>= comprehension where
  comprehension: {n: Nat} -> Nat -> List (Vect 3 t)
  comprehension i = pure (window {n} i 3 xs)

值得注意的是，我的 comprehension 类型签名应该清楚：尽管在使用站点有固定输入，comprehension 实际上只是另一个必须适用于所有 的 case 表达式]可能个输入。

Idris 也无法在理解应用程序中推断出 window 的 n：虽然 m 是固定的，但 i 是可变的。解决这个问题的唯一方法是使用 proof-carrying 结构（Vect (i+(m+n))) 以外的某种类型）或显式携带大小证明，这有时会使使用复杂化，但推理仍然有帮助。

Sum3: (i,m,n,s: Nat) -> Type
Sum3 i m n s = s = i + (m + n)

window: (i,m: Nat) -> Sum3 i m n s => Vect s t -> Vect m t
window i m xs = take m (drop i (replace sum3 xs {p = \l => Vect l t}))

此版本的 window 要求调用者提供明确的证明，证明第三个参数的大小 s 等于 i + (m + n)，这对调用者来说有点难看：

ys: List (Vect 3 Int)                                                            
ys = [Answer.window {n} i 3 @{p} xs | (i**n**p) <- [getSum 0, getSum 2]] where    
   getSum: {n: Nat} -> (x: Nat) -> {auto sum3: Sum3 x 3 n (length Question.xs)} ->
      (i: Nat ** n: Nat ** Sum3 i 3 n (length Question.xs))                       
   getSum x = ( x ** n ** sum3 )

Idris 中的向量切片列表

List of vector slices in Idris

dependent-type

idris