Library prosa.util.list
From mathcomp Require Import ssreflect ssrbool eqtype ssrnat seq fintype bigop.
Require Export mathcomp.boot.path mathcomp.zify.zify.
Require Import prosa.util.tactics.
Require Export prosa.util.supremum.
Require Export mathcomp.boot.path mathcomp.zify.zify.
Require Import prosa.util.tactics.
Require Export prosa.util.supremum.
Lemma last_undup {T : eqType} (d : T) (xs : seq T) :
last d (undup xs) = last d xs.
Proof. by case/lastP: xs ⇒ [//|ys x]; rewrite undup_rcons !last_rcons. Qed.
last d (undup xs) = last d xs.
Proof. by case/lastP: xs ⇒ [//|ys x]; rewrite undup_rcons !last_rcons. Qed.
The last element is bounded by the maximum.
Lemma last_le_bigmax :
∀ xs, last 0 xs ≤ \max_(x <- xs) x.
Proof.
case⇒ [|x xs]; first by rewrite big_nil.
by apply: leq_bigmax_seq; [exact: mem_last | done].
Qed.
∀ xs, last 0 xs ≤ \max_(x <- xs) x.
Proof.
case⇒ [|x xs]; first by rewrite big_nil.
by apply: leq_bigmax_seq; [exact: mem_last | done].
Qed.
If every element in a set ys is greater than the corresponding element
in another set xs then the maxima of ys is also greater than the
maxima of xs.
Lemma bigmax_leq_nth :
∀ xs ys,
(∀ n, nth 0 xs n ≤ nth 0 ys n) →
(\max_(x <- xs) x) ≤ \max_(y <- ys) y.
Proof.
move⇒ xs ys LE; apply/bigmax_leqP_seq ⇒ x /(nthP 0) [i LT <-] _.
apply: leq_trans (LE i) _.
case: (ltnP i (size ys)) ⇒ LTys; last by rewrite nth_default.
by apply: leq_bigmax_seq; [exact: mem_nth | done].
Qed.
∀ xs ys,
(∀ n, nth 0 xs n ≤ nth 0 ys n) →
(\max_(x <- xs) x) ≤ \max_(y <- ys) y.
Proof.
move⇒ xs ys LE; apply/bigmax_leqP_seq ⇒ x /(nthP 0) [i LT <-] _.
apply: leq_trans (LE i) _.
case: (ltnP i (size ys)) ⇒ LTys; last by rewrite nth_default.
by apply: leq_bigmax_seq; [exact: mem_nth | done].
Qed.
Misc. Additional Lemmas about Sequences
Lemma filter_in_pred0 :
∀ {X : eqType} (xs : seq X) (P : pred X),
(∀ x, x \in xs → ~~ P x) →
filter P xs = [::].
Proof.
move⇒ X xs P NONE; apply/eqP/negPn; rewrite -has_filter.
exact/hasPn.
Qed.
∀ {X : eqType} (xs : seq X) (P : pred X),
(∀ x, x \in xs → ~~ P x) →
filter P xs = [::].
Proof.
move⇒ X xs P NONE; apply/eqP/negPn; rewrite -has_filter.
exact/hasPn.
Qed.
We show that in a unique sequence of size greater than one
there exist two unique elements.
Lemma exists_two :
∀ {X : eqType} (xs : seq X),
size xs > 1 →
uniq xs →
∃ a b, a ≠ b ∧ a \in xs ∧ b \in xs.
Proof.
move⇒ T [|a [|b xs]] //= _ /andP[NA _].
∃ a, b; split; first by apply/eqP; move: NA; rewrite in_cons negb_or ⇒ /andP[].
by split; rewrite !in_cons eqxx ?orbT.
Qed.
∀ {X : eqType} (xs : seq X),
size xs > 1 →
uniq xs →
∃ a b, a ≠ b ∧ a \in xs ∧ b \in xs.
Proof.
move⇒ T [|a [|b xs]] //= _ /andP[NA _].
∃ a, b; split; first by apply/eqP; move: NA; rewrite in_cons negb_or ⇒ /andP[].
by split; rewrite !in_cons eqxx ?orbT.
Qed.
If head 0 xs ≤ x < last 0 xs, then some neighboring elements
bracket x. The sequence xs need not be sorted.
Lemma belonging_to_segment_of_seq_is_total :
∀ (xs : seq nat) (x : nat),
head 0 xs ≤ x < last 0 xs →
∃ n,
n.+1 < size xs
∧ nth 0 xs n ≤ x < nth 0 xs n.+1.
Proof.
move⇒ xs x; elim: xs ⇒ [//|a xs IH].
case: xs IH ⇒ [|b xs] IH /= /andP[ha hl]; first by move: hl; rewrite ltnNge ha.
case: (leqP b x) ⇒ [bx|xb]; last by ∃ 0; split⇒ //; rewrite ha xb.
have /IH [i [ilt hi]] : b ≤ x < last b xs by rewrite bx hl.
by ∃ i.+1; split.
Qed.
∀ (xs : seq nat) (x : nat),
head 0 xs ≤ x < last 0 xs →
∃ n,
n.+1 < size xs
∧ nth 0 xs n ≤ x < nth 0 xs n.+1.
Proof.
move⇒ xs x; elim: xs ⇒ [//|a xs IH].
case: xs IH ⇒ [|b xs] IH /= /andP[ha hl]; first by move: hl; rewrite ltnNge ha.
case: (leqP b x) ⇒ [bx|xb]; last by ∃ 0; split⇒ //; rewrite ha xb.
have /IH [i [ilt hi]] : b ≤ x < last b xs by rewrite bx hl.
by ∃ i.+1; split.
Qed.
Additional Lemmas about sorted
Lemma sorted_split :
∀ {X : eqType} (xs : seq X) P f t,
sorted (fun x y ⇒ f x ≤ f y) xs →
[seq x <- xs | P x] = [seq x <- xs | P x & f x ≤ t] ++ [seq x <- xs | P x & f x > t].
Proof.
clear; move⇒ X xs P f t; elim: xs ⇒ [//|a xs IHxs] /= SORT.
have TR : transitive (T:=X) (fun x y : X ⇒ f x ≤ f y).
{ intros ? ? ? LE1 LE2; lia. }
destruct (P a) eqn:Pa, (leqP (f a) t) as [R1 | R1]; simpl.
{ erewrite IHxs; first by reflexivity.
by eapply path_sorted; eauto. }
{ erewrite IHxs; last by eapply path_sorted; eauto.
replace ([seq x <- xs | P x & f x ≤ t]) with (@nil X); first by done.
symmetry; move: SORT; rewrite path_sortedE // ⇒ /andP [ALL SORT].
apply filter_in_pred0; intros ? IN; apply/negP; intros H; move: H ⇒ /andP [Px LEx].
by move: ALL ⇒ /allP ALL; specialize (ALL _ IN); simpl in ALL; lia.
}
{ by eapply IHxs, path_sorted; eauto. }
{ by eapply IHxs, path_sorted; eauto. }
Qed.
∀ {X : eqType} (xs : seq X) P f t,
sorted (fun x y ⇒ f x ≤ f y) xs →
[seq x <- xs | P x] = [seq x <- xs | P x & f x ≤ t] ++ [seq x <- xs | P x & f x > t].
Proof.
clear; move⇒ X xs P f t; elim: xs ⇒ [//|a xs IHxs] /= SORT.
have TR : transitive (T:=X) (fun x y : X ⇒ f x ≤ f y).
{ intros ? ? ? LE1 LE2; lia. }
destruct (P a) eqn:Pa, (leqP (f a) t) as [R1 | R1]; simpl.
{ erewrite IHxs; first by reflexivity.
by eapply path_sorted; eauto. }
{ erewrite IHxs; last by eapply path_sorted; eauto.
replace ([seq x <- xs | P x & f x ≤ t]) with (@nil X); first by done.
symmetry; move: SORT; rewrite path_sortedE // ⇒ /andP [ALL SORT].
apply filter_in_pred0; intros ? IN; apply/negP; intros H; move: H ⇒ /andP [Px LEx].
by move: ALL ⇒ /allP ALL; specialize (ALL _ IN); simpl in ALL; lia.
}
{ by eapply IHxs, path_sorted; eauto. }
{ by eapply IHxs, path_sorted; eauto. }
Qed.
Additional Lemmas about last
Lemma filter_last_mem :
∀ {X : eqType} (xs : seq X) (d : X) (P : pred X),
has P xs →
last d (filter P xs) \in xs.
Proof.
move⇒ X xs d P; rewrite has_filter.
case EQ: (filter P xs) ⇒ [//|a ys] _ /=.
move: (mem_last a ys).
by rewrite -EQ mem_filter ⇒ /andP[].
Qed.
∀ {X : eqType} (xs : seq X) (d : X) (P : pred X),
has P xs →
last d (filter P xs) \in xs.
Proof.
move⇒ X xs d P; rewrite has_filter.
case EQ: (filter P xs) ⇒ [//|a ys] _ /=.
move: (mem_last a ys).
by rewrite -EQ mem_filter ⇒ /andP[].
Qed.
Range of Indices
In the following, we establish some lemmas about index_iota and range
for lists.
Splitting index_iota t1 t2 at t yields two concatenated iotas.
Lemma index_iota_cat :
∀ t t1 t2,
t1 ≤ t ≤ t2 →
index_iota t1 t2 = index_iota t1 t ++ index_iota t t2.
Proof.
move⇒ t t1 t2 /andP [LE1 LE2]; rewrite /index_iota.
have → : t2 - t1 = (t - t1) + (t2 - t) by lia.
by rewrite iotaD (subnKC LE1).
Qed.
∀ t t1 t2,
t1 ≤ t ≤ t2 →
index_iota t1 t2 = index_iota t1 t ++ index_iota t t2.
Proof.
move⇒ t t1 t2 /andP [LE1 LE2]; rewrite /index_iota.
have → : t2 - t1 = (t - t1) + (t2 - t) by lia.
by rewrite iotaD (subnKC LE1).
Qed.
Filtering an interval by a sequence whose minimum is x yields x
followed by the interval filtered by the values other than x.
Lemma index_iota_filter_step :
∀ x xs a b,
a ≤ x < b →
(∀ y, y \in xs → x ≤ y) →
[seq ρ <- index_iota a b | ρ \in x :: xs]
= x :: [seq ρ <- index_iota a b | ρ \in filter (predC1 x) xs].
Proof.
move⇒ x xs a b /andP [AX XB] MIN.
have PRE : [seq y <- index_iota a x | y \in x :: xs] = [::].
{ apply: filter_in_pred0 ⇒ y.
rewrite mem_index_iota in_cons ⇒ /andP [_ YX].
apply/negP ⇒ /orP [/eqP EQ | /MIN XY]; lia. }
have → : [seq y <- index_iota a b | y \in filter (predC1 x) xs]
= filter (predC1 x) [seq y <- index_iota a b | y \in x :: xs].
{ rewrite -filter_predI; apply: eq_filter ⇒ y.
by rewrite mem_filter /predI /predC1 /= in_cons; case: (y == x). }
rewrite (index_iota_cat x) ?AX ?(ltnW XB) // filter_cat PRE /=.
rewrite /index_iota -(subnSK XB) /= in_cons eqxx /= /predC1 /= eqxx /=.
congr (x :: _); symmetry; apply/all_filterP/allP ⇒ y.
rewrite mem_filter mem_iota ⇒ /andP [_ /andP [XY _]].
by apply/eqP; lia.
Qed.
∀ x xs a b,
a ≤ x < b →
(∀ y, y \in xs → x ≤ y) →
[seq ρ <- index_iota a b | ρ \in x :: xs]
= x :: [seq ρ <- index_iota a b | ρ \in filter (predC1 x) xs].
Proof.
move⇒ x xs a b /andP [AX XB] MIN.
have PRE : [seq y <- index_iota a x | y \in x :: xs] = [::].
{ apply: filter_in_pred0 ⇒ y.
rewrite mem_index_iota in_cons ⇒ /andP [_ YX].
apply/negP ⇒ /orP [/eqP EQ | /MIN XY]; lia. }
have → : [seq y <- index_iota a b | y \in filter (predC1 x) xs]
= filter (predC1 x) [seq y <- index_iota a b | y \in x :: xs].
{ rewrite -filter_predI; apply: eq_filter ⇒ y.
by rewrite mem_filter /predI /predC1 /= in_cons; case: (y == x). }
rewrite (index_iota_cat x) ?AX ?(ltnW XB) // filter_cat PRE /=.
rewrite /index_iota -(subnSK XB) /= in_cons eqxx /= /predC1 /= eqxx /=.
congr (x :: _); symmetry; apply/all_filterP/allP ⇒ y.
rewrite mem_filter mem_iota ⇒ /andP [_ /andP [XY _]].
by apply/eqP; lia.
Qed.
Additional Lemmas about count
Lemma count_predUI' :
∀ (P1 P2 : pred nat) (xs : seq nat),
count (predU P1 P2) xs = count P1 xs + count P2 xs - count (predI P1 P2) xs.
Proof.
by move⇒ P1 P2 xs; rewrite -(count_predUI P1 P2 xs) addnK.
Qed.
∀ (P1 P2 : pred nat) (xs : seq nat),
count (predU P1 P2) xs = count P1 xs + count P2 xs - count (predI P1 P2) xs.
Proof.
by move⇒ P1 P2 xs; rewrite -(count_predUI P1 P2 xs) addnK.
Qed.
Shifting Sequences of Natural Numbers
Definition shift_points_pos (xs : seq nat) (s : nat) : seq nat :=
map (addn s) xs.
Definition shift_points_neg (xs : seq nat) (s : nat) : seq nat :=
let nonsmall := filter (fun x ⇒ x ≥ s) xs in
map (fun x ⇒ x - s) nonsmall.
map (addn s) xs.
Definition shift_points_neg (xs : seq nat) (s : nat) : seq nat :=
let nonsmall := filter (fun x ⇒ x ≥ s) xs in
map (fun x ⇒ x - s) nonsmall.
Upstream Replacements and Dependent Results
Lemma last_filter {T : Type} (d : T) (xs : seq T) (P : pred T) :
P (last d xs) → last d [seq x <- xs | P x] = last d xs.
Proof.
case/lastP: xs ⇒ [//|ys x].
by rewrite last_rcons ⇒ Px; rewrite filter_rcons Px last_rcons.
Qed.
P (last d xs) → last d [seq x <- xs | P x] = last d xs.
Proof.
case/lastP: xs ⇒ [//|ys x].
by rewrite last_rcons ⇒ Px; rewrite filter_rcons Px last_rcons.
Qed.
TODO: MathComp's sub_in_count covers this lemma (merged PR 1649).
Replace it after adopting the next MathComp release containing that result:
https://github.com/math-comp/math-comp/pull/1649.
If f implies g for all elements in xs, then the number of
elements in xs satisfying f is less than or equal to the
number of elements satisfying g.
Lemma sub_count_seq :
∀ {X : eqType} (f g : pred X) (xs : seq X),
{in xs, ∀ x, f x → g x} →
count f xs ≤ count g xs.
Proof.
move⇒ X f g xs LE; rewrite -!size_filter -!sum1_size !big_filter.
rewrite big_seq_cond [leqRHS]big_seq_cond big_mkcond [leqRHS]big_mkcond.
apply leq_sum ⇒ t _; destruct (_ \in _) eqn:IN, (f t) eqn:FT, (g t) eqn:GT ⇒ //.
by move: (LE _ IN); rewrite FT GT ⇒ FA.
Qed.
∀ {X : eqType} (f g : pred X) (xs : seq X),
{in xs, ∀ x, f x → g x} →
count f xs ≤ count g xs.
Proof.
move⇒ X f g xs LE; rewrite -!size_filter -!sum1_size !big_filter.
rewrite big_seq_cond [leqRHS]big_seq_cond big_mkcond [leqRHS]big_mkcond.
apply leq_sum ⇒ t _; destruct (_ \in _) eqn:IN, (f t) eqn:FT, (g t) eqn:GT ⇒ //.
by move: (LE _ IN); rewrite FT GT ⇒ FA.
Qed.
TODO: MathComp's eq_bigmax_seq subsumes this lemma (merged PR 1652).
Replace it after adopting the next MathComp release containing that result:
https://github.com/math-comp/math-comp/pull/1652.
The maximum of a nonempty sequence belongs to the sequence.
Lemma bigmax_mem :
∀ xs : seq nat, xs ≠ [::] → (\max_(x <- xs) x) \in xs.
Proof.
elim⇒ [//|a xs IH] _; rewrite big_cons.
case: xs IH ⇒ [|b xs IH]; first by rewrite big_nil maxn0 mem_head.
case: (leqP a (\max_(x <- b :: xs) x)) ⇒ LE.
- by rewrite in_cons IH // orbT.
- by rewrite mem_head.
Qed.
∀ xs : seq nat, xs ≠ [::] → (\max_(x <- xs) x) \in xs.
Proof.
elim⇒ [//|a xs IH] _; rewrite big_cons.
case: xs IH ⇒ [|b xs IH]; first by rewrite big_nil maxn0 mem_head.
case: (leqP a (\max_(x <- b :: xs) x)) ⇒ LE.
- by rewrite in_cons IH // orbT.
- by rewrite mem_head.
Qed.
This local corollary is kept alongside bigmax_mem because its proof
uses that lemma. Adapt the proof when replacing bigmax_mem with
MathComp's eq_bigmax_seq.
A nonempty sequence whose elements all equal k has maximum k.