Как использовать зависимые пары
-
09-12-2019 - |
Вопрос
Предположим, у меня есть функция (она действительно делает то, что говорит название):
filter : ∀ {A n} → (A → Bool) → Vec A n → ∃ (λ m → Vec A m)
Теперь мне хотелось бы как-то поработать с зависимой парой, которую я возвращаю.я написал просто head
функция:
head :: ∀ {A} → ∃ (λ n → Vec A n) → Maybe A
head (zero , _ ) = nothing
head (succ _ , (x :: _)) = just x
что, конечно, работает отлично.Но это заставило меня задуматься:Есть ли способ убедиться, что функцию можно вызывать только с помощью n ≥ 1
?
В идеале я хотел бы сделать функцию head : ∀ {A} → ∃ (λ n → Vec A n) → IsTrue (n ≥ succ zero) → A
;но это не получается, потому что n
выходит за рамки, когда я использую его в IsTrue
.
Спасибо за ваше время!
IsTrue
это что-то вроде:
data IsTrue : Bool → Set where
check : IsTrue true
Решение
Я думаю, что это вопрос о нетерпении.Стандартная библиотека обеспечивает функции рассеяния продуктов, см. необузданный.Для вашей ситуации было бы более полезно иметь функцию раскрытия, где первый аргумент скрыт, поскольку функция головы обычно принимает индекс длины в качестве неявного аргумента.Мы можем написать такую функцию uncurry:
uncurryʰ : ∀ {a b c} {A : Set a} {B : A → Set b} {C : (a : A) → B a → Set c} →
({x : A} → (y : B x) → C x y) →
((p : Σ A B) → uncurry C p)
uncurryʰ f (x , y) = f {x} y
Функция, которая возвращает голову вектора, если есть, кажется, в стандартной библиотеке не существует, поэтому мы пишем ее:
maybe-head : ∀ {a n} {A : Set a} → Vec A n → Maybe A
maybe-head [] = nothing
maybe-head (x ∷ xs) = just x
Теперь ваша желаемая функция является лишь вопросом разъединения функции, возможно, с головой, с помощью функции первого аргумента-импульса, определяемой выше:
maybe-filter-head : ∀ {A : Set} {n} → (A → Bool) → Vec A n → Maybe A
maybe-filter-head p = uncurryʰ maybe-head ∘ filter p
Заключение:зависимые продукты с удовольствием карри и не карри, как и их независимые версии.
Не отвлекаясь, функция, которую вы хотите написать с сигнатурой типа
head : ∀ {A} → ∃ (λ n → Vec A n) → IsTrue (n ≥ succ zero) → A
Можно записать как:
head : ∀ {A} → (p : ∃ (λ n → Vec A n)) → IsTrue (proj₁ p ≥ succ zero) → A
Другие советы
Вероятно, лучший способ — сначала деструктурировать зависимую пару, чтобы можно было просто написать:
head :: ∀ {A n} → Vec A (S n) → A
Однако, если вы действительно хотите сохранить зависимую пару в сигнатуре функции, вы можете написать предикат PosN, который проверяет первый элемент пары и проверяет, что он положителен:
head :: ∀ {A p} → PosN p -> A
или похожие.Я оставлю определение PoSN в качестве упражнения для читателя.По сути, это то, что уже делает ответ Витуса, но вместо этого можно определить более простой предикат.
Поиграв с ним некоторое время, я нашел решение, напоминающее функцию, которую я хотел в первую очередь:
data ∃-non-empty (A : Set) : ∃ (λ n → Vec A n) → Set where
∃-non-empty-intro : ∀ {n} → {x : Vec A (succ n)} → ∃-non-empty A (succ n , x)
head : ∀ {A} → (e : ∃ (λ n → Vec A n)) → ∃-non-empty A e → A
head (zero , []) ()
head (succ _ , (x :: _)) ∃-non-empty-intro = x
Если кто-нибудь предложит лучшее (или более общее) решение, я с радостью приму его ответ.Комментарии тоже приветствуются.
Вот более общий предикат, который я придумал:
data ∃-succ {A : Nat → Set} : ∃ A → Set where
∃-succ-intro : ∀ {n} → {x : A (succ n)} → ∃-succ (succ n , x)
-- or equivalently
data ∃-succ {A : Nat → Set} : ∃ (λ n → A n) → Set where
...
Это как обычно head
функция для Vec
.
head' : ∀ {α} {A : Set α} → ∃ (λ n → Vec A (suc n)) → A
head' (_ , x ∷ _) = x