src/HOL/Word/BinBoolList.thy
author chaieb
Sat Oct 20 12:09:33 2007 +0200 (2007-10-20)
changeset 25112 98824cc791c0
parent 24465 70f0214b3ecc
child 25134 3d4953e88449
permissions -rw-r--r--
fixed proofs
kleing@24333
     1
(* 
kleing@24333
     2
  ID:     $Id$
kleing@24333
     3
  Author: Jeremy Dawson, NICTA
kleing@24333
     4
kleing@24333
     5
  contains theorems to do with integers, expressed using Pls, Min, BIT,
kleing@24333
     6
  theorems linking them to lists of booleans, and repeated splitting 
kleing@24333
     7
  and concatenation.
kleing@24333
     8
*) 
kleing@24333
     9
kleing@24333
    10
header "Bool lists and integers"
kleing@24333
    11
kleing@24333
    12
theory BinBoolList imports BinOperations begin
kleing@24333
    13
huffman@24465
    14
subsection "Arithmetic in terms of bool lists"
huffman@24465
    15
huffman@24465
    16
consts (* arithmetic operations in terms of the reversed bool list,
huffman@24465
    17
  assuming input list(s) the same length, and don't extend them *)
huffman@24465
    18
  rbl_succ :: "bool list => bool list"
huffman@24465
    19
  rbl_pred :: "bool list => bool list"
huffman@24465
    20
  rbl_add :: "bool list => bool list => bool list"
huffman@24465
    21
  rbl_mult :: "bool list => bool list => bool list"
huffman@24465
    22
huffman@24465
    23
primrec 
huffman@24465
    24
  Nil: "rbl_succ Nil = Nil"
huffman@24465
    25
  Cons: "rbl_succ (x # xs) = (if x then False # rbl_succ xs else True # xs)"
huffman@24465
    26
huffman@24465
    27
primrec 
huffman@24465
    28
  Nil : "rbl_pred Nil = Nil"
huffman@24465
    29
  Cons : "rbl_pred (x # xs) = (if x then False # xs else True # rbl_pred xs)"
huffman@24465
    30
huffman@24465
    31
primrec (* result is length of first arg, second arg may be longer *)
huffman@24465
    32
  Nil : "rbl_add Nil x = Nil"
huffman@24465
    33
  Cons : "rbl_add (y # ys) x = (let ws = rbl_add ys (tl x) in 
huffman@24465
    34
    (y ~= hd x) # (if hd x & y then rbl_succ ws else ws))"
huffman@24465
    35
huffman@24465
    36
primrec (* result is length of first arg, second arg may be longer *)
huffman@24465
    37
  Nil : "rbl_mult Nil x = Nil"
huffman@24465
    38
  Cons : "rbl_mult (y # ys) x = (let ws = False # rbl_mult ys x in 
huffman@24465
    39
    if y then rbl_add ws x else ws)"
kleing@24333
    40
kleing@24333
    41
lemma tl_take: "tl (take n l) = take (n - 1) (tl l)"
kleing@24333
    42
  apply (cases n, clarsimp)
kleing@24333
    43
  apply (cases l, auto)
kleing@24333
    44
  done
kleing@24333
    45
kleing@24333
    46
lemma take_butlast [rule_format] :
kleing@24333
    47
  "ALL n. n < length l --> take n (butlast l) = take n l"
kleing@24333
    48
  apply (induct l, clarsimp)
kleing@24333
    49
  apply clarsimp
kleing@24333
    50
  apply (case_tac n)
kleing@24333
    51
  apply auto
kleing@24333
    52
  done
kleing@24333
    53
kleing@24333
    54
lemma butlast_take [rule_format] :
kleing@24333
    55
  "ALL n. n <= length l --> butlast (take n l) = take (n - 1) l"
kleing@24333
    56
  apply (induct l, clarsimp)
kleing@24333
    57
  apply clarsimp
kleing@24333
    58
  apply (case_tac "n")
kleing@24333
    59
   apply safe
kleing@24333
    60
   apply simp_all
kleing@24333
    61
  apply (case_tac "nat")
kleing@24333
    62
   apply auto
kleing@24333
    63
  done
kleing@24333
    64
kleing@24333
    65
lemma butlast_drop [rule_format] :
kleing@24333
    66
  "ALL n. butlast (drop n l) = drop n (butlast l)"
kleing@24333
    67
  apply (induct l)
kleing@24333
    68
   apply clarsimp
kleing@24333
    69
  apply clarsimp
kleing@24333
    70
  apply safe
kleing@24333
    71
   apply ((case_tac n, auto)[1])+
kleing@24333
    72
  done
kleing@24333
    73
kleing@24333
    74
lemma butlast_power:
kleing@24333
    75
  "(butlast ^ n) bl = take (length bl - n) bl"
kleing@24333
    76
  by (induct n) (auto simp: butlast_take)
kleing@24333
    77
kleing@24333
    78
lemma bin_to_bl_aux_Pls_minus_simp:
kleing@24333
    79
  "0 < n ==> bin_to_bl_aux n Numeral.Pls bl = 
