src/HOL/Library/NList.thy
author wenzelm
Mon, 11 Sep 2023 19:30:48 +0200
changeset 78659 b5f3d1051b13
parent 76032 c2812ca1a455
child 78834 35b2282fbc77
permissions -rw-r--r--
tuned;
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
76032
c2812ca1a455 tuned whitespace;
wenzelm
parents: 76031
diff changeset
     1
(*  Author:     Tobias Nipkow
76031
42e3c5f9e4c6 eliminated DOS line endings;
wenzelm
parents: 75805
diff changeset
     2
    Copyright   2000 TUM
42e3c5f9e4c6 eliminated DOS line endings;
wenzelm
parents: 75805
diff changeset
     3
*)
42e3c5f9e4c6 eliminated DOS line endings;
wenzelm
parents: 75805
diff changeset
     4
42e3c5f9e4c6 eliminated DOS line endings;
wenzelm
parents: 75805
diff changeset
     5
section \<open>Fixed Length Lists\<close>
42e3c5f9e4c6 eliminated DOS line endings;
wenzelm
parents: 75805
diff changeset
     6
42e3c5f9e4c6 eliminated DOS line endings;
wenzelm
parents: 75805
diff changeset
     7
theory NList
42e3c5f9e4c6 eliminated DOS line endings;
wenzelm
parents: 75805
diff changeset
     8
imports Main
42e3c5f9e4c6 eliminated DOS line endings;
wenzelm
parents: 75805
diff changeset
     9
begin
42e3c5f9e4c6 eliminated DOS line endings;
wenzelm
parents: 75805
diff changeset
    10
42e3c5f9e4c6 eliminated DOS line endings;
wenzelm
parents: 75805
diff changeset
    11
definition nlists :: "nat \<Rightarrow> 'a set \<Rightarrow> 'a list set"
42e3c5f9e4c6 eliminated DOS line endings;
wenzelm
parents: 75805
diff changeset
    12
  where "nlists n A = {xs. size xs = n \<and> set xs \<subseteq> A}"
42e3c5f9e4c6 eliminated DOS line endings;
wenzelm
parents: 75805
diff changeset
    13
42e3c5f9e4c6 eliminated DOS line endings;
wenzelm
parents: 75805
diff changeset
    14
lemma nlistsI: "\<lbrakk> size xs = n; set xs \<subseteq> A \<rbrakk> \<Longrightarrow> xs \<in> nlists n A"
42e3c5f9e4c6 eliminated DOS line endings;
wenzelm
parents: 75805
diff changeset
    15
  by (simp add: nlists_def)
42e3c5f9e4c6 eliminated DOS line endings;
wenzelm
parents: 75805
diff changeset
    16
42e3c5f9e4c6 eliminated DOS line endings;
wenzelm
parents: 75805
diff changeset
    17
text \<open>These [simp] attributes are double-edged.
42e3c5f9e4c6 eliminated DOS line endings;
wenzelm
parents: 75805
diff changeset
    18
 Many proofs in Jinja rely on it but they can degrade performance.\<close>
42e3c5f9e4c6 eliminated DOS line endings;
wenzelm
parents: 75805
diff changeset
    19
42e3c5f9e4c6 eliminated DOS line endings;
wenzelm
parents: 75805
diff changeset
    20
lemma nlistsE_length [simp]: "xs \<in> nlists n A \<Longrightarrow> size xs = n"
42e3c5f9e4c6 eliminated DOS line endings;
wenzelm
parents: 75805
diff changeset
    21
  by (simp add: nlists_def)
42e3c5f9e4c6 eliminated DOS line endings;
wenzelm
parents: 75805
diff changeset
    22
42e3c5f9e4c6 eliminated DOS line endings;
wenzelm
parents: 75805
diff changeset
    23
lemma less_lengthI: "\<lbrakk> xs \<in> nlists n A; p < n \<rbrakk> \<Longrightarrow> p < size xs"
42e3c5f9e4c6 eliminated DOS line endings;
wenzelm
parents: 75805
diff changeset
    24
by (simp)
42e3c5f9e4c6 eliminated DOS line endings;
wenzelm
parents: 75805
diff changeset
    25
42e3c5f9e4c6 eliminated DOS line endings;
wenzelm
parents: 75805
diff changeset
    26
lemma nlistsE_set[simp]: "xs \<in> nlists n A \<Longrightarrow> set xs \<subseteq> A"
42e3c5f9e4c6 eliminated DOS line endings;
wenzelm
parents: 75805
diff changeset
    27
unfolding nlists_def by (simp)
42e3c5f9e4c6 eliminated DOS line endings;
wenzelm
parents: 75805
diff changeset
    28
