src/HOL/Imperative_HOL/ex/Linked_Lists.thy
changeset 37709 70fafefbcc98
parent 36098 53992c639da5
child 37725 6d28a2aea936
equal deleted inserted replaced
37706:c63649d8d75b 37709:70fafefbcc98
    54   "traverse (Node x r) = do tl \<leftarrow> Ref.lookup r;
    54   "traverse (Node x r) = do tl \<leftarrow> Ref.lookup r;
    55                             xs \<leftarrow> traverse tl;
    55                             xs \<leftarrow> traverse tl;
    56                             return (x#xs)
    56                             return (x#xs)
    57                          done"
    57                          done"
    58 unfolding traverse_def
    58 unfolding traverse_def
    59 by (auto simp: traverse_def monad_simp MREC_rule)
    59 by (auto simp: traverse_def MREC_rule)
    60 
    60 
    61 
    61 
    62 section {* Proving correctness with relational abstraction *}
    62 section {* Proving correctness with relational abstraction *}
    63 
    63 
    64 subsection {* Definition of list_of, list_of', refs_of and refs_of' *}
    64 subsection {* Definition of list_of, list_of', refs_of and refs_of' *}
   529           rev' (p, next)
   529           rev' (p, next)
   530         done)
   530         done)
   531   done"
   531   done"
   532   unfolding rev'_def MREC_rule[of _ _ "(q, p)"] unfolding rev'_def[symmetric]
   532   unfolding rev'_def MREC_rule[of _ _ "(q, p)"] unfolding rev'_def[symmetric]
   533 thm arg_cong2
   533 thm arg_cong2
   534   by (auto simp add: monad_simp expand_fun_eq intro: arg_cong2[where f = "op \<guillemotright>="] split: node.split)
   534   by (auto simp add: expand_fun_eq intro: arg_cong2[where f = "op \<guillemotright>="] split: node.split)
   535 
   535 
   536 fun rev :: "('a:: heap) node \<Rightarrow> 'a node Heap" 
   536 fun rev :: "('a:: heap) node \<Rightarrow> 'a node Heap" 
   537 where
   537 where
   538   "rev Empty = return Empty"
   538   "rev Empty = return Empty"
   539 | "rev (Node x n) = (do q \<leftarrow> Ref.new Empty; p \<leftarrow> Ref.new (Node x n); v \<leftarrow> rev' (q, p); !v done)"
   539 | "rev (Node x n) = (do q \<leftarrow> Ref.new Empty; p \<leftarrow> Ref.new (Node x n); v \<leftarrow> rev' (q, p); !v done)"