kleing@24333
    80
    bin_to_bl_aux (n - 1) Numeral.Pls (False # bl)"
kleing@24333
    81
  by (cases n) auto
kleing@24333
    82
kleing@24333
    83
lemma bin_to_bl_aux_Min_minus_simp:
kleing@24333
    84
  "0 < n ==> bin_to_bl_aux n Numeral.Min bl = 
kleing@24333
    85
    bin_to_bl_aux (n - 1) Numeral.Min (True # bl)"
kleing@24333
    86
  by (cases n) auto
kleing@24333
    87
kleing@24333
    88
lemma bin_to_bl_aux_Bit_minus_simp:
kleing@24333
    89
  "0 < n ==> bin_to_bl_aux n (w BIT b) bl = 
kleing@24333
    90
    bin_to_bl_aux (n - 1) w ((b = bit.B1) # bl)"
kleing@24333
    91
  by (cases n) auto
kleing@24333
    92
kleing@24333
    93
declare bin_to_bl_aux_Pls_minus_simp [simp]
kleing@24333
    94
  bin_to_bl_aux_Min_minus_simp [simp]
kleing@24333
    95
  bin_to_bl_aux_Bit_minus_simp [simp]
kleing@24333
    96
huffman@24465
    97
(** link between bin and bool list **)
huffman@24465
    98
huffman@24465
    99
lemma bl_to_bin_aux_append [rule_format] : 
huffman@24465
   100
  "ALL w. bl_to_bin_aux w (bs @ cs) = bl_to_bin_aux (bl_to_bin_aux w bs) cs"
huffman@24465
   101
  by (induct bs) auto
huffman@24465
   102
kleing@24333
   103
lemma bin_to_bl_aux_append [rule_format] : 
kleing@24333
   104
  "ALL w bs. bin_to_bl_aux n w bs @ cs = bin_to_bl_aux n w (bs @ cs)"
kleing@24333
   105
  by (induct n) auto
kleing@24333
   106
huffman@24465
   107
lemma bl_to_bin_append: 
huffman@24465
   108
  "bl_to_bin (bs @ cs) = bl_to_bin_aux (bl_to_bin bs) cs"
huffman@24465
   109
  unfolding bl_to_bin_def by (rule bl_to_bin_aux_append)
huffman@24465
   110
kleing@24333
   111
lemma bin_to_bl_aux_alt: 
kleing@24333
   112
  "bin_to_bl_aux n w bs = bin_to_bl n w @ bs" 
kleing@24333
   113
  unfolding bin_to_bl_def by (simp add : bin_to_bl_aux_append)
kleing@24333
   114
huffman@24465
   115
lemma bin_to_bl_0: "bin_to_bl 0 bs = []"
kleing@24333
   116
  unfolding bin_to_bl_def by auto
kleing@24333
   117
kleing@24333
   118
lemma size_bin_to_bl_aux [rule_format] : 
kleing@24333
   119
  "ALL w bs. size (bin_to_bl_aux n w bs) = n + length bs"
kleing@24333
   120
  by (induct n) auto
kleing@24333
   121
huffman@24465
   122
lemma size_bin_to_bl: "size (bin_to_bl n w) = n" 
kleing@24333
   123
  unfolding bin_to_bl_def by (simp add : size_bin_to_bl_aux)
kleing@24333
   124
huffman@24465
   125
lemma bin_bl_bin' [rule_format] : 
huffman@24465
   126
  "ALL w bs. bl_to_bin (bin_to_bl_aux n w bs) = 
huffman@24465
   127
    bl_to_bin_aux (bintrunc n w) bs"
huffman@24465
   128
  by (induct n) (auto simp add : bl_to_bin_def)
huffman@24465
   129
huffman@24465
   130
lemma bin_bl_bin: "bl_to_bin (bin_to_bl n w) = bintrunc n w"
huffman@24465
   131
  unfolding bin_to_bl_def bin_bl_bin' by auto
huffman@24465
   132
huffman@24465
   133
lemma bl_bin_bl' [rule_format] :
huffman@24465
   134
  "ALL w n. bin_to_bl (n + length bs) (bl_to_bin_aux w bs) = 
huffman@24465
   135
    bin_to_bl_aux n w bs"
huffman@24465
   136
  apply (induct "bs")
huffman@24465
   137
   apply auto
huffman@24465
   138
    apply (simp_all only : add_Suc [symmetric])
huffman@24465
   139
    apply (auto simp add : bin_to_bl_def)
huffman@24465
   140
  done
huffman@24465
   141
huffman@24465
   142
lemma bl_bin_bl: "bin_to_bl (length bs) (bl_to_bin bs) = bs"
huffman@24465
   143
  unfolding bl_to_bin_def
huffman@24465
   144
  apply (rule box_equals)
huffman@24465
   145
    apply (rule bl_bin_bl')
huffman@24465
   146
   prefer 2
huffman@24465
   147
   apply (rule bin_to_bl_aux.Z)
huffman@24465
   148
  apply simp
huffman@24465
   149
  done
huffman@24465
   150
  
huffman@24465
   151
declare 
huffman@24465
   152
  bin_to_bl_0 [simp] 
huffman@24465
   153
  size_bin_to_bl [simp] 
huffman@24465
   154
  bin_bl_bin [simp] 
huffman@24465
   155
  bl_bin_bl [simp]
huffman@24465
   156
huffman@24465
   157
lemma bl_to_bin_inj:
huffman@24465
   158
  "bl_to_bin bs = bl_to_bin cs ==> length bs = length cs ==> bs = cs"
huffman@24465
   159
  apply (rule_tac box_equals)
huffman@24465
   160
    defer
huffman@24465
   161
    apply (rule bl_bin_bl)
huffman@24465
   162
   apply (rule bl_bin_bl)
huffman@24465
   163
  apply simp
huffman@24465
   164
  done
huffman@24465
   165
huffman@24465
   166
lemma bl_to_bin_False: "bl_to_bin (False # bl) = bl_to_bin bl"
huffman@24465
   167
  unfolding bl_to_bin_def by auto
huffman@24465
   168
  
huffman@24465
   169
lemma bl_to_bin_Nil: "bl_to_bin [] = Numeral.Pls"
huffman@24465
   170
  unfolding bl_to_bin_def by auto
huffman@24465
   171
kleing@24333
   172
lemma bin_to_bl_Pls_aux [rule_format] : 
kleing@24333
   173
  "ALL bl. bin_to_bl_aux n Numeral.Pls bl = replicate n False @ bl"
kleing@24333
   174
  by (induct n) (auto simp: replicate_app_Cons_same)
kleing@24333
   175
kleing@24333
   176
lemma bin_to_bl_Pls: "bin_to_bl n Numeral.Pls = replicate n False"
kleing@24333
   177
  unfolding bin_to_bl_def by (simp add : bin_to_bl_Pls_aux)
kleing@24333
   178
kleing@24333
   179
lemma bin_to_bl_Min_aux [rule_format] : 
kleing@24333
   180
  "ALL bl. bin_to_bl_aux n Numeral.Min bl = replicate n True @ bl"
kleing@24333
   181
  by (induct n) (auto simp: replicate_app_Cons_same)
kleing@24333
   182
kleing@24333
   183
lemma bin_to_bl_Min: "bin_to_bl n Numeral.Min = replicate n True"
kleing@24333
   184
  unfolding bin_to_bl_def by (simp add : bin_to_bl_Min_aux)
kleing@24333
   185
huffman@24465
   186
lemma bl_to_bin_rep_F: 
huffman@24465
   187
  "bl_to_bin (replicate n False @ bl) = bl_to_bin bl"
huffman@24465
   188
  apply (simp add: bin_to_bl_Pls_aux [symmetric] bin_bl_bin')
huffman@24465
   189
  apply (simp add: bl_to_bin_def)
huffman@24465
   190
  done
huffman@24465
   191
huffman@24465
   192
lemma bin_to_bl_trunc:
huffman@24465
   193
  "n <= m ==> bin_to_bl n (bintrunc m w) = bin_to_bl n w"
huffman@24465
   194
  by (auto intro: bl_to_bin_inj)
huffman@24465
   195
huffman@24465
   196
declare 
huffman@24465
   197
  bin_to_bl_trunc [simp] 
huffman@24465
   198
  bl_to_bin_False [simp] 
huffman@24465
   199
  bl_to_bin_Nil [simp]
huffman@24465
   200
kleing@24333
   201
lemma bin_to_bl_aux_bintr [rule_format] :
kleing@24333
   202
  "ALL m bin bl. bin_to_bl_aux n (bintrunc m bin) bl = 
kleing@24333
   203
    replicate (n - m) False @ bin_to_bl_aux (min n m) bin bl"
kleing@24333
   204
  apply (induct_tac "n")
kleing@24333
   205
   apply clarsimp
kleing@24333
   206
  apply clarsimp
kleing@24333
   207
  apply (case_tac "m")
kleing@24333
   208
   apply (clarsimp simp: bin_to_bl_Pls_aux) 
kleing@24333
   209
   apply (erule thin_rl)
kleing@24333
   210
   apply (induct_tac n)   
kleing@24333
   211
    apply auto
kleing@24333
   212
  done
kleing@24333
   213
kleing@24333
   214
lemmas bin_to_bl_bintr = 
kleing@24333
   215
  bin_to_bl_aux_bintr [where bl = "[]", folded bin_to_bl_def]
kleing@24333
   216
huffman@24465
   217
lemma bl_to_bin_rep_False: "bl_to_bin (replicate n False) = Numeral.Pls"
huffman@24465
   218
  by (induct n) auto
huffman@24465
   219
kleing@24333
   220
lemma len_bin_to_bl_aux [rule_format] : 
kleing@24333
   221
  "ALL w bs. length (bin_to_bl_aux n w bs) = n + length bs"
kleing@24333
   222
  by (induct "n") auto
kleing@24333
   223
kleing@24333
   224
lemma len_bin_to_bl [simp]: "length (bin_to_bl n w) = n"
kleing@24333
   225
  unfolding bin_to_bl_def len_bin_to_bl_aux by auto
kleing@24333
   226
  
kleing@24333
   227
lemma sign_bl_bin' [rule_format] : 
kleing@24333
   228
  "ALL w. bin_sign (bl_to_bin_aux w bs) = bin_sign w"
kleing@24333
   229
  by (induct bs) auto
kleing@24333
   230
  
kleing@24333
   231
lemma sign_bl_bin: "bin_sign (bl_to_bin bs) = Numeral.Pls"
kleing@24333
   232
  unfolding bl_to_bin_def by (simp add : sign_bl_bin')
kleing@24333
   233
  
kleing@24333
   234
lemma bl_sbin_sign_aux [rule_format] : 
kleing@24333
   235
  "ALL w bs. hd (bin_to_bl_aux (Suc n) w bs) = 
kleing@24333
   236
    (bin_sign (sbintrunc n w) = Numeral.Min)"
kleing@24333
   237
  apply (induct "n")
kleing@24333
   238
   apply clarsimp
kleing@24333
   239
   apply (case_tac w rule: bin_exhaust)
kleing@24333
   240
   apply (simp split add : bit.split)
kleing@24333
   241
  apply clarsimp
kleing@24333
   242
  done
kleing@24333
   243
    
kleing@24333
   244
lemma bl_sbin_sign: 
kleing@24333
   245
  "hd (bin_to_bl (Suc n) w) = (bin_sign (sbintrunc n w) = Numeral.Min)"
kleing@24333
   246
  unfolding bin_to_bl_def by (rule bl_sbin_sign_aux)
kleing@24333
   247
kleing@24333
   248
lemma bin_nth_of_bl_aux [rule_format] : 
kleing@24333
   249
  "ALL w. bin_nth (bl_to_bin_aux w bl) n = 
kleing@24333
   250
    (n < size bl & rev bl ! n | n >= length bl & bin_nth w (n - size bl))"
kleing@24333
   251
  apply (induct_tac bl)
kleing@24333
   252
   apply clarsimp
kleing@24333
   253
  apply clarsimp
kleing@24333
   254
  apply (cut_tac x=n and y="size list" in linorder_less_linear)
kleing@24333
   255
  apply (erule disjE, simp add: nth_append)+
kleing@24333
   256
  apply (simp add: nth_append)
kleing@24333
   257
  done
kleing@24333
   258
kleing@24333
   259
lemma bin_nth_of_bl: "bin_nth (bl_to_bin bl) n = (n < length bl & rev bl ! n)";
kleing@24333
   260
  unfolding bl_to_bin_def by (simp add : bin_nth_of_bl_aux)
kleing@24333
   261
kleing@24333
   262
lemma bin_nth_bl [rule_format] : "ALL m w. n < m --> 
kleing@24333
   263
    bin_nth w n = nth (rev (bin_to_bl m w)) n"
kleing@24333
   264
  apply (induct n)
kleing@24333
   265
   apply clarsimp
kleing@24333
   266
   apply (case_tac m, clarsimp)
kleing@24333
   267
   apply (clarsimp simp: bin_to_bl_def)
kleing@24333
   268
   apply (simp add: bin_to_bl_aux_alt)
kleing@24333
   269
  apply clarsimp
kleing@24333
   270
  apply (case_tac m, clarsimp)
kleing@24333
   271
  apply (clarsimp simp: bin_to_bl_def)
kleing@24333
   272
  apply (simp add: bin_to_bl_aux_alt)
kleing@24333
   273
  done
kleing@24333
   274
huffman@24465
   275
lemma nth_rev [rule_format] : 
huffman@24465
   276
  "n < length xs --> rev xs ! n = xs ! (length xs - 1 - n)"
huffman@24465
   277
  apply (induct_tac "xs")
huffman@24465
   278
   apply simp
huffman@24465
   279
  apply (clarsimp simp add : nth_append nth.simps split add : nat.split)
huffman@24465
   280
  apply (rule_tac f = "%n. list ! n" in arg_cong) 
huffman@24465
   281
  apply arith
huffman@24465
   282
  done
huffman@24465
   283
huffman@24465
   284
lemmas nth_rev_alt = nth_rev [where xs = "rev ?ys", simplified]
huffman@24465
   285
kleing@24333
   286
lemma nth_bin_to_bl_aux [rule_format] : 
kleing@24333
   287
  "ALL w n bl. n < m + length bl --> (bin_to_bl_aux m w bl) ! n = 
kleing@24333
   288
    (if n < m then bin_nth w (m - 1 - n) else bl ! (n - m))"
kleing@24333
   289
  apply (induct_tac "m")
kleing@24333
   290
   apply clarsimp
kleing@24333
   291
  apply clarsimp
kleing@24333
   292
  apply (case_tac w rule: bin_exhaust)
kleing@24333
   293
  apply clarsimp
kleing@24333
   294
  apply (case_tac "na - n")
kleing@24333
   295
   apply arith
kleing@24333
   296
  apply simp
kleing@24333
   297
  apply (rule_tac f = "%n. bl ! n" in arg_cong) 
kleing@24333
   298
  apply arith
kleing@24333
   299
  done
kleing@24333
   300
  
kleing@24333
   301
lemma nth_bin_to_bl: "n < m ==> (bin_to_bl m w) ! n = bin_nth w (m - Suc n)"
kleing@24333
   302
  unfolding bin_to_bl_def by (simp add : nth_bin_to_bl_aux)
kleing@24333
   303
kleing@24333
   304
lemma bl_to_bin_lt2p_aux [rule_format] : 
kleing@24333
   305
  "ALL w. bl_to_bin_aux w bs < (w + 1) * (2 ^ length bs)"
kleing@24333
   306
  apply (induct "bs")
kleing@24333
   307
   apply clarsimp
kleing@24333
   308
  apply clarsimp
kleing@24333
   309
  apply safe
kleing@24333
   310
   apply (erule allE, erule xtr8 [rotated],
kleing@24333
   311
          simp add: Bit_def ring_simps cong add : number_of_False_cong)+
kleing@24333
   312
  done
kleing@24333
   313
kleing@24333
   314
lemma bl_to_bin_lt2p: "bl_to_bin bs < (2 ^ length bs)"
kleing@24333
   315
  apply (unfold bl_to_bin_def)
kleing@24333
   316
  apply (rule xtr1)
kleing@24333
   317
   prefer 2
kleing@24333
   318
   apply (rule bl_to_bin_lt2p_aux)
kleing@24333
   319
  apply simp
kleing@24333
   320
  done
kleing@24333
   321
kleing@24333
   322
lemma bl_to_bin_ge2p_aux [rule_format] : 
kleing@24333
   323
  "ALL w. bl_to_bin_aux w bs >= w * (2 ^ length bs)"
kleing@24333
   324
  apply (induct bs)
kleing@24333
   325
   apply clarsimp
kleing@24333
   326
  apply clarsimp
kleing@24333
   327
  apply safe
kleing@24333
   328
   apply (erule allE, erule less_eq_less.order_trans [rotated],
kleing@24333
   329
          simp add: Bit_def ring_simps cong add : number_of_False_cong)+
kleing@24333
   330
  done
kleing@24333
   331
kleing@24333
   332
lemma bl_to_bin_ge0: "bl_to_bin bs >= 0"
kleing@24333
   333
  apply (unfold bl_to_bin_def)
kleing@24333
   334
  apply (rule xtr4)
kleing@24333
   335
   apply (rule bl_to_bin_ge2p_aux)
kleing@24333
   336
  apply simp
kleing@24333
   337
  done
kleing@24333
   338
kleing@24333
   339
lemma butlast_rest_bin: 
kleing@24333
   340
  "butlast (bin_to_bl n w) = bin_to_bl (n - 1) (bin_rest w)"
kleing@24333
   341
  apply (unfold bin_to_bl_def)
kleing@24333
   342
  apply (cases w rule: bin_exhaust)
kleing@24333
   343
  apply (cases n, clarsimp)
kleing@24333
   344
  apply clarsimp
kleing@24333
   345
  apply (auto simp add: bin_to_bl_aux_alt)
kleing@24333
   346
  done
kleing@24333
   347
kleing@24333
   348
lemmas butlast_bin_rest = butlast_rest_bin
kleing@24333
   349
  [where w="bl_to_bin ?bl" and n="length ?bl", simplified]
kleing@24333
   350
kleing@24333
   351
lemma butlast_rest_bl2bin_aux [rule_format] :
kleing@24333
   352
  "ALL w. bl ~= [] --> 
kleing@24333
   353
    bl_to_bin_aux w (butlast bl) = bin_rest (bl_to_bin_aux w bl)"
kleing@24333
   354
  by (induct bl) auto
kleing@24333
   355
  
kleing@24333
   356
lemma butlast_rest_bl2bin: 
kleing@24333
   357
  "bl_to_bin (butlast bl) = bin_rest (bl_to_bin bl)"
kleing@24333
   358
  apply (unfold bl_to_bin_def)
kleing@24333
   359
  apply (cases bl)
kleing@24333
   360
   apply (auto simp add: butlast_rest_bl2bin_aux)
kleing@24333
   361
  done
kleing@24333
   362
kleing@24333
   363
lemma trunc_bl2bin_aux [rule_format] : 
kleing@24333
   364
  "ALL w. bintrunc m (bl_to_bin_aux w bl) = 
kleing@24333
   365
    bl_to_bin_aux (bintrunc (m - length bl) w) (drop (length bl - m) bl)"
kleing@24333
   366
  apply (induct_tac bl)
kleing@24333
   367
   apply clarsimp
kleing@24333
   368
  apply clarsimp
kleing@24333
   369
  apply safe
kleing@24333
   370
   apply (case_tac "m - size list")
kleing@24333
   371
    apply (simp add : diff_is_0_eq [THEN iffD1, THEN Suc_diff_le])
kleing@24333
   372
   apply simp
kleing@24333
   373
   apply (rule_tac f = "%nat. bl_to_bin_aux (bintrunc nat w BIT bit.B1) list" 
kleing@24333
   374
                   in arg_cong) 
kleing@24333
   375
   apply simp
kleing@24333
   376
  apply (case_tac "m - size list")
kleing@24333
   377
   apply (simp add: diff_is_0_eq [THEN iffD1, THEN Suc_diff_le])
kleing@24333
   378
  apply simp
kleing@24333
   379
  apply (rule_tac f = "%nat. bl_to_bin_aux (bintrunc nat w BIT bit.B0) list" 
kleing@24333
   380
                  in arg_cong) 
kleing@24333
   381
  apply simp
kleing@24333
   382
  done
kleing@24333
   383
kleing@24333
   384
lemma trunc_bl2bin: 
kleing@24333
   385
  "bintrunc m (bl_to_bin bl) = bl_to_bin (drop (length bl - m) bl)"
kleing@24333
   386
  unfolding bl_to_bin_def by (simp add : trunc_bl2bin_aux)
kleing@24333
   387
  
kleing@24333
   388
lemmas trunc_bl2bin_len [simp] =
kleing@24333
   389
  trunc_bl2bin [of "length bl" bl, simplified, standard]  
kleing@24333
   390
kleing@24333
   391
lemma bl2bin_drop: 
kleing@24333
   392
  "bl_to_bin (drop k bl) = bintrunc (length bl - k) (bl_to_bin bl)"
kleing@24333
   393
  apply (rule trans)
kleing@24333
   394
   prefer 2
kleing@24333
   395
   apply (rule trunc_bl2bin [symmetric])
kleing@24333
   396
  apply (cases "k <= length bl")
kleing@24333
   397
   apply auto
kleing@24333
   398
  done
kleing@24333
   399
kleing@24333
   400
lemma nth_rest_power_bin [rule_format] :
kleing@24333
   401
  "ALL n. bin_nth ((bin_rest ^ k) w) n = bin_nth w (n + k)"
kleing@24333
   402
  apply (induct k, clarsimp)
kleing@24333
   403
  apply clarsimp
kleing@24333
   404
  apply (simp only: bin_nth.Suc [symmetric] add_Suc)
kleing@24333
   405
  done
kleing@24333
   406
kleing@24333
   407
lemma take_rest_power_bin:
kleing@24333
   408
  "m <= n ==> take m (bin_to_bl n w) = bin_to_bl m ((bin_rest ^ (n - m)) w)" 
kleing@24333
   409
  apply (rule nth_equalityI)
kleing@24333
   410
   apply simp
kleing@24333
   411
  apply (clarsimp simp add: nth_bin_to_bl nth_rest_power_bin)
kleing@24333
   412
  done
kleing@24333
   413
huffman@24465
   414
lemma hd_butlast: "size xs > 1 ==> hd (butlast xs) = hd xs"
huffman@24465
   415
  by (cases xs) auto
kleing@24333
   416
kleing@24333
   417
lemma last_bin_last' [rule_format] : 
kleing@24333
   418
  "ALL w. size xs > 0 --> last xs = (bin_last (bl_to_bin_aux w xs) = bit.B1)" 
kleing@24333
   419
  by (induct xs) auto
kleing@24333
   420
kleing@24333
   421
lemma last_bin_last: 
kleing@24333
   422
  "size xs > 0 ==> last xs = (bin_last (bl_to_bin xs) = bit.B1)" 
kleing@24333
   423
  unfolding bl_to_bin_def by (erule last_bin_last')
kleing@24333
   424
  
kleing@24333
   425
lemma bin_last_last: 
kleing@24333
   426
  "bin_last w = (if last (bin_to_bl (Suc n) w) then bit.B1 else bit.B0)" 
kleing@24333
   427
  apply (unfold bin_to_bl_def)
kleing@24333
   428
  apply simp
kleing@24333
   429
  apply (auto simp add: bin_to_bl_aux_alt)
kleing@24333
   430
  done
kleing@24333
   431
huffman@24465
   432
(** links between bit-wise operations and operations on bool lists **)
huffman@24465
   433
    
kleing@24333
   434
lemma app2_Nil [simp]: "app2 f [] ys = []"
kleing@24333
   435
  unfolding app2_def by auto
kleing@24333
   436
kleing@24333
   437
lemma app2_Cons [simp]:
kleing@24333
   438
  "app2 f (x # xs) (y # ys) = f x y # app2 f xs ys"
kleing@24333
   439
  unfolding app2_def by auto
kleing@24333
   440
kleing@24333
   441
lemma bl_xor_aux_bin [rule_format] : "ALL v w bs cs. 
kleing@24333
   442
    app2 (%x y. x ~= y) (bin_to_bl_aux n v bs) (bin_to_bl_aux n w cs) = 
huffman@24353
   443
    bin_to_bl_aux n (v XOR w) (app2 (%x y. x ~= y) bs cs)"
kleing@24333
   444
  apply (induct_tac n)
kleing@24333
   445
   apply safe
kleing@24333
   446
   apply simp
kleing@24333
   447
  apply (case_tac v rule: bin_exhaust)
kleing@24333
   448
  apply (case_tac w rule: bin_exhaust)
kleing@24333
   449
  apply clarsimp
kleing@24333
   450
  apply (case_tac b)
kleing@24333
   451
  apply (case_tac ba, safe, simp_all)+
kleing@24333
   452
  done
kleing@24333
   453
    
kleing@24333
   454
lemma bl_or_aux_bin [rule_format] : "ALL v w bs cs. 
kleing@24333
   455
    app2 (op | ) (bin_to_bl_aux n v bs) (bin_to_bl_aux n w cs) = 
huffman@24353
   456
    bin_to_bl_aux n (v OR w) (app2 (op | ) bs cs)" 
kleing@24333
   457
  apply (induct_tac n)
kleing@24333
   458
   apply safe
kleing@24333
   459
   apply simp
kleing@24333
   460
  apply (case_tac v rule: bin_exhaust)
kleing@24333
   461
  apply (case_tac w rule: bin_exhaust)
kleing@24333
   462
  apply clarsimp
kleing@24333
   463
  apply (case_tac b)
kleing@24333
   464
  apply (case_tac ba, safe, simp_all)+
kleing@24333
   465
  done
kleing@24333
   466
    
kleing@24333
   467
lemma bl_and_aux_bin [rule_format] : "ALL v w bs cs. 
kleing@24333
   468
    app2 (op & ) (bin_to_bl_aux n v bs) (bin_to_bl_aux n w cs) = 
huffman@24353
   469
    bin_to_bl_aux n (v AND w) (app2 (op & ) bs cs)" 
kleing@24333
   470
  apply (induct_tac n)
kleing@24333
   471
   apply safe
kleing@24333
   472
   apply simp
kleing@24333
   473
  apply (case_tac v rule: bin_exhaust)
kleing@24333
   474
  apply (case_tac w rule: bin_exhaust)
kleing@24333
   475
  apply clarsimp
kleing@24333
   476
  apply (case_tac b)
kleing@24333
   477
  apply (case_tac ba, safe, simp_all)+
kleing@24333
   478
  done
kleing@24333
   479
    
kleing@24333
   480
lemma bl_not_aux_bin [rule_format] : 
kleing@24333
   481
  "ALL w cs. map Not (bin_to_bl_aux n w cs) = 
huffman@24353
   482
    bin_to_bl_aux n (NOT w) (map Not cs)"
kleing@24333
   483
  apply (induct n)
kleing@24333
   484
   apply clarsimp
kleing@24333
   485
  apply clarsimp
kleing@24333
   486
  apply (case_tac w rule: bin_exhaust)
kleing@24333
   487
  apply (case_tac b)
kleing@24333
   488
   apply auto
kleing@24333
   489
  done
kleing@24333
   490
kleing@24333
   491
lemmas bl_not_bin = bl_not_aux_bin
kleing@24333
   492
  [where cs = "[]", unfolded bin_to_bl_def [symmetric] map.simps]
kleing@24333
   493
kleing@24333
   494
lemmas bl_and_bin = bl_and_aux_bin [where bs="[]" and cs="[]", 
kleing@24333
   495
                                    unfolded app2_Nil, folded bin_to_bl_def]
kleing@24333
   496
kleing@24333
   497
lemmas bl_or_bin = bl_or_aux_bin [where bs="[]" and cs="[]", 
kleing@24333
   498
                                  unfolded app2_Nil, folded bin_to_bl_def]
kleing@24333
   499
kleing@24333
   500
lemmas bl_xor_bin = bl_xor_aux_bin [where bs="[]" and cs="[]", 
kleing@24333
   501
                                    unfolded app2_Nil, folded bin_to_bl_def]
kleing@24333
   502
kleing@24333
   503
lemma drop_bin2bl_aux [rule_format] : 
kleing@24333
   504
  "ALL m bin bs. drop m (bin_to_bl_aux n bin bs) = 
kleing@24333
   505
    bin_to_bl_aux (n - m) bin (drop (m - n) bs)"
kleing@24333
   506
  apply (induct n, clarsimp)
kleing@24333
   507
  apply clarsimp
kleing@24333
   508
  apply (case_tac bin rule: bin_exhaust)
kleing@24333
   509
  apply (case_tac "m <= n", simp)
kleing@24333
   510
  apply (case_tac "m - n", simp)
kleing@24333
   511
  apply simp
kleing@24333
   512
  apply (rule_tac f = "%nat. drop nat bs" in arg_cong) 
kleing@24333
   513
  apply simp
kleing@24333
   514
  done
kleing@24333
   515
kleing@24333
   516
lemma drop_bin2bl: "drop m (bin_to_bl n bin) = bin_to_bl (n - m) bin"
kleing@24333
   517
  unfolding bin_to_bl_def by (simp add : drop_bin2bl_aux)
kleing@24333
   518
kleing@24333
   519
lemma take_bin2bl_lem1 [rule_format] : 
kleing@24333
   520
  "ALL w bs. take m (bin_to_bl_aux m w bs) = bin_to_bl m w"
kleing@24333
   521
  apply (induct m, clarsimp)
kleing@24333
   522
  apply clarsimp
kleing@24333
   523
  apply (simp add: bin_to_bl_aux_alt)
kleing@24333
   524
  apply (simp add: bin_to_bl_def)
kleing@24333
   525
  apply (simp add: bin_to_bl_aux_alt)
kleing@24333
   526
  done
kleing@24333
   527
kleing@24333
   528
lemma take_bin2bl_lem [rule_format] : 
kleing@24333
   529
  "ALL w bs. take m (bin_to_bl_aux (m + n) w bs) = 
kleing@24333
   530
    take m (bin_to_bl (m + n) w)"
kleing@24333
   531
  apply (induct n)
kleing@24333
   532
   apply clarify
kleing@24333
   533
   apply (simp_all (no_asm) add: bin_to_bl_def take_bin2bl_lem1)
kleing@24333
   534
  apply simp
kleing@24333
   535
  done
kleing@24333
   536
kleing@24333
   537
lemma bin_split_take [rule_format] : 
kleing@24333
   538
  "ALL b c. bin_split n c = (a, b) --> 
kleing@24333
   539
    bin_to_bl m a = take m (bin_to_bl (m + n) c)"
kleing@24333
   540
  apply (induct n)
kleing@24333
   541
   apply clarsimp
kleing@24333
   542
  apply (clarsimp simp: Let_def split: ls_splits)
kleing@24333
   543
  apply (simp add: bin_to_bl_def)
kleing@24333
   544
  apply (simp add: take_bin2bl_lem)
kleing@24333
   545
  done
kleing@24333
   546
kleing@24333
   547
lemma bin_split_take1: 
kleing@24333
   548
  "k = m + n ==> bin_split n c = (a, b) ==> 
kleing@24333
   549
    bin_to_bl m a = take m (bin_to_bl k c)"
kleing@24333
   550
  by (auto elim: bin_split_take)
kleing@24333
   551
  
kleing@24333
   552
lemma nth_takefill [rule_format] : "ALL m l. m < n --> 
kleing@24333
   553
    takefill fill n l ! m = (if m < length l then l ! m else fill)"
kleing@24333
   554
  apply (induct n, clarsimp)
kleing@24333
   555
  apply clarsimp
kleing@24333
   556
  apply (case_tac m)
kleing@24333
   557
   apply (simp split: list.split)
kleing@24333
   558
  apply clarsimp
kleing@24333
   559
  apply (erule allE)+
kleing@24333
   560
  apply (erule (1) impE)
kleing@24333
   561
  apply (simp split: list.split)
kleing@24333
   562
  done
kleing@24333
   563
kleing@24333
   564
lemma takefill_alt [rule_format] :
kleing@24333
   565
  "ALL l. takefill fill n l = take n l @ replicate (n - length l) fill"
kleing@24333
   566
  by (induct n) (auto split: list.split)
kleing@24333
   567
kleing@24333
   568
lemma takefill_replicate [simp]:
kleing@24333
   569
  "takefill fill n (replicate m fill) = replicate n fill"
kleing@24333
   570
  by (simp add : takefill_alt replicate_add [symmetric])
kleing@24333
   571
kleing@24333
   572
lemma takefill_le' [rule_format] :
kleing@24333
   573
  "ALL l n. n = m + k --> takefill x m (takefill x n l) = takefill x m l"
kleing@24333
   574
  by (induct m) (auto split: list.split)
kleing@24333
   575
kleing@24333
   576
lemma length_takefill [simp]: "length (takefill fill n l) = n"
kleing@24333
   577
  by (simp add : takefill_alt)
kleing@24333
   578
kleing@24333
   579
lemma take_takefill':
kleing@24333
   580
  "!!w n.  n = k + m ==> take k (takefill fill n w) = takefill fill k w"
kleing@24333
   581
  by (induct k) (auto split add : list.split) 
kleing@24333
   582
kleing@24333
   583
lemma drop_takefill:
kleing@24333
   584
  "!!w. drop k (takefill fill (m + k) w) = takefill fill m (drop k w)"
kleing@24333
   585
  by (induct k) (auto split add : list.split) 
kleing@24333
   586
kleing@24333
   587
lemma takefill_le [simp]:
kleing@24333
   588
  "m \<le> n \<Longrightarrow> takefill x m (takefill x n l) = takefill x m l"
kleing@24333
   589
  by (auto simp: le_iff_add takefill_le')
kleing@24333
   590
kleing@24333
   591
lemma take_takefill [simp]:
kleing@24333
   592
  "m \<le> n \<Longrightarrow> take m (takefill fill n w) = takefill fill m w"
kleing@24333
   593
  by (auto simp: le_iff_add take_takefill')
kleing@24333
   594
 
kleing@24333
   595
lemma takefill_append:
kleing@24333
   596
  "takefill fill (m + length xs) (xs @ w) = xs @ (takefill fill m w)"
kleing@24333
   597
  by (induct xs) auto
kleing@24333
   598
kleing@24333
   599
lemma takefill_same': 
kleing@24333
   600
  "l = length xs ==> takefill fill l xs = xs"
kleing@24333
   601
  by clarify (induct xs, auto)
kleing@24333
   602
 
kleing@24333
   603
lemmas takefill_same [simp] = takefill_same' [OF refl]
kleing@24333
   604
kleing@24333
   605
lemma takefill_bintrunc:
kleing@24333
   606
  "takefill False n bl = rev (bin_to_bl n (bl_to_bin (rev bl)))"
kleing@24333
   607
  apply (rule nth_equalityI)
kleing@24333
   608
   apply simp
kleing@24333
   609
  apply (clarsimp simp: nth_takefill nth_rev nth_bin_to_bl bin_nth_of_bl)
kleing@24333
   610
  done
kleing@24333
   611
kleing@24333
   612
lemma bl_bin_bl_rtf:
kleing@24333
   613
  "bin_to_bl n (bl_to_bin bl) = rev (takefill False n (rev bl))"
kleing@24333
   614
  by (simp add : takefill_bintrunc)
kleing@24333
   615
  
kleing@24333
   616
lemmas bl_bin_bl_rep_drop = 
kleing@24333
   617
  bl_bin_bl_rtf [simplified takefill_alt,
kleing@24333
   618
                 simplified, simplified rev_take, simplified]
kleing@24333
   619
kleing@24333
   620
lemma tf_rev:
kleing@24333
   621
  "n + k = m + length bl ==> takefill x m (rev (takefill y n bl)) = 
kleing@24333
   622
    rev (takefill y m (rev (takefill x k (rev bl))))"
kleing@24333
   623
  apply (rule nth_equalityI)
kleing@24333
   624
   apply (auto simp add: nth_takefill nth_rev)
kleing@24333
   625
  apply (rule_tac f = "%n. bl ! n" in arg_cong) 
kleing@24333
   626
  apply arith 
kleing@24333
   627
  done
kleing@24333
   628
kleing@24333
   629
lemma takefill_minus:
kleing@24333
   630
  "0 < n ==> takefill fill (Suc (n - 1)) w = takefill fill n w"
kleing@24333
   631
  by auto
kleing@24333
   632
kleing@24333
   633
lemmas takefill_Suc_cases = 
kleing@24333
   634
  list.cases [THEN takefill.Suc [THEN trans], standard]
kleing@24333
   635
kleing@24333
   636
lemmas takefill_Suc_Nil = takefill_Suc_cases (1)
kleing@24333
   637
lemmas takefill_Suc_Cons = takefill_Suc_cases (2)
kleing@24333
   638
kleing@24333
   639
lemmas takefill_minus_simps = takefill_Suc_cases [THEN [2] 
kleing@24333
   640
  takefill_minus [symmetric, THEN trans], standard]
kleing@24333
   641
kleing@24333
   642
lemmas takefill_pred_simps [simp] =
kleing@24333
   643
  takefill_minus_simps [where n="number_of bin", simplified nobm1, standard]
kleing@24333
   644
kleing@24333
   645
(* links with function bl_to_bin *)
kleing@24333
   646
kleing@24333
   647
lemma bl_to_bin_aux_cat: 
kleing@24333
   648
  "!!nv v. bl_to_bin_aux (bin_cat w nv v) bs = 
kleing@24333
   649
    bin_cat w (nv + length bs) (bl_to_bin_aux v bs)"
kleing@24333
   650
  apply (induct bs)
kleing@24333
   651
   apply simp
kleing@24333
   652
  apply (simp add: bin_cat_Suc_Bit [symmetric] del: bin_cat.simps)
kleing@24333
   653
  done
kleing@24333
   654
kleing@24333
   655
lemma bin_to_bl_aux_cat: 
kleing@24333
   656
  "!!w bs. bin_to_bl_aux (nv + nw) (bin_cat v nw w) bs = 
kleing@24333
   657
    bin_to_bl_aux nv v (bin_to_bl_aux nw w bs)"
kleing@24333
   658
  by (induct nw) auto 
kleing@24333
   659
kleing@24333
   660
lemmas bl_to_bin_aux_alt = 
kleing@24333
   661
  bl_to_bin_aux_cat [where nv = "0" and v = "Numeral.Pls", 
kleing@24333
   662
    simplified bl_to_bin_def [symmetric], simplified]
kleing@24333
   663
kleing@24333
   664
lemmas bin_to_bl_cat =
kleing@24333
   665
  bin_to_bl_aux_cat [where bs = "[]", folded bin_to_bl_def]
kleing@24333
   666
kleing@24333
   667
lemmas bl_to_bin_aux_app_cat = 
kleing@24333
   668
  trans [OF bl_to_bin_aux_append bl_to_bin_aux_alt]
kleing@24333
   669
kleing@24333
   670
lemmas bin_to_bl_aux_cat_app =
kleing@24333
   671
  trans [OF bin_to_bl_aux_cat bin_to_bl_aux_alt]
kleing@24333
   672
kleing@24333
   673
lemmas bl_to_bin_app_cat = bl_to_bin_aux_app_cat
kleing@24333
   674
  [where w = "Numeral.Pls", folded bl_to_bin_def]
kleing@24333
   675
kleing@24333
   676
lemmas bin_to_bl_cat_app = bin_to_bl_aux_cat_app
kleing@24333
   677
  [where bs = "[]", folded bin_to_bl_def]
kleing@24333
   678
kleing@24333
   679
(* bl_to_bin_app_cat_alt and bl_to_bin_app_cat are easily interderivable *)
kleing@24333
   680
lemma bl_to_bin_app_cat_alt: 
kleing@24333
   681
  "bin_cat (bl_to_bin cs) n w = bl_to_bin (cs @ bin_to_bl n w)"
kleing@24333
   682
  by (simp add : bl_to_bin_app_cat)
kleing@24333
   683
kleing@24333
   684
lemma mask_lem: "(bl_to_bin (True # replicate n False)) = 
kleing@24333
   685
    Numeral.succ (bl_to_bin (replicate n True))"
kleing@24333
   686
  apply (unfold bl_to_bin_def)
kleing@24333
   687
  apply (induct n)
kleing@24333
   688
   apply simp
kleing@24333
   689
  apply (simp only: Suc_eq_add_numeral_1 replicate_add
kleing@24333
   690
                    append_Cons [symmetric] bl_to_bin_aux_append)
kleing@24333
   691
  apply simp
kleing@24333
   692
  done
kleing@24333
   693
huffman@24465
   694
(* function bl_of_nth *)
kleing@24333
   695
lemma length_bl_of_nth [simp]: "length (bl_of_nth n f) = n"
kleing@24333
   696
  by (induct n)  auto
kleing@24333
   697
kleing@24333
   698
lemma nth_bl_of_nth [simp]:
kleing@24333
   699
  "m < n \<Longrightarrow> rev (bl_of_nth n f) ! m = f m"
kleing@24333
   700
  apply (induct n)
kleing@24333
   701
   apply simp
kleing@24333
   702
  apply (clarsimp simp add : nth_append)
kleing@24333
   703
  apply (rule_tac f = "f" in arg_cong) 
kleing@24333
   704
  apply simp
kleing@24333
   705
  done
kleing@24333
   706
kleing@24333
   707
lemma bl_of_nth_inj: 
kleing@24333
   708
  "(!!k. k < n ==> f k = g k) ==> bl_of_nth n f = bl_of_nth n g"
kleing@24333
   709
  by (induct n)  auto
kleing@24333
   710
kleing@24333
   711
lemma bl_of_nth_nth_le [rule_format] : "ALL xs. 
kleing@24333
   712
    length xs >= n --> bl_of_nth n (nth (rev xs)) = drop (length xs - n) xs";
kleing@24333
   713
  apply (induct n, clarsimp)
kleing@24333
   714
  apply clarsimp
kleing@24333
   715
  apply (rule trans [OF _ hd_Cons_tl])
kleing@24333
   716
   apply (frule Suc_le_lessD)
kleing@24333
   717
   apply (simp add: nth_rev trans [OF drop_Suc drop_tl, symmetric])
kleing@24333
   718
   apply (subst hd_drop_conv_nth)
kleing@24333
   719
     apply force
kleing@24333
   720
    apply simp_all
kleing@24333
   721
  apply (rule_tac f = "%n. drop n xs" in arg_cong) 
kleing@24333
   722
  apply simp
kleing@24333
   723
  done
kleing@24333
   724
kleing@24333
   725
lemmas bl_of_nth_nth [simp] = order_refl [THEN bl_of_nth_nth_le, simplified]
kleing@24333
   726
kleing@24333
   727
lemma size_rbl_pred: "length (rbl_pred bl) = length bl"
kleing@24333
   728
  by (induct bl) auto
kleing@24333
   729
kleing@24333
   730
lemma size_rbl_succ: "length (rbl_succ bl) = length bl"
kleing@24333
   731
  by (induct bl) auto
kleing@24333
   732
kleing@24333
   733
lemma size_rbl_add:
kleing@24333
   734
  "!!cl. length (rbl_add bl cl) = length bl"
kleing@24333
   735
  by (induct bl) (auto simp: Let_def size_rbl_succ)
kleing@24333
   736
kleing@24333
   737
lemma size_rbl_mult: 
kleing@24333
   738
  "!!cl. length (rbl_mult bl cl) = length bl"
kleing@24333
   739
  by (induct bl) (auto simp add : Let_def size_rbl_add)
kleing@24333
   740
kleing@24333
   741
lemmas rbl_sizes [simp] = 
kleing@24333
   742
  size_rbl_pred size_rbl_succ size_rbl_add size_rbl_mult
kleing@24333
   743
kleing@24333
   744
lemmas rbl_Nils =
kleing@24333
   745
  rbl_pred.Nil rbl_succ.Nil rbl_add.Nil rbl_mult.Nil
kleing@24333
   746
kleing@24333
   747
lemma rbl_pred: 
kleing@24333
   748
  "!!bin. rbl_pred (rev (bin_to_bl n bin)) = rev (bin_to_bl n (Numeral.pred bin))"
kleing@24333
   749
  apply (induct n, simp)
kleing@24333
   750
  apply (unfold bin_to_bl_def)
kleing@24333
   751
  apply clarsimp
kleing@24333
   752
  apply (case_tac bin rule: bin_exhaust)
kleing@24333
   753
  apply (case_tac b)
kleing@24333
   754
   apply (clarsimp simp: bin_to_bl_aux_alt)+
kleing@24333
   755
  done
kleing@24333
   756
kleing@24333
   757
lemma rbl_succ: 
kleing@24333
   758
  "!!bin. rbl_succ (rev (bin_to_bl n bin)) = rev (bin_to_bl n (Numeral.succ bin))"
kleing@24333
   759
  apply (induct n, simp)
kleing@24333
   760
  apply (unfold bin_to_bl_def)
kleing@24333
   761
  apply clarsimp
kleing@24333
   762
  apply (case_tac bin rule: bin_exhaust)
kleing@24333
   763
  apply (case_tac b)
kleing@24333
   764
   apply (clarsimp simp: bin_to_bl_aux_alt)+
kleing@24333
   765
  done
kleing@24333
   766
kleing@24333
   767
lemma rbl_add: 
kleing@24333
   768
  "!!bina binb. rbl_add (rev (bin_to_bl n bina)) (rev (bin_to_bl n binb)) = 
kleing@24333
   769
    rev (bin_to_bl n (bina + binb))"
kleing@24333
   770
  apply (induct n, simp)
kleing@24333
   771
  apply (unfold bin_to_bl_def)
kleing@24333
   772
  apply clarsimp
kleing@24333
   773
  apply (case_tac bina rule: bin_exhaust)
kleing@24333
   774
  apply (case_tac binb rule: bin_exhaust)
kleing@24333
   775
  apply (case_tac b)
kleing@24333
   776
   apply (case_tac [!] "ba")
kleing@24333
   777
     apply (auto simp: rbl_succ succ_def bin_to_bl_aux_alt Let_def add_ac)
kleing@24333
   778
  done
kleing@24333
   779
kleing@24333
   780
lemma rbl_add_app2: 
kleing@24333
   781
  "!!blb. length blb >= length bla ==> 
kleing@24333
   782
    rbl_add bla (blb @ blc) = rbl_add bla blb"
kleing@24333
   783
  apply (induct bla, simp)
kleing@24333
   784
  apply clarsimp
kleing@24333
   785
  apply (case_tac blb, clarsimp)
kleing@24333
   786
  apply (clarsimp simp: Let_def)
kleing@24333
   787
  done
kleing@24333
   788
kleing@24333
   789
lemma rbl_add_take2: 
kleing@24333
   790
  "!!blb. length blb >= length bla ==> 
kleing@24333
   791
    rbl_add bla (take (length bla) blb) = rbl_add bla blb"
kleing@24333
   792
  apply (induct bla, simp)
kleing@24333
   793
  apply clarsimp
kleing@24333
   794
  apply (case_tac blb, clarsimp)
kleing@24333
   795
  apply (clarsimp simp: Let_def)
kleing@24333
   796
  done
kleing@24333
   797
kleing@24333
   798
lemma rbl_add_long: 
kleing@24333
   799
  "m >= n ==> rbl_add (rev (bin_to_bl n bina)) (rev (bin_to_bl m binb)) = 
kleing@24333
   800
    rev (bin_to_bl n (bina + binb))"
kleing@24333
   801
  apply (rule box_equals [OF _ rbl_add_take2 rbl_add])
kleing@24333
   802
   apply (rule_tac f = "rbl_add (rev (bin_to_bl n bina))" in arg_cong) 
kleing@24333
   803
   apply (rule rev_swap [THEN iffD1])
kleing@24333
   804
   apply (simp add: rev_take drop_bin2bl)
kleing@24333
   805
  apply simp
kleing@24333
   806
  done
kleing@24333
   807
kleing@24333
   808
lemma rbl_mult_app2:
kleing@24333
   809
  "!!blb. length blb >= length bla ==> 
kleing@24333
   810
    rbl_mult bla (blb @ blc) = rbl_mult bla blb"
kleing@24333
   811
  apply (induct bla, simp)
kleing@24333
   812
  apply clarsimp
kleing@24333
   813
  apply (case_tac blb, clarsimp)
kleing@24333
   814
  apply (clarsimp simp: Let_def rbl_add_app2)
kleing@24333
   815
  done
kleing@24333
   816
kleing@24333
   817
lemma rbl_mult_take2: 
kleing@24333
   818
  "length blb >= length bla ==> 
kleing@24333
   819
    rbl_mult bla (take (length bla) blb) = rbl_mult bla blb"
kleing@24333
   820
  apply (rule trans)
kleing@24333
   821
   apply (rule rbl_mult_app2 [symmetric])
kleing@24333
   822
   apply simp
kleing@24333
   823
  apply (rule_tac f = "rbl_mult bla" in arg_cong) 
kleing@24333
   824
  apply (rule append_take_drop_id)
kleing@24333
   825
  done
kleing@24333
   826
    
kleing@24333
   827
lemma rbl_mult_gt1: 
kleing@24333
   828
  "m >= length bl ==> rbl_mult bl (rev (bin_to_bl m binb)) = 
kleing@24333
   829
    rbl_mult bl (rev (bin_to_bl (length bl) binb))"
kleing@24333
   830
  apply (rule trans)
kleing@24333
   831
   apply (rule rbl_mult_take2 [symmetric])
kleing@24333
   832
   apply simp_all
kleing@24333
   833
  apply (rule_tac f = "rbl_mult bl" in arg_cong) 
kleing@24333
   834
  apply (rule rev_swap [THEN iffD1])
kleing@24333
   835
  apply (simp add: rev_take drop_bin2bl)
kleing@24333
   836
  done
kleing@24333
   837
    
kleing@24333
   838
lemma rbl_mult_gt: 
kleing@24333
   839
  "m > n ==> rbl_mult (rev (bin_to_bl n bina)) (rev (bin_to_bl m binb)) = 
kleing@24333
   840
    rbl_mult (rev (bin_to_bl n bina)) (rev (bin_to_bl n binb))"
kleing@24333
   841
  by (auto intro: trans [OF rbl_mult_gt1])
kleing@24333
   842
  
kleing@24333
   843
lemmas rbl_mult_Suc = lessI [THEN rbl_mult_gt]
kleing@24333
   844
kleing@24333
   845
lemma rbbl_Cons: 
kleing@24333
   846
  "b # rev (bin_to_bl n x) = rev (bin_to_bl (Suc n) (x BIT If b bit.B1 bit.B0))"
kleing@24333
   847
  apply (unfold bin_to_bl_def)
kleing@24333
   848
  apply simp
kleing@24333
   849
  apply (simp add: bin_to_bl_aux_alt)
kleing@24333
   850
  done
kleing@24333
   851
  
kleing@24333
   852
lemma rbl_mult: "!!bina binb. 
kleing@24333
   853
    rbl_mult (rev (bin_to_bl n bina)) (rev (bin_to_bl n binb)) = 
kleing@24333
   854
    rev (bin_to_bl n (bina * binb))"
kleing@24333
   855
  apply (induct n)
kleing@24333
   856
   apply simp
kleing@24333
   857
  apply (unfold bin_to_bl_def)
kleing@24333
   858
  apply clarsimp
kleing@24333
   859
  apply (case_tac bina rule: bin_exhaust)
kleing@24333
   860
  apply (case_tac binb rule: bin_exhaust)
kleing@24333
   861
  apply (case_tac b)
kleing@24333
   862
   apply (case_tac [!] "ba")
kleing@24333
   863
     apply (auto simp: bin_to_bl_aux_alt Let_def)
kleing@24333
   864
     apply (auto simp: rbbl_Cons rbl_mult_Suc rbl_add)
kleing@24333
   865
  done
kleing@24333
   866
kleing@24333
   867
lemma rbl_add_split: 
kleing@24333
   868
  "P (rbl_add (y # ys) (x # xs)) = 
kleing@24333
   869
    (ALL ws. length ws = length ys --> ws = rbl_add ys xs --> 
kleing@24333
   870
    (y --> ((x --> P (False # rbl_succ ws)) & (~ x -->  P (True # ws)))) & \ 
kleing@24333
   871
    (~ y --> P (x # ws)))"
kleing@24333
   872
  apply (auto simp add: Let_def)
kleing@24333
   873
   apply (case_tac [!] "y")
kleing@24333
   874
     apply auto
kleing@24333
   875
  done
kleing@24333
   876
kleing@24333
   877
lemma rbl_mult_split: 
kleing@24333
   878
  "P (rbl_mult (y # ys) xs) = 
kleing@24333
   879
    (ALL ws. length ws = Suc (length ys) --> ws = False # rbl_mult ys xs --> 
kleing@24333
   880
    (y --> P (rbl_add ws xs)) & (~ y -->  P ws))"
kleing@24333
   881
  by (clarsimp simp add : Let_def)
kleing@24333
   882
  
kleing@24333
   883
lemma and_len: "xs = ys ==> xs = ys & length xs = length ys"
kleing@24333
   884
  by auto
kleing@24333
   885
kleing@24333
   886
lemma size_if: "size (if p then xs else ys) = (if p then size xs else size ys)"
kleing@24333
   887
  by auto
kleing@24333
   888
kleing@24333
   889
lemma tl_if: "tl (if p then xs else ys) = (if p then tl xs else tl ys)"
kleing@24333
   890
  by auto
kleing@24333
   891
kleing@24333
   892
lemma hd_if: "hd (if p then xs else ys) = (if p then hd xs else hd ys)"
kleing@24333
   893
  by auto
kleing@24333
   894
huffman@24465
   895
lemma if_Not_x: "(if p then ~ x else x) = (p = (~ x))"
huffman@24465
   896
  by auto
huffman@24465
   897
huffman@24465
   898
lemma if_x_Not: "(if p then x else ~ x) = (p = x)"
huffman@24465
   899
  by auto
huffman@24465
   900
kleing@24333
   901
lemma if_same_and: "(If p x y & If p u v) = (if p then x & u else y & v)"
kleing@24333
   902
  by auto
kleing@24333
   903
kleing@24333
   904
lemma if_same_eq: "(If p x y  = (If p u v)) = (if p then x = (u) else y = (v))"
kleing@24333
   905
  by auto
kleing@24333
   906
kleing@24333
   907
lemma if_same_eq_not:
kleing@24333
   908
  "(If p x y  = (~ If p u v)) = (if p then x = (~u) else y = (~v))"
kleing@24333
   909
  by auto
kleing@24333
   910
kleing@24333
   911
(* note - if_Cons can cause blowup in the size, if p is complex,
kleing@24333
   912
  so make a simproc *)
kleing@24333
   913
lemma if_Cons: "(if p then x # xs else y # ys) = If p x y # If p xs ys"
kleing@24333
   914
  by auto
kleing@24333
   915
kleing@24333
   916
lemma if_single:
kleing@24333
   917
  "(if xc then [xab] else [an]) = [if xc then xab else an]"
kleing@24333
   918
  by auto
kleing@24333
   919
huffman@24465
   920
lemma if_bool_simps:
huffman@24465
   921
  "If p True y = (p | y) & If p False y = (~p & y) & 
huffman@24465
   922
    If p y True = (p --> y) & If p y False = (p & y)"
huffman@24465
   923
  by auto
huffman@24465
   924
huffman@24465
   925
lemmas if_simps = if_x_Not if_Not_x if_cancel if_True if_False if_bool_simps
huffman@24465
   926
kleing@24333
   927
lemmas seqr = eq_reflection [where x = "size ?w"]
kleing@24333
   928
kleing@24333
   929
lemmas tl_Nil = tl.simps (1)
kleing@24333
   930
lemmas tl_Cons = tl.simps (2)
kleing@24333
   931
kleing@24333
   932
huffman@24350
   933
subsection "Repeated splitting or concatenation"
kleing@24333
   934
kleing@24333
   935
lemma sclem:
kleing@24333
   936
  "size (concat (map (bin_to_bl n) xs)) = length xs * n"
kleing@24333
   937
  by (induct xs) auto
kleing@24333
   938
kleing@24333
   939
lemma bin_cat_foldl_lem [rule_format] :
kleing@24333
   940
  "ALL x. foldl (%u. bin_cat u n) x xs = 
kleing@24333
   941
    bin_cat x (size xs * n) (foldl (%u. bin_cat u n) y xs)"
kleing@24333
   942
  apply (induct xs)
kleing@24333
   943
   apply simp
kleing@24333
   944
  apply clarify
kleing@24333
   945
  apply (simp (no_asm))
kleing@24333
   946
  apply (frule asm_rl)
kleing@24333
   947
  apply (drule spec)
kleing@24333
   948
  apply (erule trans)
kleing@24333
   949
  apply (drule_tac x = "bin_cat y n a" in spec) 
kleing@24333
   950
  apply (simp add : bin_cat_assoc_sym min_def)
kleing@24333
   951
  done
kleing@24333
   952
kleing@24333
   953
lemma bin_rcat_bl:
kleing@24333
   954
  "(bin_rcat n wl) = bl_to_bin (concat (map (bin_to_bl n) wl))"
kleing@24333
   955
  apply (unfold bin_rcat_def)
kleing@24333
   956
  apply (rule sym)
kleing@24333
   957
  apply (induct wl)
kleing@24333
   958
   apply (auto simp add : bl_to_bin_append)
kleing@24333
   959
  apply (simp add : bl_to_bin_aux_alt sclem)
kleing@24333
   960
  apply (simp add : bin_cat_foldl_lem [symmetric])
kleing@24333
   961
  done
kleing@24333
   962
kleing@24333
   963
lemmas bin_rsplit_aux_simps = bin_rsplit_aux.simps bin_rsplitl_aux.simps
kleing@24333
   964
lemmas rsplit_aux_simps = bin_rsplit_aux_simps
kleing@24333
   965
kleing@24333
   966
lemmas th_if_simp1 = split_if [where P = "op = ?l",
kleing@24333
   967
  THEN iffD1, THEN conjunct1, THEN mp, standard]
kleing@24333
   968
lemmas th_if_simp2 = split_if [where P = "op = ?l",
kleing@24333
   969
  THEN iffD1, THEN conjunct2, THEN mp, standard]
kleing@24333
   970
kleing@24333
   971
lemmas rsplit_aux_simp1s = rsplit_aux_simps [THEN th_if_simp1]
kleing@24333
   972
kleing@24333
   973
lemmas rsplit_aux_simp2ls = rsplit_aux_simps [THEN th_if_simp2]
kleing@24333
   974
(* these safe to [simp add] as require calculating m - n *)
kleing@24333
   975
lemmas bin_rsplit_aux_simp2s [simp] = rsplit_aux_simp2ls [unfolded Let_def]
kleing@24333
   976
lemmas rbscl = bin_rsplit_aux_simp2s (2)
kleing@24333
   977
kleing@24333
   978
lemmas rsplit_aux_0_simps [simp] = 
kleing@24333
   979
  rsplit_aux_simp1s [OF disjI1] rsplit_aux_simp1s [OF disjI2]
kleing@24333
   980
kleing@24333
   981
lemma bin_rsplit_aux_append:
kleing@24333
   982
  "bin_rsplit_aux (n, bs @ cs, m, c) = bin_rsplit_aux (n, bs, m, c) @ cs"
kleing@24333
   983
  apply (rule_tac u=n and v=bs and w=m and x=c in bin_rsplit_aux.induct)
kleing@24333
   984
  apply (subst bin_rsplit_aux.simps)
kleing@24333
   985
  apply (subst bin_rsplit_aux.simps)
kleing@24333
   986
  apply (clarsimp split: ls_splits)
kleing@24333
   987
  done
kleing@24333
   988
kleing@24333
   989
lemma bin_rsplitl_aux_append:
kleing@24333
   990
  "bin_rsplitl_aux (n, bs @ cs, m, c) = bin_rsplitl_aux (n, bs, m, c) @ cs"
kleing@24333
   991
  apply (rule_tac u=n and v=bs and w=m and x=c in bin_rsplitl_aux.induct)
kleing@24333
   992
  apply (subst bin_rsplitl_aux.simps)
kleing@24333
   993
  apply (subst bin_rsplitl_aux.simps)
kleing@24333
   994
  apply (clarsimp split: ls_splits)
kleing@24333
   995
  done
kleing@24333
   996
kleing@24333
   997
lemmas rsplit_aux_apps [where bs = "[]"] =
kleing@24333
   998
  bin_rsplit_aux_append bin_rsplitl_aux_append
kleing@24333
   999
kleing@24333
  1000
lemmas rsplit_def_auxs = bin_rsplit_def bin_rsplitl_def
kleing@24333
  1001
kleing@24333
  1002
lemmas rsplit_aux_alts = rsplit_aux_apps 
kleing@24333
  1003
  [unfolded append_Nil rsplit_def_auxs [symmetric]]
kleing@24333
  1004
kleing@24333
  1005
lemma bin_split_minus: "0 < n ==> bin_split (Suc (n - 1)) w = bin_split n w"
kleing@24333
  1006
  by auto
kleing@24333
  1007
kleing@24333
  1008
lemmas bin_split_minus_simp =
kleing@24333
  1009
  bin_split.Suc [THEN [2] bin_split_minus [symmetric, THEN trans], standard]
kleing@24333
  1010
kleing@24333
  1011
lemma bin_split_pred_simp [simp]: 
kleing@24333
  1012
  "(0::nat) < number_of bin \<Longrightarrow>
kleing@24333
  1013
  bin_split (number_of bin) w =
kleing@24333
  1014
  (let (w1, w2) = bin_split (number_of (Numeral.pred bin)) (bin_rest w)
kleing@24333
  1015
   in (w1, w2 BIT bin_last w))" 
kleing@24333
  1016
  by (simp only: nobm1 bin_split_minus_simp)
kleing@24333
  1017
huffman@24465
  1018
declare bin_split_pred_simp [simp]
huffman@24465
  1019
kleing@24333
  1020
lemma bin_rsplit_aux_simp_alt:
kleing@24333
  1021
  "bin_rsplit_aux (n, bs, m, c) =
kleing@24333
  1022
   (if m = 0 \<or> n = 0 
kleing@24333
  1023
   then bs
kleing@24333
  1024
   else let (a, b) = bin_split n c in bin_rsplit n (m - n, a) @ b # bs)"
kleing@24333
  1025
  apply (rule trans)
kleing@24333
  1026
   apply (subst bin_rsplit_aux.simps, rule refl)
kleing@24333
  1027
  apply (simp add: rsplit_aux_alts)
kleing@24333
  1028
  done
kleing@24333
  1029
kleing@24333
  1030
lemmas bin_rsplit_simp_alt = 
kleing@24333
  1031
  trans [OF bin_rsplit_def [THEN meta_eq_to_obj_eq]
kleing@24333
  1032
            bin_rsplit_aux_simp_alt, standard]
kleing@24333
  1033
kleing@24333
  1034
lemmas bthrs = bin_rsplit_simp_alt [THEN [2] trans]
kleing@24333
  1035
kleing@24333
  1036
lemma bin_rsplit_size_sign' [rule_format] : 
kleing@24333
  1037
  "n > 0 ==> (ALL nw w. rev sw = bin_rsplit n (nw, w) --> 
kleing@24333
  1038
    (ALL v: set sw. bintrunc n v = v))"
kleing@24333
  1039
  apply (induct sw)
kleing@24333
  1040
   apply clarsimp
kleing@24333
  1041
  apply clarsimp
kleing@24333
  1042
  apply (drule bthrs)
kleing@24333
  1043
  apply (simp (no_asm_use) add: Let_def split: ls_splits)
kleing@24333
  1044
  apply clarify
kleing@24333
  1045
  apply (erule impE, rule exI, erule exI)
kleing@24333
  1046
  apply (drule split_bintrunc)
kleing@24333
  1047
  apply simp
kleing@24333
  1048
  done
kleing@24333
  1049
kleing@24333
  1050
lemmas bin_rsplit_size_sign = bin_rsplit_size_sign' [OF asm_rl 
kleing@24333
  1051
  rev_rev_ident [THEN trans] set_rev [THEN equalityD2 [THEN subsetD]],
kleing@24333
  1052
  standard]
kleing@24333
  1053
kleing@24333
  1054
lemma bin_nth_rsplit [rule_format] :
kleing@24333
  1055
  "n > 0 ==> m < n ==> (ALL w k nw. rev sw = bin_rsplit n (nw, w) --> 
kleing@24333
  1056
       k < size sw --> bin_nth (sw ! k) m = bin_nth w (k * n + m))"
kleing@24333
  1057
  apply (induct sw)
kleing@24333
  1058
   apply clarsimp
kleing@24333
  1059
  apply clarsimp
kleing@24333
  1060
  apply (drule bthrs)
kleing@24333
  1061
  apply (simp (no_asm_use) add: Let_def split: ls_splits)
kleing@24333
  1062
  apply clarify
kleing@24333
  1063
  apply (erule allE, erule impE, erule exI)
kleing@24333
  1064
  apply (case_tac k)
kleing@24333
  1065
   apply clarsimp   
kleing@24333
  1066
   prefer 2
kleing@24333
  1067
   apply clarsimp
kleing@24333
  1068
   apply (erule allE)
kleing@24333
  1069
   apply (erule (1) impE)
kleing@24333
  1070
   apply (drule bin_nth_split, erule conjE, erule allE,
kleing@24333
  1071
          erule trans, simp add : add_ac)+
kleing@24333
  1072
  done
kleing@24333
  1073
kleing@24333
  1074
lemma bin_rsplit_all:
kleing@24333
  1075
  "0 < nw ==> nw <= n ==> bin_rsplit n (nw, w) = [bintrunc n w]"
kleing@24333
  1076
  unfolding bin_rsplit_def
kleing@24333
  1077
  by (clarsimp dest!: split_bintrunc simp: rsplit_aux_simp2ls split: ls_splits)
kleing@24333
  1078
kleing@24333
  1079
lemma bin_rsplit_l [rule_format] :
kleing@24333
  1080
  "ALL bin. bin_rsplitl n (m, bin) = bin_rsplit n (m, bintrunc m bin)"
kleing@24333
  1081
  apply (rule_tac a = "m" in wf_less_than [THEN wf_induct])
kleing@24333
  1082
  apply (simp (no_asm) add : bin_rsplitl_def bin_rsplit_def)
kleing@24333
  1083
  apply (rule allI)
kleing@24333
  1084
  apply (subst bin_rsplitl_aux.simps)
kleing@24333
  1085
  apply (subst bin_rsplit_aux.simps)
kleing@24333
  1086
  apply (clarsimp simp: rsplit_aux_alts Let_def split: ls_splits)
kleing@24333
  1087
  apply (drule bin_split_trunc)
kleing@24333
  1088
  apply (drule sym [THEN trans], assumption)
kleing@24333
  1089
  apply fast
kleing@24333
  1090
  done
kleing@24333
  1091
    
kleing@24333
  1092
lemma bin_rsplit_rcat [rule_format] :
kleing@24333
  1093
  "n > 0 --> bin_rsplit n (n * size ws, bin_rcat n ws) = map (bintrunc n) ws"
kleing@24333
  1094
  apply (unfold bin_rsplit_def bin_rcat_def)
kleing@24333
  1095
  apply (rule_tac xs = "ws" in rev_induct)
kleing@24333
  1096
   apply clarsimp
kleing@24333
  1097
  apply clarsimp
kleing@24333
  1098
  apply (clarsimp simp add: bin_split_cat rsplit_aux_alts)
kleing@24333
  1099
  done
kleing@24333
  1100
kleing@24333
  1101
lemma bin_rsplit_aux_len_le [rule_format] :
kleing@24333
  1102
  "ALL ws m. n > 0 --> ws = bin_rsplit_aux (n, bs, nw, w) --> 
kleing@24333
  1103
    (length ws <= m) = (nw + length bs * n <= m * n)"
kleing@24333
  1104
  apply (rule_tac u=n and v=bs and w=nw and x=w in bin_rsplit_aux.induct)
kleing@24333
  1105
  apply (subst bin_rsplit_aux.simps)
chaieb@25112
  1106
  apply (clarsimp simp: Let_def neq0_conv split: ls_splits )
kleing@24333
  1107
  apply (erule lrlem)
kleing@24333
  1108
  done
kleing@24333
  1109
kleing@24333
  1110
lemma bin_rsplit_len_le: 
kleing@24333
  1111
  "n > 0 --> ws = bin_rsplit n (nw, w) --> (length ws <= m) = (nw <= m * n)"
kleing@24333
  1112
  unfolding bin_rsplit_def by (clarsimp simp add : bin_rsplit_aux_len_le)
kleing@24333
  1113
 
kleing@24333
  1114
lemma bin_rsplit_aux_len [rule_format] :
kleing@24333
  1115
  "0 < n --> length (bin_rsplit_aux (n, cs, nw, w)) = 
kleing@24333
  1116
    (nw + n - 1) div n + length cs"
kleing@24333
  1117
  apply (rule_tac u=n and v=cs and w=nw and x=w in bin_rsplit_aux.induct)
kleing@24333
  1118
  apply (subst bin_rsplit_aux.simps)
kleing@24333
  1119
  apply (clarsimp simp: Let_def split: ls_splits)
kleing@24333
  1120
  apply (erule thin_rl)
kleing@24333
  1121
  apply (case_tac "m <= n")
kleing@24333
  1122
   prefer 2
kleing@24333
  1123
   apply (simp add: div_add_self2 [symmetric])
kleing@24333
  1124
  apply (case_tac m, clarsimp)
kleing@24333
  1125
  apply (simp add: div_add_self2)
kleing@24333
  1126
  done
kleing@24333
  1127
kleing@24333
  1128
lemma bin_rsplit_len: 
kleing@24333
  1129
  "0 < n ==> length (bin_rsplit n (nw, w)) = (nw + n - 1) div n"
kleing@24333
  1130
  unfolding bin_rsplit_def by (clarsimp simp add : bin_rsplit_aux_len)
kleing@24333
  1131
kleing@24333
  1132
lemma bin_rsplit_aux_len_indep [rule_format] :
kleing@24333
  1133
  "0 < n ==> (ALL v bs. length bs = length cs --> 
kleing@24333
  1134
    length (bin_rsplit_aux (n, bs, nw, v)) = 
kleing@24333
  1135
    length (bin_rsplit_aux (n, cs, nw, w)))"
kleing@24333
  1136
  apply (rule_tac u=n and v=cs and w=nw and x=w in bin_rsplit_aux.induct)
kleing@24333
  1137
  apply clarsimp
kleing@24333
  1138
  apply (simp (no_asm_simp) add: bin_rsplit_aux_simp_alt Let_def 
kleing@24333
  1139
                            split: ls_splits)
kleing@24333
  1140
  apply clarify 
kleing@24333
  1141
  apply (erule allE)+
kleing@24333
  1142
  apply (erule impE)
kleing@24333
  1143
   apply (fast elim!: sym)
kleing@24333
  1144
  apply (simp (no_asm_use) add: rsplit_aux_alts)
kleing@24333
  1145
  apply (erule impE)
kleing@24333
  1146
  apply (rule_tac x="ba # bs" in exI)
kleing@24333
  1147
  apply auto
kleing@24333
  1148
  done
kleing@24333
  1149
kleing@24333
  1150
lemma bin_rsplit_len_indep: 
kleing@24333
  1151
  "0 < n ==> length (bin_rsplit n (nw, v)) = length (bin_rsplit n (nw, w))"
kleing@24333
  1152
  apply (unfold bin_rsplit_def)
kleing@24333
  1153
  apply (erule bin_rsplit_aux_len_indep)
kleing@24333
  1154
  apply (rule refl)
kleing@24333
  1155
  done
kleing@24333
  1156
kleing@24333
  1157
end
kleing@24333
  1158