42e3c5f9e4c6 eliminated DOS line endings;
wenzelm
parents: 75805
diff changeset
    29
lemma nlists_mono:
42e3c5f9e4c6 eliminated DOS line endings;
wenzelm
parents: 75805
diff changeset
    30
assumes "A \<subseteq> B" shows "nlists n A \<subseteq> nlists n B"
42e3c5f9e4c6 eliminated DOS line endings;
wenzelm
parents: 75805
diff changeset
    31
proof
42e3c5f9e4c6 eliminated DOS line endings;
wenzelm
parents: 75805
diff changeset
    32
  fix xs assume "xs \<in> nlists n A"
42e3c5f9e4c6 eliminated DOS line endings;
wenzelm
parents: 75805
diff changeset
    33
  then obtain size: "size xs = n" and inA: "set xs \<subseteq> A" by (simp)
42e3c5f9e4c6 eliminated DOS line endings;
wenzelm
parents: 75805
diff changeset
    34
  with assms have "set xs \<subseteq> B" by simp
42e3c5f9e4c6 eliminated DOS line endings;
wenzelm
parents: 75805
diff changeset
    35
  with size show "xs \<in> nlists n B" by(clarsimp intro!: nlistsI)
42e3c5f9e4c6 eliminated DOS line endings;
wenzelm
parents: 75805
diff changeset
    36
qed
42e3c5f9e4c6 eliminated DOS line endings;
wenzelm
parents: 75805
diff changeset
    37
42e3c5f9e4c6 eliminated DOS line endings;
wenzelm
parents: 75805
diff changeset
    38
lemma nlists_n_0 [simp]: "nlists 0 A = {[]}"
42e3c5f9e4c6 eliminated DOS line endings;
wenzelm
parents: 75805
diff changeset
    39
unfolding nlists_def by (auto)
42e3c5f9e4c6 eliminated DOS line endings;
wenzelm
parents: 75805
diff changeset
    40
42e3c5f9e4c6 eliminated DOS line endings;
wenzelm
parents: 75805
diff changeset
    41
lemma in_nlists_Suc_iff: "(xs \<in> nlists (Suc n) A) = (\<exists>y\<in>A. \<exists>ys \<in> nlists n A. xs = y#ys)"
42e3c5f9e4c6 eliminated DOS line endings;
wenzelm
parents: 75805
diff changeset
    42
unfolding nlists_def by (cases "xs") auto
42e3c5f9e4c6 eliminated DOS line endings;
wenzelm
parents: 75805
diff changeset
    43
42e3c5f9e4c6 eliminated DOS line endings;
wenzelm
parents: 75805
diff changeset
    44
lemma Cons_in_nlists_Suc [iff]: "(x#xs \<in> nlists (Suc n) A) \<longleftrightarrow> (x\<in>A \<and> xs \<in> nlists n A)"
42e3c5f9e4c6 eliminated DOS line endings;
wenzelm
parents: 75805
diff changeset
    45
unfolding nlists_def by (auto)
42e3c5f9e4c6 eliminated DOS line endings;
wenzelm
parents: 75805
diff changeset
    46
42e3c5f9e4c6 eliminated DOS line endings;
wenzelm
parents: 75805
diff changeset
    47
lemma nlists_not_empty: "A\<noteq>{} \<Longrightarrow> \<exists>xs. xs \<in> nlists n A"
42e3c5f9e4c6 eliminated DOS line endings;
wenzelm
parents: 75805
diff changeset
    48
by (induct "n") (auto simp: in_nlists_Suc_iff)
42e3c5f9e4c6 eliminated DOS line endings;
wenzelm
parents: 75805
diff changeset
    49
42e3c5f9e4c6 eliminated DOS line endings;
wenzelm
parents: 75805
diff changeset
    50
42e3c5f9e4c6 eliminated DOS line endings;
wenzelm
parents: 75805
diff changeset
    51
lemma nlistsE_nth_in: "\<lbrakk> xs \<in> nlists n A; i < n \<rbrakk> \<Longrightarrow> xs!i \<in> A"
42e3c5f9e4c6 eliminated DOS line endings;
wenzelm
parents: 75805
diff changeset
    52
unfolding nlists_def by (auto)
42e3c5f9e4c6 eliminated DOS line endings;
wenzelm
parents: 75805
diff changeset
    53
42e3c5f9e4c6 eliminated DOS line endings;
wenzelm
parents: 75805
diff changeset
    54
