Come usare le coppie dipendenti

Question

Supponiamo di avere una funzione (fa davvero ciò che dice il nome):

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

.

Ora, vorrei in qualche modo lavorare con la coppia dipendente che ritorni.Ho scritto una semplice funzione head:

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

.

che ovviamente funziona perfettamente.Ma mi ha fatto chiesto: c'è un modo in cui posso assicurarmi che la funzione possa essere chiamata solo con n ≥ 1?

Idealmente, mi piacerebbe rendere la funzione head : ∀ {A} → ∃ (λ n → Vec A n) → IsTrue (n ≥ succ zero) → A;Ma questo fallisce, perché n è fuori portata quando lo uso in IsTrue.

Grazie per il tuo tempo!

---

.

IsTrue è qualcosa come:

data IsTrue : Bool → Set where
  check : IsTrue true

.

Answer 1

Penso che questa sia una domanda sull'inconveniente. La Biblioteca Standard fornisce irregolarità Funzioni per i prodotti, vedere Undury . Per la tua situazione, sarebbe più vantaggioso avere una funzione non corretta dove il primo L'argomento è nascosto, poiché una funzione della testa richiederebbe normalmente l'indice della lunghezza come argomento implicito. Possiamo scrivere una funzione non corretta del genere:

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 funzione che restituisce la testa di un vettore se ce n'è uno non sembra esistere nella libreria standard, Quindi scriviamo uno:

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

.

Ora la tua funzione desiderata è solo una questione di unire Funzione forse-testa con il primo argomento-implicito-incurrato Funzione definita sopra:

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

.

Conclusione: i prodotti dipendenti sono volentieri al curry e non correttamente come le loro versioni non dipendenti.

Unviso a parte, la funzione che si desidera scrivere con il tipo di firma

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

.

può essere scritto come:

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

.

Answer 2

Il modo migliore è probabilmente per distruggere prima la coppia dipendente, in modo da poter scrivere solo:

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

.

Tuttavia, se vuoi veramente mantenere la coppia dipendente intatta nella firma della funzione, è possibile scrivere un predicato POSN che ispeziona il primo elemento della coppia e controlla che è positivo:

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

.

o simili.Lascerò la definizione di posn come esercizio al lettore.Essenzialmente questa è ciò che è già la risposta di Vito, ma è possibile definire un predicato più semplice.

Answer 3

Dopo aver giocato con esso per un po 'di tempo, ho inventato la soluzione che assomiglia alla funzione che volevo al primo posto:

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

.

Se qualcuno ha una soluzione migliore (o più generale), accetterò volentieri la loro risposta.I commenti sono benvenuti anche.

---

.

Ecco il predicato più generale che ho trovato:

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

Questa è come la solita funzione head per Vec.

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

.