CODEWITHSUNDEEP
agda
Marko Grdinić
Marko Grdinić

Reputation: 4062

Is there an element-in-list datatype defined in the standard library?

data _[_]=_ {A : Set a} : ∀ {n} → Vec A n → Fin n → A → Set a where
  here  : ∀ {n}     {x}   {xs : Vec A n} → x ∷ xs [ zero ]= x
  there : ∀ {n} {i} {x y} {xs : Vec A n}
          (xs[i]=x : xs [ i ]= x) → y ∷ xs [ suc i ]= x

This is for Vec, but I can't find an analogous one for List.

Upvotes: 1

Views: 164

Answers (1)

Marko Grdinić
Marko Grdinić

Reputation: 4062

It is available in a more generic form in Data.List.Relation.Unary.Any. Here is how it is defined.

data Any {A : Set a} (P : Pred A p) : Pred (List A) (a ⊔ p) where
  here  : ∀ {x xs} (px  : P x)      → Any P (x ∷ xs)
  there : ∀ {x xs} (pxs : Any P xs) → Any P (x ∷ xs)

Here is an example of it in use.

open import Relation.Nullary
open import Relation.Binary.PropositionalEquality
open import Data.List
open import Data.List.Relation.Unary.Any

data NonRepeating {a} {A : Set a} : (l : List A) → Set a where
  done : NonRepeating []
  rest : ∀ {x xs} → ¬ Any (x ≡_) xs → NonRepeating xs → NonRepeating (x ∷ xs)

record UniqueList {a} (A : Set a) : Set a where
  constructor _//_
  field
    l : List A
    wf : NonRepeating l

Upvotes: 2

Related Questions