Idris

Question

我正在尝试在 Idris 中实现类似于功能队列的东西，但它带有类型中的元素数量 - 例如 Queue ty n m (n+m) 其中 n 是一个元素的数量Vect n ty，m是一秒内的元素，Vect m ty，(n+m)是总元素。

问题是，在将这些大小作为隐式参数进行操作时，我运行遇到了应用重写规则的问题：

module Queue

import Data.Vect as V

data Queue : Type -> Nat -> Nat -> Nat -> Type where
    mkQueue : (front : V.Vect n ty)
           -> (back : V.Vect m ty)
           -> Queue ty n m (n + m)

%name Queue queue

top : Queue ty n m (S k) -> ty
top {n = S j} {m} {k = j + m} (mkQueue front back) =
    V.head front
top {n = Z} {m = S j} {k = j} (mkQueue front back) =
    V.head $ V.reverse back

bottom : Queue ty n m (S k) -> ty
bottom {m = S j} {n} {k = n + j} (mkQueue front back) = 
    ?some_rewrite_1 (V.head back)
bottom {m = Z} {n = S j} {k = j} (mkQueue front back) = 
    ?some_rewrite_2 (V.head $ V.reverse front)

top 有效，但 bottom 无效。看起来我需要以某种方式提供 plusZeroRightNeutral 和 plusRightSuccRight 重写，但我不确定将它们放在哪里，或者是否有其他选择。以下是错误消息：

bottom 第一行错误：

         Type mismatch between
                 Queue ty n (S j) (n + S j) (Type of mkQueue front back)
         and
                 Queue ty n (S j) (S (n + j)) (Expected type)

         Specifically:
                 Type mismatch between
                         plus n (S j)
                 and
                         S (n + j)

bottom 第二行错误：

         Type mismatch between
                 Queue ty (S j) 0 (S j + 0) (Type of mkQueue front back)
         and
                 Queue ty (S j) 0 (S j) (Expected type)

         Specifically:
                 Type mismatch between
                         plus (S j) 0
                 and
                         S j

个别尺寸告诉我何时需要旋转两个 Vect，整体尺寸告诉我何时有空与非空 Queue，所以我确实想要尽可能跟踪所有信息。

Answer 1

解决此问题的一种可能方法是同时销毁 n。这次 Idris 明白最后一个参数不为零，它基本上是在抱怨：

total
bottom : Queue ty n m (S k) -> ty
bottom {m = S m} {n = S n} (MkQueue _ back) = V.head back
bottom {m = S m} {n = Z}   (MkQueue _ back) = V.head back
bottom {m = Z}   {n = S n} (MkQueue front _) = V.head $ V.reverse front
bottom {m = Z}   {n = Z}   (MkQueue _ _) impossible

附带说明一下，我建议将 top 函数设为总计：

total
top : Queue ty n m (S k) -> ty
top {n = S n}           (MkQueue front _) = V.head front
top {n = Z}   {m = S m} (MkQueue _ back) = V.head $ V.reverse back
top {n = Z}   {m = Z}   (MkQueue _ _) impossible

Idris - 向量队列和重写规则

Idris - Vector Queues and Rewrite Rules

queue

vector