lemma nlists_Cons_Suc [elim!]:
42e3c5f9e4c6 eliminated DOS line endings;
wenzelm
parents: 75805
diff changeset
    55
  "l#xs \<in> nlists n A \<Longrightarrow> (\<And>n'. n = Suc n' \<Longrightarrow> l \<in> A \<Longrightarrow> xs \<in> nlists n' A \<Longrightarrow> P) \<Longrightarrow> P"
42e3c5f9e4c6 eliminated DOS line endings;
wenzelm
parents: 75805
diff changeset
    56
unfolding nlists_def by (auto)
42e3c5f9e4c6 eliminated DOS line endings;
wenzelm
parents: 75805
diff changeset
    57
42e3c5f9e4c6 eliminated DOS line endings;
wenzelm
parents: 75805
diff changeset
    58
lemma nlists_appendE [elim!]:
42e3c5f9e4c6 eliminated DOS line endings;
wenzelm
parents: 75805
diff changeset
    59
  "a@b \<in> nlists n A \<Longrightarrow> (\<And>n1 n2. n=n1+n2 \<Longrightarrow> a \<in> nlists n1 A \<Longrightarrow> b \<in> nlists n2 A \<Longrightarrow> P) \<Longrightarrow> P"
42e3c5f9e4c6 eliminated DOS line endings;
wenzelm
parents: 75805
diff changeset
    60
proof -
42e3c5f9e4c6 eliminated DOS line endings;
wenzelm
parents: 75805
diff changeset
    61
  have "\<And>n. a@b \<in> nlists n A \<Longrightarrow> \<exists>n1 n2. n=n1+n2 \<and> a \<in> nlists n1 A \<and> b \<in> nlists n2 A"
42e3c5f9e4c6 eliminated DOS line endings;
wenzelm
parents: 75805
diff changeset
    62
    (is "\<And>n. ?list a n \<Longrightarrow> \<exists>n1 n2. ?P a n n1 n2")
42e3c5f9e4c6 eliminated DOS line endings;
wenzelm
parents: 75805
diff changeset
    63
  proof (induct a)
42e3c5f9e4c6 eliminated DOS line endings;
wenzelm
parents: 75805
diff changeset
    64
    fix n assume "?list [] n"
42e3c5f9e4c6 eliminated DOS line endings;
wenzelm
parents: 75805
diff changeset
    65
    hence "?P [] n 0 n" by simp
42e3c5f9e4c6 eliminated DOS line endings;
wenzelm
parents: 75805
diff changeset
    66
    thus "\<exists>n1 n2. ?P [] n n1 n2" by fast
42e3c5f9e4c6 eliminated DOS line endings;
wenzelm
parents: 75805
diff changeset
    67
  next
42e3c5f9e4c6 eliminated DOS line endings;
wenzelm
parents: 75805
diff changeset
    68
    fix n l ls
42e3c5f9e4c6 eliminated DOS line endings;
wenzelm
parents: 75805
diff changeset
    69
    assume "?list (l#ls) n"
42e3c5f9e4c6 eliminated DOS line endings;
wenzelm
parents: 75805
diff changeset
    70
    then obtain n' where n: "n = Suc n'" "l \<in> A" and n': "ls@b \<in> nlists n' A" by fastforce
42e3c5f9e4c6 eliminated DOS line endings;
wenzelm
parents: 75805
diff changeset
    71
    assume "\<And>n. ls @ b \<in> nlists n A \<Longrightarrow> \<exists>n1 n2. n = n1 + n2 \<and> ls \<in> nlists n1 A \<and> b \<in> nlists n2 A"
42e3c5f9e4c6 eliminated DOS line endings;
wenzelm
parents: 75805
diff changeset
    72
    from this and n' have "\<exists>n1 n2. n' = n1 + n2 \<and> ls \<in> nlists n1 A \<and> b \<in> nlists n2 A" .
42e3c5f9e4c6 eliminated DOS line endings;
wenzelm
parents: 75805
diff changeset
    73
    then obtain n1 n2 where "n' = n1 + n2" "ls \<in> nlists n1 A" "b \<in> nlists n2 A" by fast
42e3c5f9e4c6 eliminated DOS line endings;
wenzelm
parents: 75805
diff changeset
    74
    with n have "?P (l#ls) n (n1+1) n2" by simp
42e3c5f9e4c6 eliminated DOS line endings;
wenzelm
parents: 75805
diff changeset
    75
    thus "\<exists>n1 n2. ?P (l#ls) n n1 n2" by fastforce
42e3c5f9e4c6 eliminated DOS line endings;
wenzelm
parents: 75805
diff changeset
    76
  qed
42e3c5f9e4c6 eliminated DOS line endings;
wenzelm
parents: 75805
diff changeset
    77
  moreover assume "a@b \<in> nlists n A" "\<And>n1 n2. n=n1+n2 \<Longrightarrow> a \<in> nlists n1 A \<Longrightarrow> b \<in> nlists n2 A \<Longrightarrow> P"
