update in ground

[helm.git] / matita / matita / contribs / lambdadelta / ground / lib / list_append.ma

diff --git a/matita/matita/contribs/lambdadelta/ground/lib/list_append.ma b/matita/matita/contribs/lambdadelta/ground/lib/list_append.ma
new file mode 100644 (file)
index 0000000..2dcf8e5
--- /dev/null
+++ b/matita/matita/contribs/lambdadelta/ground/lib/list_append.ma
@@ -0,0 +1,58 @@
+(**************************************************************************)
+(*       ___                                                              *)
+(*      ||M||                                                             *)
+(*      ||A||       A project by Andrea Asperti                           *)
+(*      ||T||                                                             *)
+(*      ||I||       Developers:                                           *)
+(*      ||T||         The HELM team.                                      *)
+(*      ||A||         http://helm.cs.unibo.it                             *)
+(*      \   /                                                             *)
+(*       \ /        This file is distributed under the terms of the       *)
+(*        v         GNU General Public License Version 2                  *)
+(*                                                                        *)
+(**************************************************************************)
+
+include "ground/notation/functions/oplus_3.ma".
+include "ground/lib/list.ma".
+
+(* APPEND FOR LISTS *********************************************************)
+
+rec definition list_append A (l1:list A) (l2:list A) on l1 ≝ match l1 with
+[ list_empty       ⇒ l2
+| list_lcons hd tl ⇒ hd ⨮ (list_append A tl l2)
+].
+
+interpretation
+  "append (lists)"
+  'OPlus A l1 l2 = (list_append A l1 l2).
+
+(* Basic constructions ******************************************************)
+
+lemma list_append_empty_sn (A):
+      ∀l2. l2 = Ⓔ ⨁{A} l2.
+// qed.
+
+lemma list_append_lcons_sn (A):
+      ∀a,l1,l2. a ⨮ l1 ⨁ l2 = (a⨮l1) ⨁{A} l2.
+// qed.
+
+(* Advanced constructions ***************************************************)
+
+lemma list_append_empty_dx (A):
+      ∀l1. l1 = l1 ⨁{A} Ⓔ.
+#A #l1 elim l1 -l1
+[ <list_append_empty_sn //
+| #hd #tl #IH <list_append_lcons_sn <IH //
+]
+qed.
+
+lemma list_append_assoc (A):
+      associative … (list_append A).
+#A #l1 elim l1 -l1
+[ <list_append_empty_sn //
+| #a1 #l1 #IH *
+  [ #l3 <list_append_empty_dx <list_append_empty_sn //
+  | #a2 #l2 #l3 <list_append_lcons_sn <list_append_lcons_sn <IH //
+  ]
+]
+qed.