------------------------------------------------------------------------
-- The Agda standard library
--
-- First generalizes the idea that an element is the first in a list to
-- satisfy a predicate.
------------------------------------------------------------------------
{-# OPTIONS --cubical-compatible --safe #-}
module Data.List.Relation.Unary.First {a} {A : Set a} where
open import Level using (_⊔_)
open import Data.Fin.Base as Fin using (Fin; zero; suc)
open import Data.List.Base as List using (List; []; _∷_)
open import Data.List.Relation.Unary.All as All using (All; []; _∷_)
open import Data.List.Relation.Unary.Any as Any using (Any; here; there)
open import Data.Product.Base using (∃; -,_; _,_)
open import Data.Sum.Base as Sum using (_⊎_; inj₁; inj₂)
open import Function.Base using (id; _∘′_)
open import Relation.Unary
open import Relation.Nullary.Negation.Core using (¬_; contradiction)
------------------------------------------------------------------------
-- Basic type.
module _ {p q} (P : Pred A p) (Q : Pred A q) where
infix 1 _++_∷_
infixr 5 _∷_
data First : Pred (List A) (a ⊔ p ⊔ q) where
[_] : ∀ {x xs} → Q x → First (x ∷ xs)
_∷_ : ∀ {x xs} → P x → First xs → First (x ∷ xs)
data FirstView : Pred (List A) (a ⊔ p ⊔ q) where
_++_∷_ : ∀ {xs y} → All P xs → Q y → ∀ ys → FirstView (xs List.++ y ∷ ys)
------------------------------------------------------------------------
-- map
module _ {p q r s} {P : Pred A p} {Q : Pred A q} {R : Pred A r} {S : Pred A s} where
map : P ⊆ R → Q ⊆ S → First P Q ⊆ First R S
map p⇒r q⇒r [ qx ] = [ q⇒r qx ]
map p⇒r q⇒r (px ∷ pqxs) = p⇒r px ∷ map p⇒r q⇒r pqxs
module _ {p q r} {P : Pred A p} {Q : Pred A q} {R : Pred A r} where
map₁ : P ⊆ R → First P Q ⊆ First R Q
map₁ p⇒r = map p⇒r id
map₂ : Q ⊆ R → First P Q ⊆ First P R
map₂ = map id
refine : P ⊆ Q ∪ R → First P Q ⊆ First R Q
refine f [ qx ] = [ qx ]
refine f (px ∷ pqxs) with f px
... | inj₁ qx = [ qx ]
... | inj₂ rx = rx ∷ refine f pqxs
module _ {p q} {P : Pred A p} {Q : Pred A q} where
------------------------------------------------------------------------
-- Operations
empty : ¬ First P Q []
empty ()
tail : ∀ {x xs} → ¬ Q x → First P Q (x ∷ xs) → First P Q xs
tail ¬qx [ qx ] = contradiction qx ¬qx
tail ¬qx (px ∷ pqxs) = pqxs
index : First P Q ⊆ (Fin ∘′ List.length)
index [ qx ] = zero
index (_ ∷ pqxs) = suc (index pqxs)
index-satisfied : ∀ {xs} (pqxs : First P Q xs) → Q (List.lookup xs (index pqxs))
index-satisfied [ qx ] = qx
index-satisfied (_ ∷ pqxs) = index-satisfied pqxs
satisfied : ∀ {xs} → First P Q xs → ∃ Q
satisfied pqxs = -, index-satisfied pqxs
satisfiable : Satisfiable Q → Satisfiable (First P Q)
satisfiable (x , qx) = List.[ x ] , [ qx ]
------------------------------------------------------------------------
-- Decidability results
first : Π[ P ∪ Q ] → Π[ First P Q ∪ All P ]
first p⊎q [] = inj₂ []
first p⊎q (x ∷ xs) with p⊎q x
... | inj₁ px = Sum.map (px ∷_) (px ∷_) (first p⊎q xs)
... | inj₂ qx = inj₁ [ qx ]
------------------------------------------------------------------------
-- Relationship with Any
module _ {q} {Q : Pred A q} where
fromAny : Any Q ⊆ First U Q
fromAny (here qx) = [ qx ]
fromAny (there any) = _ ∷ fromAny any
toAny : ∀ {p} {P : Pred A p} → First P Q ⊆ Any Q
toAny [ qx ] = here qx
toAny (_ ∷ pqxs) = there (toAny pqxs)
RetroSearch is an open source project built by @garambo | Open a GitHub Issue
Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo
HTML:
3.2
| Encoding:
UTF-8
| Version:
0.7.4