Debian Codegraph @

tests/inputs/dlist.lean

raw
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