:PROPERTIES: :ID: 6d990717-fce8-4821-8f4c-f21c3964666e :mtime: 20231030033229 :ctime: 20231030033227 :END: #+title: imperative programming in ocaml #+filetags: :public:project: Imperative programming in [[id:8952459c-5076-4e68-8a68-5f658209f39e][Ocaml]] * Update #+BEGIN_SRC ocaml let update f r = r := f (!r) #+END_SRC #+RESULTS: : <fun> * Examples ** Example: [[id:cf967e5c-c8fd-4fd3-b333-e7c26925dca4][List]] length [[id:9ff5f281-61c5-4726-9d00-f5b2bd9a0fa8][tail-recursive]]length of a list #+BEGIN_SRC ocaml let length' = let addLen n xs = match xs with | [] -> n | a :: as -> addLen (n + 1) as in addLen 0 #+END_SRC #+RESULTS: : Line 4, characters 15-17: : 4 | | a :: as -> addLen (n + 1) as : ^^ : Error: Syntax error: pattern expected. Imperative length of a list #+BEGIN_SRC ocaml let length (xs : 'a list) : int = let lp = ref xs in let np = ref 0 in while !lp != [] do update succ np; update List.tl lp done; !np #+END_SRC #+RESULTS: : <fun> #+BEGIN_SRC ocaml length [1 ; 2 ; 3 ; 4] #+END_SrC #+RESULTS: : 4 ** Example: Bank account #+BEGIN_SRC ocaml exception Overdraw of int let makeAccount initialBalance = let balance = ref initialBalance in let withdraw amount = if amount > !balance then raise (Overdraw amount) else begin update (Fun.flip (-) amount) balance ; !balance end in withdraw #+END_SRC #+RESULTS: : <fun> #+BEGIN_SRC ocaml let student = makeAccount 500 #+END_SRC #+RESULTS: : <fun> #+BEGIN_SRC ocaml student 5 #+END_SRC #+RESULTS: : 495 #+BEGIN_SRC ocaml student 5000 #+END_SRC #+RESULTS: : Exception: Overdraw 5000. ** Example: Mutable linked [[id:cf967e5c-c8fd-4fd3-b333-e7c26925dca4][list]] #+BEGIN_SRC ocaml type 'a mlist = | Nil | Cons of 'a * 'a mlist ref #+END_SRC #+RESULTS: : type 'a mlist = Nil | Cons of 'a * 'a mlist ref #+BEGIN_SRC ocaml let rec mlistof = function | [] -> Nil | x :: xs -> Cons (x , ref (mlistof xs)) #+END_SRC #+RESULTS: : <fun> #+BEGIN_SRC ocaml let extend mlp x = let last = ref Nil in mlp := Cons (x , last) ; last #+END_SRC #+RESULTS: : <fun> Linear time, constant space append for lists. #+BEGIN_SRC ocaml let rec joining (mlp : 'a mlist ref) (ml2 : 'a mlist) : unit = match !mlp with | Nil -> mlp := ml2 | Cons (_ , mlp1) -> joining mlp1 ml2 let join (ml1 : 'a mlist) (ml2 : 'a mlist) : 'a mlist = let mlp = ref ml1 in joining mlp ml2 ; !mlp #+END_SRC #+RESULTS: : <fun> #+BEGIN_SRC ocaml let ml1 = mlistof ["a" ; "b"] let ml2 = mlistof ["c" ; "d"] #+END_SRC #+RESULTS: : Cons ("c", {contents = Cons ("d", {contents = Nil})}) #+BEGIN_SRC ocaml join ml1 ml2 #+END_SRC #+RESULTS: : Cons ("a", : {contents = : Cons ("b", : {contents = Cons ("c", {contents = Cons ("d", {contents = Nil})})})}) #+BEGIN_SRC ocaml ml2 #+END_SRC #+RESULTS: : Cons ("c", {contents = Cons ("d", {contents = Nil})})