| 1 |
-- https://github.com/leanprover/lean/raw/master/library/data/dlist.lean |
| 2 |
/- |
| 3 |
Copyright (c) 2017 Microsoft Corporation. All rights reserved. |
| 4 |
Released under Apache 2.0 license as described in the file LICENSE. |
| 5 |
Author: Leonardo de Moura |
| 6 |
-/ |
| 7 |
universes u |
| 8 |
/-- |
| 9 |
A difference list is a function that, given a list, returns the original |
| 10 |
contents of the difference list prepended to the given list. |
| 11 |
|
| 12 |
This structure supports `O(1)` `append` and `concat` operations on lists, making it |
| 13 |
useful for append-heavy uses such as logging and pretty printing. |
| 14 |
-/ |
| 15 |
structure dlist (α : Type u) := |
| 16 |
(apply : list α → list α) |
| 17 |
(invariant : ∀ l, apply l = apply [] ++ l) |
| 18 |
|
| 19 |
namespace dlist |
| 20 |
open function |
| 21 |
variables {α : Type u} |
| 22 |
|
| 23 |
local notation `♯`:max := by abstract {intros, rsimp} |
| 24 |
|
| 25 |
/-- Convert a list to a dlist -/ |
| 26 |
def of_list (l : list α) : dlist α := |
| 27 |
⟨append l, ♯⟩ |
| 28 |
|
| 29 |
/-- Convert a lazily-evaluated list to a dlist -/ |
| 30 |
def lazy_of_list (l : thunk (list α)) : dlist α := |
| 31 |
⟨λ xs, l () ++ xs, ♯⟩ |
| 32 |
|
| 33 |
/-- Convert a dlist to a list -/ |
| 34 |
def to_list : dlist α → list α |
| 35 |
| ⟨xs, _⟩ := xs [] |
| 36 |
|
| 37 |
/-- Create a dlist containing no elements -/ |
| 38 |
def empty : dlist α := |
| 39 |
⟨id, ♯⟩ |
| 40 |
|
| 41 |
local notation a `::_`:max := list.cons a |
| 42 |
|
| 43 |
/-- Create dlist with a single element -/ |
| 44 |
def singleton (x : α) : dlist α := |
| 45 |
⟨x::_, ♯⟩ |
| 46 |
|
| 47 |
local attribute [simp] function.comp |
| 48 |
|
| 49 |
/-- `O(1)` Prepend a single element to a dlist -/ |
| 50 |
def cons (x : α) : dlist α → dlist α |
| 51 |
| ⟨xs, h⟩ := ⟨x::_ ∘ xs, ♯⟩ |
| 52 |
|
| 53 |
/-- `O(1)` Append a single element to a dlist -/ |
| 54 |
def concat (x : α) : dlist α → dlist α |
| 55 |
| ⟨xs, h⟩ := ⟨xs ∘ x::_, ♯⟩ |
| 56 |
|
| 57 |
/-- `O(1)` Append dlists -/ |
| 58 |
protected def append : dlist α → dlist α → dlist α |
| 59 |
| ⟨xs, h₁⟩ ⟨ys, h₂⟩ := ⟨xs ∘ ys, ♯⟩ |
| 60 |
|
| 61 |
instance : has_append (dlist α) := |
| 62 |
⟨dlist.append⟩ |
| 63 |
|
| 64 |
local attribute [simp] of_list to_list empty singleton cons concat dlist.append |
| 65 |
|
| 66 |
lemma to_list_of_list (l : list α) : to_list (of_list l) = l := |
| 67 |
by cases l; simp |
| 68 |
|
| 69 |
lemma of_list_to_list (l : dlist α) : of_list (to_list l) = l := |
| 70 |
begin |
| 71 |
cases l with xs, |
| 72 |
have h : append (xs []) = xs, |
| 73 |
{ intros, funext x, simp [l_invariant x] }, |
| 74 |
simp [h] |
| 75 |
end |
| 76 |
|
| 77 |
lemma to_list_empty : to_list (@empty α) = [] := |
| 78 |
by simp |
| 79 |
|
| 80 |
lemma to_list_singleton (x : α) : to_list (singleton x) = [x] := |
| 81 |
by simp |
| 82 |
|
| 83 |
lemma to_list_append (l₁ l₂ : dlist α) : to_list (l₁ ++ l₂) = to_list l₁ ++ to_list l₂ := |
| 84 |
show to_list (dlist.append l₁ l₂) = to_list l₁ ++ to_list l₂, from |
| 85 |
by cases l₁; cases l₂; simp; rsimp |
| 86 |
|
| 87 |
lemma to_list_cons (x : α) (l : dlist α) : to_list (cons x l) = x :: to_list l := |
| 88 |
by cases l; rsimp |
| 89 |
|
| 90 |
lemma to_list_concat (x : α) (l : dlist α) : to_list (concat x l) = to_list l ++ [x] := |
| 91 |
by cases l; simp; rsimp |
| 92 |
|
| 93 |
section transfer |
| 94 |
|
| 95 |
protected def rel_dlist_list (d : dlist α) (l : list α) : Prop := |
| 96 |
to_list d = l |
| 97 |
|
| 98 |
instance bi_total_rel_dlist_list : @relator.bi_total (dlist α) (list α) dlist.rel_dlist_list := |
| 99 |
⟨assume d, ⟨to_list d, rfl⟩, assume l, ⟨of_list l, to_list_of_list l⟩⟩ |
| 100 |
|
| 101 |
protected lemma rel_eq : |
| 102 |
(dlist.rel_dlist_list ⇒ dlist.rel_dlist_list ⇒ iff) (@eq (dlist α)) eq |
| 103 |
| l₁ ._ rfl l₂ ._ rfl := ⟨congr_arg to_list, |
| 104 |
assume : to_list l₁ = to_list l₂, |
| 105 |
have of_list (to_list l₁) = of_list (to_list l₂), from congr_arg of_list this, |
| 106 |
by simp [of_list_to_list] at this; assumption⟩ |
| 107 |
|
| 108 |
protected lemma rel_empty : dlist.rel_dlist_list (@empty α) [] := |
| 109 |
to_list_empty |
| 110 |
|
| 111 |
protected lemma rel_singleton : (@eq α ⇒ dlist.rel_dlist_list) (λx, singleton x) (λx, [x]) |
| 112 |
| ._ x rfl := to_list_singleton x |
| 113 |
|
| 114 |
protected lemma rel_append : |
| 115 |
(dlist.rel_dlist_list ⇒ dlist.rel_dlist_list ⇒ dlist.rel_dlist_list) (λ(x y : dlist α), x ++ y) (λx y, x ++ y) |
| 116 |
| l₁ ._ rfl l₂ ._ rfl := to_list_append l₁ l₂ |
| 117 |
|
| 118 |
protected lemma rel_cons : |
| 119 |
(@eq α ⇒ dlist.rel_dlist_list ⇒ dlist.rel_dlist_list) cons (λx y, x :: y) |
| 120 |
| x ._ rfl l ._ rfl := to_list_cons x l |
| 121 |
|
| 122 |
protected lemma rel_concat : |
| 123 |
(@eq α ⇒ dlist.rel_dlist_list ⇒ dlist.rel_dlist_list) concat (λx y, y ++ [x]) |
| 124 |
| x ._ rfl l ._ rfl := to_list_concat x l |
| 125 |
|
| 126 |
protected meta def transfer : tactic unit := do |
| 127 |
_root_.transfer.transfer [`relator.rel_forall_of_total, `dlist.rel_eq, `dlist.rel_empty, |
| 128 |
`dlist.rel_singleton, `dlist.rel_append, `dlist.rel_cons, `dlist.rel_concat] |
| 129 |
|
| 130 |
example : ∀(a b c : dlist α), a ++ (b ++ c) = (a ++ b) ++ c := |
| 131 |
begin |
| 132 |
dlist.transfer, |
| 133 |
intros, |
| 134 |
simp |
| 135 |
end |
| 136 |
|
| 137 |
example : ∀(a : α), singleton a ++ empty = singleton a := |
| 138 |
begin |
| 139 |
dlist.transfer, |
| 140 |
intros, |
| 141 |
simp |
| 142 |
end |
| 143 |
|
| 144 |
end transfer |
| 145 |
|
| 146 |
end dlist |