blob: 6d2110d342b0324ed96c73a2220a27a3ae780981 [file]
/-
Copyright (c) 2025 Lean FRO, LLC. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Paul Reichert
-/
module
prelude
import all Init.Data.Array.Subarray
import all Init.Data.Slice.Array.Basic
import Init.Data.Slice.Lemmas
public import Init.Data.Slice.Array.Iterator
import all Init.Data.Slice.Array.Iterator
import all Init.Data.Slice.Operations
import all Init.Data.Range.Polymorphic.Iterators
import all Init.Data.Range.Polymorphic.Lemmas
import Init.Data.Slice.List.Lemmas
public import Init.Data.List.Control
public import Init.Data.Nat.MinMax
public import Init.Data.Slice.Array.Basic
import Init.Data.List.Nat.TakeDrop
import Init.Data.List.TakeDrop
open Std Std.Iterators Std.PRange Std.Slice
namespace SubarrayIterator
theorem step_eq {it : Iter (α := SubarrayIterator α) α} :
it.step = if h : it.1.xs.start < it.1.xs.stop then
haveI := it.1.xs.start_le_stop
haveI := it.1.xs.stop_le_array_size
⟨.yield ⟨⟨it.1.xs.array, it.1.xs.start + 1, it.1.xs.stop, by omega, by assumption⟩⟩
(it.1.xs.array[it.1.xs.start]'(by omega)),
(by
simp_all [Iter.IsPlausibleStep, IterM.IsPlausibleStep, Iterator.IsPlausibleStep,
SubarrayIterator.step, Iter.toIterM])⟩
else
⟨.done, (by
simpa [Iter.IsPlausibleStep, IterM.IsPlausibleStep, Iterator.IsPlausibleStep,
SubarrayIterator.step] using h)⟩ := by
simp only [Iter.step, IterM.Step.toPure, Iter.toIter_toIterM, IterStep.mapIterator, IterM.step,
Iterator.step, SubarrayIterator.step, Id.run_pure, Shrink.inflate_deflate]
by_cases h : it.internalState.xs.start < it.internalState.xs.stop
· simp only [h, ↓reduceDIte]
split
· rfl
· rename_i h'
exact h'.elim h
· simp only [h, ↓reduceDIte]
split
· rename_i h'
exact h.elim h'
· rfl
theorem val_step_eq {it : Iter (α := SubarrayIterator α) α} :
it.step.val = if h : it.1.xs.start < it.1.xs.stop then
haveI := it.1.xs.start_le_stop
haveI := it.1.xs.stop_le_array_size
.yield ⟨⟨it.1.xs.array, it.1.xs.start + 1, it.1.xs.stop, by omega, by assumption⟩⟩
it.1.xs.array[it.1.xs.start]
else
.done := by
simp only [step_eq]
split <;> simp
theorem toList_eq {α : Type u} {it : Iter (α := SubarrayIterator α) α} :
it.toList =
(it.internalState.xs.array.toList.take it.internalState.xs.stop).drop it.internalState.xs.start := by
induction it using Iter.inductSteps with | step it ihy ihs
rw [Iter.toList_eq_match_step, SubarrayIterator.val_step_eq]
by_cases h : it.internalState.xs.start < it.internalState.xs.stop
· simp [h]
have := it.1.xs.start_le_stop
have := it.1.xs.stop_le_array_size
rw [ihy (out := it.internalState.xs.array[it.internalState.xs.start])]
· simp only [Subarray.start]
rw (occs := [2]) [List.drop_eq_getElem_cons]; rotate_left
· rw [List.length_take]
simp [it.internalState.xs.stop_le_array_size]
exact h
· simp [Subarray.array, Subarray.stop]
· simp only [Iter.IsPlausibleStep, IterM.IsPlausibleStep, Iterator.IsPlausibleStep,
IterStep.mapIterator_yield, SubarrayIterator.step]
rw [dif_pos]; rotate_left; exact h
rfl
· rw [dif_neg]; rotate_left; exact h
simp_all [it.internalState.xs.stop_le_array_size]
theorem length_eq {α : Type u} {it : Iter (α := SubarrayIterator α) α} :
it.length = it.internalState.xs.stop - it.internalState.xs.start := by
simp [← Iter.length_toList_eq_length, toList_eq, it.internalState.xs.stop_le_array_size]
@[deprecated length_eq (since := "2026-01-28")]
def count_eq := @length_eq
end SubarrayIterator
namespace Subarray
theorem internalIter_eq {α : Type u} {s : Subarray α} :
Internal.iter s = ⟨⟨s⟩⟩ :=
rfl
theorem toList_internalIter {α : Type u} {s : Subarray α} :
(Internal.iter s).toList =
(s.array.toList.take s.stop).drop s.start := by
simp [SubarrayIterator.toList_eq, Internal.iter_eq_toIteratorIter, ToIterator.iter_eq]
public instance : LawfulSliceSize (Internal.SubarrayData α) where
lawful s := by
simp [SliceSize.size, ToIterator.iter_eq, Iter.toIter_toIterM,
← Iter.length_toList_eq_length, SubarrayIterator.toList_eq,
s.internalRepresentation.stop_le_array_size, start, stop, array]
public theorem toArray_eq_sliceToArray {α : Type u} {s : Subarray α} :
s.toArray = Slice.toArray s := by
simp [Subarray.toArray]
@[simp]
public theorem forIn_toList {α : Type u} {s : Subarray α}
{m : Type v → Type w} [Monad m] [LawfulMonad m] {γ : Type v} {init : γ}
{f : α → γ → m (ForInStep γ)} :
ForIn.forIn s.toList init f = ForIn.forIn s init f :=
Slice.forIn_toList
@[grind =]
public theorem forIn_eq_forIn_toList {α : Type u} {s : Subarray α}
{m : Type v → Type w} [Monad m] [LawfulMonad m] {γ : Type v} {init : γ}
{f : α → γ → m (ForInStep γ)} :
ForIn.forIn s init f = ForIn.forIn s.toList init f :=
forIn_toList.symm
@[simp]
public theorem forIn_toArray {α : Type u} {s : Subarray α}
{m : Type v → Type w} [Monad m] [LawfulMonad m] {γ : Type v} {init : γ}
{f : α → γ → m (ForInStep γ)} :
ForIn.forIn s.toArray init f = ForIn.forIn s init f :=
Slice.forIn_toArray
end Subarray
public theorem Array.toSubarray_eq_toSubarray_of_min_eq_min {xs : Array α}
{start stop stop' : Nat} (h : min stop xs.size = min stop' xs.size) :
xs.toSubarray start stop = xs.toSubarray start stop' := by
simp only [Array.toSubarray]
split
· split
· have h₁ : start ≤ xs.size := by omega
have h₂ : start ≤ stop' := by omega
simp only [dif_pos h₁, dif_pos h₂]
split
· simp_all
· simp_all [Nat.min_eq_right (Nat.le_of_lt _)]
· simp only [Nat.min_eq_left, *] at h
split
· simp only [Nat.min_eq_left, *] at h
simp only [h, right_eq_dite_iff, Slice.mk.injEq, Internal.SubarrayData.mk.injEq, and_true,
true_and]
omega
· simp only [ge_iff_le, not_false_eq_true, Nat.min_eq_right (Nat.le_of_not_ge _), *] at h
simp [h]
omega
· split
· split
· simp only [not_false_eq_true, Nat.min_eq_right (Nat.le_of_not_ge _),
Nat.min_eq_left, Nat.not_le, *] at *
simp [*]; omega
· simp
· simp [Nat.min_eq_right (Nat.le_of_not_ge _), *] at h
split
· simp only [Nat.min_eq_left, *] at h
simp [*]; omega
· simp
public theorem Array.toSubarray_eq_min {xs : Array α} {lo hi : Nat} :
xs.toSubarray lo hi = ⟨⟨xs, min lo (min hi xs.size), min hi xs.size, Nat.min_le_right _ _,
Nat.min_le_right _ _⟩⟩ := by
simp only [Array.toSubarray]
split <;> split <;> simp [Nat.min_eq_right (Nat.le_of_not_ge _), *]
@[simp, grind =]
public theorem Array.array_toSubarray {xs : Array α} {lo hi : Nat} :
(xs.toSubarray lo hi).array = xs := by
simp [toSubarray_eq_min, Subarray.array]
@[simp, grind =]
public theorem Array.start_toSubarray {xs : Array α} {lo hi : Nat} :
(xs.toSubarray lo hi).start = min lo (min hi xs.size) := by
simp [toSubarray_eq_min, Subarray.start]
@[simp, grind =]
public theorem Array.stop_toSubarray {xs : Array α} {lo hi : Nat} :
(xs.toSubarray lo hi).stop = min hi xs.size := by
simp [toSubarray_eq_min, Subarray.stop]
public theorem Subarray.toList_eq {xs : Subarray α} :
xs.toList = (xs.array.extract xs.start xs.stop).toList := by
let aslice := xs
obtain ⟨⟨array, start, stop, h₁, h₂⟩⟩ := xs
let lslice : ListSlice α := ⟨array.toList.drop start, some (stop - start)⟩
simp only [Subarray.start, Subarray.stop, Subarray.array]
change aslice.toList = _
have : aslice.toList = lslice.toList := by
rw [ListSlice.toList_eq]
simp +instances only [aslice, lslice, Std.Slice.toList, toList_internalIter]
apply List.ext_getElem
· have : stop - start ≤ array.size - start := by omega
simp [Subarray.start, Subarray.stop, *, Subarray.array]
· intros
simp [Subarray.array, Subarray.start, Subarray.stop]
simp +instances [this, ListSlice.toList_eq, lslice]
@[grind =]
public theorem Subarray.size_eq {xs : Subarray α} :
xs.size = xs.stop - xs.start := by
simp [Subarray.size]
@[simp, grind =]
public theorem Subarray.toArray_toList {xs : Subarray α} :
xs.toList.toArray = xs.toArray := by
simp [Std.Slice.toList, Subarray.toArray, Std.Slice.toArray]
@[simp, grind =]
public theorem Subarray.toList_toArray {xs : Subarray α} :
xs.toArray.toList = xs.toList := by
simp [Std.Slice.toList, Subarray.toArray, Std.Slice.toArray]
@[simp, grind =]
public theorem Subarray.length_toList {xs : Subarray α} :
xs.toList.length = xs.size := by
have : xs.start ≤ xs.stop := xs.internalRepresentation.start_le_stop
have : xs.stop ≤ xs.array.size := xs.internalRepresentation.stop_le_array_size
simp [Subarray.toList_eq, Subarray.size]; omega
@[simp, grind =]
public theorem Subarray.size_toArray {xs : Subarray α} :
xs.toArray.size = xs.size := by
simp [← Subarray.toArray_toList, Subarray.size, Slice.size, SliceSize.size, start, stop]
namespace Array
@[simp, grind =]
public theorem array_mkSlice_rco {xs : Array α} {lo hi : Nat} :
xs[lo...hi].array = xs := by
simp [Std.Rco.Sliceable.mkSlice, Array.toSubarray, apply_dite, Subarray.array]
@[simp, grind =]
public theorem start_mkSlice_rco {xs : Array α} {lo hi : Nat} :
xs[lo...hi].start = min lo (min hi xs.size) := by
simp [Std.Rco.Sliceable.mkSlice]
@[simp, grind =]
public theorem stop_mkSlice_rco {xs : Array α} {lo hi : Nat} :
xs[lo...hi].stop = min hi xs.size := by
simp [Std.Rco.Sliceable.mkSlice]
public theorem mkSlice_rco_eq_mkSlice_rco_min {xs : Array α} {lo hi : Nat} :
xs[lo...hi] = xs[(min lo (min hi xs.size))...(min hi xs.size)] := by
simp [Std.Rco.Sliceable.mkSlice, Array.toSubarray_eq_min]
@[simp, grind =]
public theorem toList_mkSlice_rco {xs : Array α} {lo hi : Nat} :
xs[lo...hi].toList = (xs.toList.take hi).drop lo := by
rw [List.take_eq_take_min, List.drop_eq_drop_min]
simp [Std.Rco.Sliceable.mkSlice, Subarray.toList_eq, List.take_drop,
Nat.add_sub_of_le (Nat.min_le_right _ _)]
@[simp, grind =]
public theorem toArray_mkSlice_rco {xs : Array α} {lo hi : Nat} :
xs[lo...hi].toArray = xs.extract lo hi := by
simp only [← Subarray.toArray_toList, toList_mkSlice_rco]
rw [show xs = xs.toList.toArray by simp, List.extract_toArray, List.extract_eq_drop_take]
simp only [List.take_drop, mk.injEq]
by_cases h : lo ≤ hi
· congr 1
rw [List.take_eq_take_iff, Nat.add_sub_cancel' h]
· rw [List.drop_eq_nil_of_le, List.drop_eq_nil_of_le]
· simp; omega
· simp; omega
@[simp, grind =]
public theorem size_mkSlice_rco {xs : Array α} {lo hi : Nat} :
xs[lo...hi].size = min hi xs.size - lo := by
simp [← Subarray.length_toList]
@[simp, grind =]
public theorem mkSlice_rcc_eq_mkSlice_rco {xs : Array α} {lo hi : Nat} :
xs[lo...=hi] = xs[lo...(hi + 1)] := by
simp [Std.Rcc.Sliceable.mkSlice, Std.Rco.Sliceable.mkSlice]
public theorem mkSlice_rcc_eq_mkSlice_rco_min {xs : Array α} {lo hi : Nat} :
xs[lo...=hi] = xs[(min lo (min (hi + 1) xs.size))...(min (hi + 1) xs.size)] := by
simp [mkSlice_rco_eq_mkSlice_rco_min]
@[simp, grind =]
public theorem array_mkSlice_rcc {xs : Array α} {lo hi : Nat} :
xs[lo...=hi].array = xs := by
simp [Std.Rcc.Sliceable.mkSlice, Array.toSubarray, apply_dite, Subarray.array]
@[simp]
public theorem start_mkSlice_rcc {xs : Array α} {lo hi : Nat} :
xs[lo...=hi].start = min lo (min (hi + 1) xs.size) := by
simp [Std.Rco.Sliceable.mkSlice]
@[simp]
public theorem stop_mkSlice_rcc {xs : Array α} {lo hi : Nat} :
xs[lo...=hi].stop = min (hi + 1) xs.size := by
simp [Std.Rco.Sliceable.mkSlice]
@[simp]
public theorem toList_mkSlice_rcc {xs : Array α} {lo hi : Nat} :
xs[lo...=hi].toList = (xs.toList.take (hi + 1)).drop lo := by
simp
@[simp]
public theorem toArray_mkSlice_rcc {xs : Array α} {lo hi : Nat} :
xs[lo...=hi].toArray = xs.extract lo (hi + 1) := by
simp
@[simp]
public theorem size_mkSlice_rcc {xs : Array α} {lo hi : Nat} :
xs[lo...=hi].size = min (hi + 1) xs.size - lo := by
simp [← Subarray.length_toList]
@[simp]
public theorem array_mkSlice_rci {xs : Array α} {lo : Nat} :
xs[lo...*].array = xs := by
simp [Std.Rci.Sliceable.mkSlice, Array.toSubarray, apply_dite, Subarray.array]
@[simp]
public theorem start_mkSlice_rci {xs : Array α} {lo : Nat} :
xs[lo...*].start = min lo xs.size := by
simp [Std.Rci.Sliceable.mkSlice, Std.Rci.HasRcoIntersection.intersection]
@[simp]
public theorem stop_mkSlice_rci {xs : Array α} {lo : Nat} :
xs[lo...*].stop = xs.size := by
simp [Std.Rci.Sliceable.mkSlice, Std.Rci.HasRcoIntersection.intersection]
@[simp, grind =]
public theorem mkSlice_rci_eq_mkSlice_rco {xs : Array α} {lo : Nat} :
xs[lo...*] = xs[lo...xs.size] := by
simp [Std.Rci.Sliceable.mkSlice, Std.Rco.Sliceable.mkSlice, Std.Rci.HasRcoIntersection.intersection]
public theorem mkSlice_rci_eq_mkSlice_rco_min {xs : Array α} {lo : Nat} :
xs[lo...*] = xs[(min lo xs.size)...xs.size] := by
simp [mkSlice_rco_eq_mkSlice_rco_min]
@[simp]
public theorem toList_mkSlice_rci {xs : Array α} {lo : Nat} :
xs[lo...*].toList = xs.toList.drop lo := by
rw [mkSlice_rci_eq_mkSlice_rco, toList_mkSlice_rco, ← Array.length_toList, List.take_length]
@[simp]
public theorem toArray_mkSlice_rci {xs : Array α} {lo : Nat} :
xs[lo...*].toArray = xs.extract lo := by
simp
@[simp, grind =]
public theorem size_mkSlice_rci {xs : Array α} {lo : Nat} :
xs[lo...*].size = xs.size - lo := by
simp [← Subarray.length_toList]
@[simp]
public theorem array_mkSlice_roo {xs : Array α} {lo hi : Nat} :
xs[lo<...hi].array = xs := by
simp [Std.Roo.Sliceable.mkSlice, Array.toSubarray, apply_dite, Subarray.array]
@[simp]
public theorem start_mkSlice_roo {xs : Array α} {lo hi : Nat} :
xs[lo<...hi].start = min (lo + 1) (min hi xs.size) := by
simp [Std.Roo.Sliceable.mkSlice]
@[simp]
public theorem stop_mkSlice_roo {xs : Array α} {lo hi : Nat} :
xs[lo<...hi].stop = min hi xs.size := by
simp [Std.Roo.Sliceable.mkSlice]
@[simp, grind =]
public theorem mkSlice_roo_eq_mkSlice_rco {xs : Array α} {lo hi : Nat} :
xs[lo<...hi] = xs[(lo + 1)...hi] := by
simp [Std.Roo.Sliceable.mkSlice, Std.Rco.Sliceable.mkSlice]
public theorem mkSlice_roo_eq_mkSlice_roo_min {xs : Array α} {lo hi : Nat} :
xs[lo<...hi] = xs[(min (lo + 1) (min hi xs.size))...(min hi xs.size)] := by
simp [mkSlice_rco_eq_mkSlice_rco_min]
@[simp]
public theorem toList_mkSlice_roo {xs : Array α} {lo hi : Nat} :
xs[lo<...hi].toList = (xs.toList.take hi).drop (lo + 1) := by
simp
@[simp]
public theorem toArray_mkSlice_roo {xs : Array α} {lo hi : Nat} :
xs[lo<...hi].toArray = xs.extract (lo + 1) hi := by
simp
@[simp]
public theorem size_mkSlice_roo {xs : Array α} {lo hi : Nat} :
xs[lo<...hi].size = min hi xs.size - (lo + 1) := by
simp [← Subarray.length_toList]
@[simp]
public theorem array_mkSlice_roc {xs : Array α} {lo hi : Nat} :
xs[lo<...=hi].array = xs := by
simp [Std.Roc.Sliceable.mkSlice, Array.toSubarray, apply_dite, Subarray.array]
@[simp]
public theorem start_mkSlice_roc {xs : Array α} {lo hi : Nat} :
xs[lo<...=hi].start = min (lo + 1) (min (hi + 1) xs.size) := by
simp [Std.Roc.Sliceable.mkSlice]
@[simp]
public theorem stop_mkSlice_roc {xs : Array α} {lo hi : Nat} :
xs[lo<...=hi].stop = min (hi + 1) xs.size := by
simp [Std.Roc.Sliceable.mkSlice]
@[simp]
public theorem mkSlice_roc_eq_mkSlice_roo {xs : Array α} {lo hi : Nat} :
xs[lo<...=hi] = xs[lo<...(hi + 1)] := by
simp [Std.Roc.Sliceable.mkSlice, Std.Roo.Sliceable.mkSlice]
@[grind =]
public theorem mkSlice_roc_eq_mkSlice_rco {xs : Array α} {lo hi : Nat} :
xs[lo<...=hi] = xs[(lo + 1)...(hi + 1)] := by
simp
public theorem mkSlice_roc_eq_mkSlice_roo_min {xs : Array α} {lo hi : Nat} :
xs[lo<...=hi] = xs[(min (lo + 1) (min (hi + 1) xs.size))...(min (hi + 1) xs.size)] := by
simp [mkSlice_rco_eq_mkSlice_rco_min]
@[simp]
public theorem toList_mkSlice_roc {xs : Array α} {lo hi : Nat} :
xs[lo<...=hi].toList = (xs.toList.take (hi + 1)).drop (lo + 1) := by
simp
@[simp]
public theorem toArray_mkSlice_roc {xs : Array α} {lo hi : Nat} :
xs[lo<...=hi].toArray = xs.extract (lo + 1) (hi + 1) := by
simp
@[simp]
public theorem size_mkSlice_roc {xs : Array α} {lo hi : Nat} :
xs[lo<...=hi].size = min (hi + 1) xs.size - (lo + 1) := by
simp [← Subarray.length_toList]
@[simp]
public theorem array_mkSlice_roi {xs : Array α} {lo : Nat} :
xs[lo<...*].array = xs := by
simp [Std.Roi.Sliceable.mkSlice, Array.toSubarray, apply_dite, Subarray.array]
@[simp]
public theorem start_mkSlice_roi {xs : Array α} {lo : Nat} :
xs[lo<...*].start = min (lo + 1) xs.size := by
simp [Std.Roi.Sliceable.mkSlice, Std.Roi.HasRcoIntersection.intersection]
@[simp]
public theorem stop_mkSlice_roi {xs : Array α} {lo : Nat} :
xs[lo...*].stop = xs.size := by
simp [Std.Rco.Sliceable.mkSlice]
@[simp]
public theorem mkSlice_roi_eq_mkSlice_rci {xs : Array α} {lo : Nat} :
xs[lo<...*] = xs[(lo + 1)...*] := by
simp [Std.Roi.Sliceable.mkSlice, Std.Roi.HasRcoIntersection.intersection,
Std.Rci.Sliceable.mkSlice, Std.Rci.HasRcoIntersection.intersection]
public theorem mkSlice_roi_eq_mkSlice_roo {xs : Array α} {lo : Nat} :
xs[lo<...*] = xs[lo<...xs.size] := by
simp [mkSlice_rci_eq_mkSlice_rco]
@[grind =]
public theorem mkSlice_roi_eq_mkSlice_rco {xs : Array α} {lo : Nat} :
xs[lo<...*] = xs[(lo + 1)...xs.size] := by
simp [mkSlice_rci_eq_mkSlice_rco]
public theorem mkSlice_roi_eq_mkSlice_roo_min {xs : Array α} {lo : Nat} :
xs[lo<...*] = xs[(min (lo + 1) xs.size)...xs.size] := by
simp [mkSlice_rco_eq_mkSlice_rco_min]
@[simp]
public theorem toList_mkSlice_roi {xs : Array α} {lo : Nat} :
xs[lo<...*].toList = xs.toList.drop (lo + 1) := by
rw [mkSlice_roi_eq_mkSlice_rci, toList_mkSlice_rci]
@[simp]
public theorem toArray_mkSlice_roi {xs : Array α} {lo : Nat} :
xs[lo<...*].toArray = xs.drop (lo + 1) := by
simp
@[simp]
public theorem size_mkSlice_roi {xs : Array α} {lo : Nat} :
xs[lo<...*].size = xs.size - (lo + 1) := by
simp [← Subarray.length_toList]
@[simp]
public theorem array_mkSlice_rio {xs : Array α} {hi : Nat} :
xs[*...hi].array = xs := by
simp [Std.Rio.Sliceable.mkSlice, Array.toSubarray, apply_dite, Subarray.array]
@[simp, grind =]
public theorem start_mkSlice_rio {xs : Array α} {hi : Nat} :
xs[*...hi].start = 0 := by
simp [Std.Rio.Sliceable.mkSlice]
@[simp]
public theorem stop_mkSlice_rio {xs : Array α} {hi : Nat} :
xs[*...hi].stop = min hi xs.size := by
simp [Std.Rio.Sliceable.mkSlice]
@[simp, grind =]
public theorem mkSlice_rio_eq_mkSlice_rco {xs : Array α} {hi : Nat} :
xs[*...hi] = xs[0...hi] := by
simp [Std.Rio.Sliceable.mkSlice, Std.Rco.Sliceable.mkSlice]
public theorem mkSlice_rio_eq_mkSlice_rio_min {xs : Array α} {hi : Nat} :
xs[*...hi] = xs[*...(min hi xs.size)] := by
simp [mkSlice_rco_eq_mkSlice_rco_min]
@[simp]
public theorem toList_mkSlice_rio {xs : Array α} {hi : Nat} :
xs[*...hi].toList = xs.toList.take hi := by
simp
@[simp]
public theorem toArray_mkSlice_rio {xs : Array α} {hi : Nat} :
xs[*...hi].toArray = xs.extract 0 hi := by
simp
@[simp]
public theorem size_mkSlice_rio {xs : Array α} {hi : Nat} :
xs[*...hi].size = min hi xs.size := by
simp [← Subarray.length_toList]
@[simp]
public theorem array_mkSlice_ric {xs : Array α} {hi : Nat} :
xs[*...=hi].array = xs := by
simp [Std.Ric.Sliceable.mkSlice, Array.toSubarray, apply_dite, Subarray.array]
@[simp, grind =]
public theorem start_mkSlice_ric {xs : Array α} {hi : Nat} :
xs[*...=hi].start = 0 := by
simp [Std.Ric.Sliceable.mkSlice]
@[simp]
public theorem stop_mkSlice_ric {xs : Array α} {hi : Nat} :
xs[*...=hi].stop = min (hi + 1) xs.size := by
simp [Std.Ric.Sliceable.mkSlice]
@[simp]
public theorem mkSlice_ric_eq_mkSlice_rio {xs : Array α} {hi : Nat} :
xs[*...=hi] = xs[*...(hi + 1)] := by
simp [Std.Ric.Sliceable.mkSlice, Std.Rio.Sliceable.mkSlice]
@[grind =]
public theorem mkSlice_ric_eq_mkSlice_rco {xs : Array α} {hi : Nat} :
xs[*...=hi] = xs[0...(hi + 1)] := by
simp
public theorem mkSlice_ric_eq_mkSlice_rio_min {xs : Array α} {hi : Nat} :
xs[*...=hi] = xs[*...(min (hi + 1) xs.size)] := by
simp [mkSlice_rco_eq_mkSlice_rco_min]
@[simp]
public theorem toList_mkSlice_ric {xs : Array α} {hi : Nat} :
xs[*...=hi].toList = xs.toList.take (hi + 1) := by
simp
@[simp]
public theorem toArray_mkSlice_ric {xs : Array α} {hi : Nat} :
xs[*...=hi].toArray = xs.extract 0 (hi + 1) := by
simp
@[simp]
public theorem size_mkSlice_ric {xs : Array α} {hi : Nat} :
xs[*...=hi].size = min (hi + 1) xs.size := by
simp [← Subarray.length_toList]
@[simp]
public theorem mkSlice_rii_eq_mkSlice_rci {xs : Array α} :
xs[*...*] = xs[0...*] := by
simp [Std.Rii.Sliceable.mkSlice, Std.Rci.Sliceable.mkSlice,
Std.Rci.HasRcoIntersection.intersection]
public theorem mkSlice_rii_eq_mkSlice_rio {xs : Array α} :
xs[*...*] = xs[*...xs.size] := by
simp [mkSlice_rci_eq_mkSlice_rco]
@[grind =]
public theorem mkSlice_rii_eq_mkSlice_rco {xs : Array α} :
xs[*...*] = xs[0...xs.size] := by
simp
public theorem mkSlice_rii_eq_mkSlice_rio_min {xs : Array α} :
xs[*...*] = xs[*...xs.size] := by
simp [mkSlice_rco_eq_mkSlice_rco_min]
@[simp, grind =]
public theorem toList_mkSlice_rii {xs : Array α} :
xs[*...*].toList = xs.toList := by
rw [mkSlice_rii_eq_mkSlice_rci, toList_mkSlice_rci, List.drop_zero]
@[simp]
public theorem toArray_mkSlice_rii {xs : Array α} :
xs[*...*].toArray = xs := by
simp
@[simp, grind =]
public theorem size_mkSlice_rii {xs : Array α} :
xs[*...*].size = xs.size := by
simp [← Subarray.length_toList]
@[simp]
public theorem array_mkSlice_rii {xs : Array α} :
xs[*...*].array = xs := by
simp
@[simp, grind =]
public theorem start_mkSlice_rii {xs : Array α} :
xs[*...*].start = 0 := by
simp
@[simp, grind =]
public theorem stop_mkSlice_rii {xs : Array α} :
xs[*...*].stop = xs.size := by
simp [Std.Rii.Sliceable.mkSlice]
end Array
section SubarraySlices
namespace Subarray
@[simp, grind =]
public theorem toList_mkSlice_rco {xs : Subarray α} {lo hi : Nat} :
xs[lo...hi].toList = (xs.toList.take hi).drop lo := by
simp only [Std.Rco.Sliceable.mkSlice, Std.Rco.HasRcoIntersection.intersection, toList_eq,
Array.start_toSubarray, Array.stop_toSubarray, Array.toList_extract, List.take_drop,
List.take_take]
rw [Nat.add_sub_cancel' (by omega)]
simp [Subarray.size, ← Array.length_toList, ← List.take_eq_take_min, Nat.add_comm xs.start]
@[simp, grind =]
public theorem toArray_mkSlice_rco {xs : Subarray α} {lo hi : Nat} :
xs[lo...hi].toArray = xs.toArray.extract lo hi := by
simp [← Subarray.toArray_toList, List.drop_take]
@[simp, grind =]
public theorem mkSlice_rcc_eq_mkSlice_rco {xs : Subarray α} {lo hi : Nat} :
xs[lo...=hi] = xs[lo...(hi + 1)] := by
simp [Std.Rcc.Sliceable.mkSlice, Std.Rco.Sliceable.mkSlice,
Std.Rcc.HasRcoIntersection.intersection, Std.Rco.HasRcoIntersection.intersection]
@[simp]
public theorem toList_mkSlice_rcc {xs : Subarray α} {lo hi : Nat} :
xs[lo...=hi].toList = (xs.toList.take (hi + 1)).drop lo := by
simp
@[simp]
public theorem toArray_mkSlice_rcc {xs : Subarray α} {lo hi : Nat} :
xs[lo...=hi].toArray = xs.toArray.extract lo (hi + 1) := by
simp
@[simp, grind =]
public theorem mkSlice_rci_eq_mkSlice_rco {xs : Subarray α} {lo : Nat} :
xs[lo...*] = xs[lo...xs.size] := by
simp [Std.Rci.Sliceable.mkSlice, Std.Rco.Sliceable.mkSlice,
Std.Rci.HasRcoIntersection.intersection, Std.Rco.HasRcoIntersection.intersection]
@[simp]
public theorem toList_mkSlice_rci {xs : Subarray α} {lo : Nat} :
xs[lo...*].toList = xs.toList.drop lo := by
rw [mkSlice_rci_eq_mkSlice_rco, toList_mkSlice_rco, ← Subarray.length_toList, List.take_length]
@[simp]
public theorem toArray_mkSlice_rci {xs : Subarray α} {lo : Nat} :
xs[lo...*].toArray = xs.toArray.extract lo := by
simp
@[simp]
public theorem mkSlice_roc_eq_mkSlice_roo {xs : Subarray α} {lo hi : Nat} :
xs[lo<...=hi] = xs[lo<...(hi + 1)] := by
simp [Std.Roc.Sliceable.mkSlice, Std.Roo.Sliceable.mkSlice,
Std.Roc.HasRcoIntersection.intersection, Std.Roo.HasRcoIntersection.intersection]
@[simp, grind =]
public theorem mkSlice_roo_eq_mkSlice_rco {xs : Subarray α} {lo hi : Nat} :
xs[lo<...hi] = xs[(lo + 1)...hi] := by
simp [Std.Roo.Sliceable.mkSlice, Std.Rco.Sliceable.mkSlice,
Std.Roo.HasRcoIntersection.intersection, Std.Rco.HasRcoIntersection.intersection]
@[grind =]
public theorem mkSlice_roc_eq_mkSlice_rco {xs : Subarray α} {lo hi : Nat} :
xs[lo<...=hi] = xs[(lo + 1)...(hi + 1)] := by
simp
@[simp]
public theorem toList_mkSlice_roo {xs : Subarray α} {lo hi : Nat} :
xs[lo<...hi].toList = (xs.toList.take hi).drop (lo + 1) := by
simp
@[simp]
public theorem toArray_mkSlice_roo {xs : Subarray α} {lo hi : Nat} :
xs[lo<...hi].toArray = xs.toArray.extract (lo + 1) hi := by
simp
@[simp]
public theorem mkSlice_roc_eq_mkSlice_rcc {xs : Subarray α} {lo hi : Nat} :
xs[lo<...=hi] = xs[(lo + 1)...=hi] := by
simp
@[simp]
public theorem toList_mkSlice_roc {xs : Subarray α} {lo hi : Nat} :
xs[lo<...=hi].toList = (xs.toList.take (hi + 1)).drop (lo + 1) := by
simp
@[simp]
public theorem toArray_mkSlice_roc {xs : Subarray α} {lo hi : Nat} :
xs[lo<...=hi].toArray = xs.toArray.extract (lo + 1) (hi + 1) := by
simp
@[simp]
public theorem mkSlice_roi_eq_mkSlice_rci {xs : Subarray α} {lo : Nat} :
xs[lo<...*] = xs[(lo + 1)...*] := by
simp [Std.Roi.Sliceable.mkSlice, Std.Rci.Sliceable.mkSlice,
Std.Roi.HasRcoIntersection.intersection, Std.Rci.HasRcoIntersection.intersection]
@[grind =]
public theorem mkSlice_roi_eq_mkSlice_rco {xs : Subarray α} {lo : Nat} :
xs[lo<...*] = xs[(lo + 1)...xs.size] := by
simp
@[simp]
public theorem toList_mkSlice_roi {xs : Subarray α} {lo : Nat} :
xs[lo<...*].toList = xs.toList.drop (lo + 1) := by
rw [mkSlice_roi_eq_mkSlice_rci, toList_mkSlice_rci]
@[simp]
public theorem toArray_mkSlice_roi {xs : Subarray α} {lo : Nat} :
xs[lo<...*].toArray = xs.toArray.extract (lo + 1) := by
simp
@[simp]
public theorem mkSlice_ric_eq_mkSlice_rio {xs : Subarray α} {hi : Nat} :
xs[*...=hi] = xs[*...(hi + 1)] := by
simp [Std.Ric.Sliceable.mkSlice, Std.Rio.Sliceable.mkSlice,
Std.Ric.HasRcoIntersection.intersection, Std.Rio.HasRcoIntersection.intersection]
@[simp, grind =]
public theorem mkSlice_rio_eq_mkSlice_rco {xs : Subarray α} {hi : Nat} :
xs[*...hi] = xs[0...hi] := by
simp [Std.Rio.Sliceable.mkSlice, Std.Rco.Sliceable.mkSlice,
Std.Rio.HasRcoIntersection.intersection, Std.Rco.HasRcoIntersection.intersection]
@[grind =]
public theorem mkSlice_ric_eq_mkSlice_rco {xs : Subarray α} {hi : Nat} :
xs[*...=hi] = xs[0...(hi + 1)] := by
simp
@[simp]
public theorem toList_mkSlice_rio {xs : Subarray α} {hi : Nat} :
xs[*...hi].toList = xs.toList.take hi := by
simp
@[simp]
public theorem toArray_mkSlice_rio {xs : Subarray α} {hi : Nat} :
xs[*...hi].toArray = xs.toArray.extract 0 hi := by
simp
@[simp]
public theorem mkSlice_ric_eq_mkSlice_rcc {xs : Subarray α} {hi : Nat} :
xs[*...=hi] = xs[0...=hi] := by
simp [Std.Ric.Sliceable.mkSlice, Std.Rco.Sliceable.mkSlice,
Std.Ric.HasRcoIntersection.intersection, Std.Rco.HasRcoIntersection.intersection]
@[simp]
public theorem toList_mkSlice_ric {xs : Subarray α} {hi : Nat} :
xs[*...=hi].toList = xs.toList.take (hi + 1) := by
simp
@[simp]
public theorem toArray_mkSlice_ric {xs : Subarray α} {hi : Nat} :
xs[*...=hi].toArray = xs.toArray.extract 0 (hi + 1) := by
simp
@[simp, grind =]
public theorem mkSlice_rii {xs : Subarray α} :
xs[*...*] = xs := by
simp [Std.Rii.Sliceable.mkSlice]
@[simp]
public theorem toList_mkSlice_rii {xs : Subarray α} :
xs[*...*].toList = xs.toList := by
rw [mkSlice_rii]
@[simp]
public theorem toArray_mkSlice_rii {xs : Subarray α} :
xs[*...*].toArray = xs.toArray := by
rw [mkSlice_rii]
end Subarray
end SubarraySlices