42e3c5f9e4c6 eliminated DOS line endings;
wenzelm
parents: 75805
diff changeset
    78
  ultimately show ?thesis by blast
42e3c5f9e4c6 eliminated DOS line endings;
wenzelm
parents: 75805
diff changeset
    79
qed
42e3c5f9e4c6 eliminated DOS line endings;
wenzelm
parents: 75805
diff changeset
    80
42e3c5f9e4c6 eliminated DOS line endings;
wenzelm
parents: 75805
diff changeset
    81
42e3c5f9e4c6 eliminated DOS line endings;
wenzelm
parents: 75805
diff changeset
    82
lemma nlists_update_in_list [simp, intro!]:
42e3c5f9e4c6 eliminated DOS line endings;
wenzelm
parents: 75805
diff changeset
    83
  "\<lbrakk> xs \<in> nlists n A; x\<in>A \<rbrakk> \<Longrightarrow> xs[i := x] \<in> nlists n A"
42e3c5f9e4c6 eliminated DOS line endings;
wenzelm
parents: 75805
diff changeset
    84
  by (metis length_list_update nlistsE_length nlistsE_set nlistsI set_update_subsetI)
42e3c5f9e4c6 eliminated DOS line endings;
wenzelm
parents: 75805
diff changeset
    85
42e3c5f9e4c6 eliminated DOS line endings;
wenzelm
parents: 75805
diff changeset
    86
lemma nlists_appendI [intro?]:
42e3c5f9e4c6 eliminated DOS line endings;
wenzelm
parents: 75805
diff changeset
    87
  "\<lbrakk> a \<in> nlists n A; b \<in> nlists m A \<rbrakk> \<Longrightarrow> a @ b \<in> nlists (n+m) A"
42e3c5f9e4c6 eliminated DOS line endings;
wenzelm
parents: 75805
diff changeset
    88
unfolding nlists_def by (auto)
42e3c5f9e4c6 eliminated DOS line endings;
wenzelm
parents: 75805
diff changeset
    89
42e3c5f9e4c6 eliminated DOS line endings;
wenzelm
parents: 75805
diff changeset
    90
lemma nlists_append:
42e3c5f9e4c6 eliminated DOS line endings;
wenzelm
parents: 75805
diff changeset
    91
  "xs @ ys \<in> nlists k A \<longleftrightarrow>
42e3c5f9e4c6 eliminated DOS line endings;
wenzelm
parents: 75805
diff changeset
    92
   k = length(xs @ ys) \<and> xs \<in> nlists (length xs) A \<and> ys \<in> nlists (length ys) A"
42e3c5f9e4c6 eliminated DOS line endings;
wenzelm
parents: 75805
diff changeset
    93
unfolding nlists_def by (auto)
42e3c5f9e4c6 eliminated DOS line endings;
wenzelm
parents: 75805
diff changeset
    94
42e3c5f9e4c6 eliminated DOS line endings;
wenzelm
parents: 75805
diff changeset
    95
lemma nlists_map [simp]: "(map f xs \<in> nlists (size xs) A) = (f ` set xs \<subseteq> A)"
42e3c5f9e4c6 eliminated DOS line endings;
wenzelm
parents: 75805
diff changeset
    96
unfolding nlists_def by (auto)
42e3c5f9e4c6 eliminated DOS line endings;
wenzelm
parents: 75805
diff changeset
    97
42e3c5f9e4c6 eliminated DOS line endings;
wenzelm
parents: 75805
diff changeset
    98
lemma nlists_replicateI [intro]: "x \<in> A \<Longrightarrow> replicate n x \<in> nlists n A"
42e3c5f9e4c6 eliminated DOS line endings;
wenzelm
parents: 75805
diff changeset
    99
 by (induct n) auto
42e3c5f9e4c6 eliminated DOS line endings;
wenzelm
parents: 75805
diff changeset
   100
42e3c5f9e4c6 eliminated DOS line endings;
wenzelm
parents: 75805
diff changeset
   101
lemma nlists_set[code]: "nlists n (set xs) = set (List.n_lists n xs)"
42e3c5f9e4c6 eliminated DOS line endings;
wenzelm
parents: 75805
diff changeset
   102
unfolding nlists_def by (rule sym, induct n) (auto simp: image_iff length_Suc_conv)
42e3c5f9e4c6 eliminated DOS line endings;
wenzelm
parents: 75805
diff changeset
   103
42e3c5f9e4c6 eliminated DOS line endings;
wenzelm
parents: 75805
diff changeset
   104
end