Подпись типа "половина" в Idris

Question

Я довольно новичок в Идрисе и пытаюсь уловить основные понятия и синтаксис.

Даже если это может показаться бессмысленным, я пытаюсь определить half функция, которая наполовину естественная.

Я хочу придумать что-то вроде:

half : (n : Nat) -> (k : Nat) -> (n = k + k) -> (k : Nat)

но, конечно, это не работает. В частности, я получаю:

ошибка: ожидается: подпись зависимого типа

half : (n : Nat) -> (k : Nat) -> (n = k + k) -> (k : Nat)

Является ли это возможным?

Благодарю.

Answer 1

Вы хотите выразить это half n это какой-то Nat Уральский номер k такой, что n = k + k держит. Способ сделать это - использовать сигма-тип, то есть зависимую пару числа k и доказательство n = k + k (это зависимая пара, потому что тип второй координаты, n = k + k зависит от значения первой координаты, k).

Стандартная библиотека Idris определяет DPair для зависимых пар, включая синтаксический сахар, позволяющий писать

half : (n : Nat) -> (k ** n = k + k)

Тем не менее, обратите внимание, что вы не сможете реализовать half (как общая функция), потому что нет хорошего ответа, например, half 1, Может быть, то, что вы хотите, это

half : (n : Nat) -> (k ** Either (n = k + k) (n = k + k + 1))

?

Answer 2

Вы не должны использовать k дважды. половина: (n: Nat) -> (k: Nat) -> (n = k + k) -> Nat правильно, но бесполезно. Я думаю, что вам нужна половина: (n: Nat) -> Может быть (k ** n = k + k)