Так как _+_
-Operation для Nat
обычно определяется рекурсивно в первом аргументе, его очевидно нетривиально для проверки типа, чтобы знать, что i + 0 == i
. Тем не менее, я часто сталкиваюсь с этой проблемой при записи функций на Vectors с фиксированным размером.
Один пример: как определить функцию Agda
swap : {A : Set}{m n : Nat} -> Vec A (n + m) -> Vec A (m + n)
который помещает первые n
значения в конец вектора?
Так как простое решение в Haskell было бы
swap 0 xs = xs
swap n (x:xs) = swap (n-1) (xs ++ [x])
Я попробовал это аналогично в Agda следующим образом:
swap : {A : Set}{m n : Nat} -> Vec A (n + m) -> Vec A (m + n)
swap {_} {_} {zero} xs = xs
swap {_} {_} {suc i} (x :: xs) = swap {_} {_} {i} (xs ++ (x :: []))
Но сбой проверки типа с сообщением (относящимся к {zero}
-case в приведенном выше swap
-Definition):
.m != .m + zero of type Nat
when checking that the expression xs has type Vec .A (.m + zero)
Итак, мой вопрос: как научить Агда, что m == m + zero
? И как написать такую функцию swap
в Agda?