Library Coq.Lists.SetoidList
Logical relations over lists with respect to a setoid equality
or ordering.
This can be seen as a complement of predicate
lelistA and
sort
found in
Sorting.
Being in a list modulo an equality relation over type A.
TODO: it would be nice to have a generic definition instead
of the previous one. Having InA = Exists eqA raises too
many compatibility issues. For now, we only state the equivalence:
An alternative definition of InA.
A list without redundancy modulo the equality over A.
An alternative definition of NoDupA based on ForallOrdPairs
lists with same elements modulo eqA
lists with same elements modulo eqA at the same place
We could also have written eqlistA = Forall2 eqA.
Results concerning lists modulo eqA
First, the two notions equivlistA and eqlistA are indeed equivlances
Moreover, eqlistA implies equivlistA. A reverse result
will be proved later for sorted list without duplicates.
InA is compatible with eqA (for its first arg) and with
equivlistA (and hence eqlistA) for its second arg
For compatibility, an immediate consequence of InA_compat
Some more facts about InA
Fold with restricted transpose hypothesis.
Compatibility of ForallOrdPairs with respect to inclA.
Two-argument functions that allow to reorder their arguments.
A version of transpose with restriction on where it should hold
we now state similar results, but without restriction on transpose.
Results concerning lists modulo eqA and ltA
For compatibility, can be deduced from InfA_compat
Lemma InfA_eqA l x y :
eqA x y ->
InfA y l ->
InfA x l.
Hint Immediate InfA_ltA InfA_eqA.
Lemma SortA_InfA_InA :
forall l x a,
SortA l ->
InfA a l ->
InA x l ->
ltA a x.
Lemma In_InfA :
forall l x, (
forall y,
In y l ->
ltA x y) ->
InfA x l.
Lemma InA_InfA :
forall l x, (
forall y,
InA y l ->
ltA x y) ->
InfA x l.
Lemma InfA_alt :
forall l x,
SortA l -> (
InfA x l <-> (forall y,
InA y l ->
ltA x y)).
Lemma InfA_app :
forall l1 l2 a,
InfA a l1 ->
InfA a l2 ->
InfA a (
l1++l2).
Lemma SortA_app :
forall l1 l2,
SortA l1 ->
SortA l2 ->
(
forall x y,
InA x l1 ->
InA y l2 ->
ltA x y) ->
SortA (
l1 ++ l2).
Lemma SortA_NoDupA :
forall l,
SortA l ->
NoDupA l.
Some results about eqlistA
For compatibility, can be deduced from app_eqlistA_compat
A few things about filter
Section Filter.
Lemma filter_sort :
forall f l,
SortA l ->
SortA (
List.filter f l).
Lemma filter_InA :
forall f,
Proper (
eqA==>eq)
f ->
forall l x,
InA x (
List.filter f l)
<-> InA x l /\ f x = true.
Lemma filter_split :
forall f, (
forall x y,
f x = true ->
f y = false ->
ltA x y) ->
forall l,
SortA l ->
l = filter f l ++ filter (
fun x=>
negb (
f x))
l.
End Filter.
End Type_with_equality.
Hint Constructors InA eqlistA NoDupA sort lelistA.
Section Find.
Variable A B :
Type.
Variable eqA :
A ->
A ->
Prop.
Hypothesis eqA_equiv :
Equivalence eqA.
Hypothesis eqA_dec :
forall x y :
A,
{eqA x y}+{~(eqA x y)}.
Fixpoint findA (
f :
A ->
bool) (
l:
list (
A*B)) :
option B :=
match l with
|
nil =>
None
|
(a,b)::l =>
if f a then Some b else findA f l
end.
Lemma findA_NoDupA :
forall l a b,
NoDupA (
fun p p´ =>
eqA (
fst p) (
fst p´))
l ->
(
InA (
fun p p´ =>
eqA (
fst p) (
fst p´)
/\ snd p = snd p´)
(a,b) l <->
findA (
fun a´ =>
if eqA_dec a a´ then true else false)
l = Some b).
End Find.
Compatibility aliases. Proper is rather to be used directly now.