Comment utiliser les paires dépendantes

Question

Supposons que j'ai une fonction (elle fait vraiment ce que son nom dit) :

filter : ∀ {A n} → (A → Bool) → Vec A n → ∃ (λ m → Vec A m)

Maintenant, j'aimerais travailler d'une manière ou d'une autre avec la paire dépendante que je reviens.j'ai écrit simple head fonction:

head :: ∀ {A} → ∃ (λ n → Vec A n) → Maybe A
head (zero   , _ )       = nothing
head (succ _ , (x :: _)) = just x

ce qui bien sûr fonctionne parfaitement.Mais ça m'a fait me demander :Y a-t-il un moyen de m'assurer que la fonction ne peut être appelée qu'avec n ≥ 1?

Idéalement, j'aimerais faire fonctionner head : ∀ {A} → ∃ (λ n → Vec A n) → IsTrue (n ≥ succ zero) → A;mais cela échoue, parce que n est hors de portée lorsque je l'utilise dans IsTrue.

Merci pour votre temps!

---

IsTrue c'est quelque chose comme :

data IsTrue : Bool → Set where
  check : IsTrue true

Answer 1

Je pense que c'est une question sur l'inconvénient. La bibliothèque standard fournit des inconvénients Fonctions pour les produits, voir Uncurry . Pour votre situation, il serait plus utile d'avoir une fonction incontrôlante où le premier L'argument est caché, car une fonction de tête prendrait normalement l'indice de longueur comme un argument implicite. Nous pouvons écrire une fonction d'inconvénients comme celle-là:

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

La fonction qui renvoie la tête d'un vecteur s'il n'y en a pas ne semble pas exister dans la bibliothèque standard, Nous en écrivons donc:

maybe-head : ∀ {a n} {A : Set a} → Vec A n → Maybe A
maybe-head []       = nothing
maybe-head (x ∷ xs) = just x

Maintenant, votre fonction souhaitée est juste une question d'inconvénération de la Peut-être-la fonction avec le premier argument-implicite-neige fonction définie ci-dessus:

maybe-filter-head : ∀ {A : Set} {n} → (A → Bool) → Vec A n → Maybe A
maybe-filter-head p = uncurryʰ maybe-head ∘ filter p

Conclusion: Les produits dépendants du curry et des inconvénients liés à leurs versions non dépendantes.

Encourage de côté, la fonction que vous souhaitez écrire avec la signature de type

head : ∀ {A} → ∃ (λ n → Vec A n) → IsTrue (n ≥ succ zero) → A

peut être écrit comme suit:

head : ∀ {A} → (p : ∃ (λ n → Vec A n)) → IsTrue (proj₁ p ≥ succ zero) → A

Answer 2

Le meilleur moyen est probablement de déstructurer d'abord la paire dépendante, de sorte que vous puissiez simplement écrire:

head :: ∀ {A n} → Vec A (S n) → A

Toutefois, si vous voulez vraiment garder la paire dépendante intacte dans la signature de fonction, vous pouvez écrire un POSN de prédicat qui inspecte le premier élément de la paire et vérifie qu'il est positif:

head :: ∀ {A p} → PosN p -> A

ou similaire.Je laisserai la définition de POSN comme un exercice au lecteur.C'est essentiellement ce que la réponse de Vitaus fait déjà, mais un prédicat plus simple peut être défini à la place.

Answer 3

Après avoir joué avec elle depuis un certain temps, je suis proposé une solution qui ressemble à la fonction que je voulais en premier lieu:

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

Si quelqu'un propose une meilleure solution (ou plus générale), j'accepterai volontiers leur réponse.Les commentaires sont aussi les bienvenus.

---

Voici plus de prédicat général que j'ai proposé:

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
  ...

Answer 4

C'est comme d'habitude head fonction pour Vec.

head' : ∀ {α} {A : Set α} → ∃ (λ n → Vec A (suc n)) → A
head' (_ , x ∷ _) = x