Rob Simmons avatar Rob Simmons committed 33df908

Binary insertion

Comments (0)

Files changed (1)

+# Examples from Yasuhiko Minamide's 1998 POPL paper "A Functional 
+# Representation of Data Structures with a Hole."
+
 # Figure 2: Using Hole Abstractions for Lists
 # No polymorphic lists, blah.
 
 
 
 # Figure 3: Using Hole Abstractions for Trees
+# No exceptions, so inserting an extant value just keeps the tree the same
 
 data Lf: tree
    | Br: int -o tree -o tree -o tree ;; 
 
+val binsert = thunk rec binsert: tree -> int -> F tree is
+  fun t: tree ->
+  fun y: int -> 
+    match t with
+      | Lf -> return Br y Lf Lf
+      | Br x t1 t2 ->
+          if y < x 
+          then force binsert t1 y to t1' in return Br x t1' t2
+          else if x < y 
+          then force binsert t2 y to t2' in return Br x t1 t2'
+          else return Br x t1 t2 ;; 
+
+val hfun_binsert = thunk fun t: tree -> fun y: int ->
+  let binsert' be thunk rec binsert': tree -> int -> (tree -o tree) -> F tree is
+    fun t: tree ->
+    fun y: int ->
+    fun k: (tree -o tree) ->
+      match t with
+        | Lf -> return k (Br y Lf Lf) 
+        | Br x t1 t2 -> 
+            if y < x 
+            then force binsert' t1 y ([hole: tree] k (Br x hole t2))
+            else if x < y
+            then force binsert' t2 y ([hole: tree] k (Br x t1 hole))
+            else return k (Br x t1 t2) 
+  in 
+    force binsert' t y ([hole: tree] hole) ;;
Tip: Filter by directory path e.g. /media app.js to search for public/media/app.js.
Tip: Use camelCasing e.g. ProjME to search for ProjectModifiedEvent.java.
Tip: Filter by extension type e.g. /repo .js to search for all .js files in the /repo directory.
Tip: Separate your search with spaces e.g. /ssh pom.xml to search for src/ssh/pom.xml.
Tip: Use ↑ and ↓ arrow keys to navigate and return to view the file.
Tip: You can also navigate files with Ctrl+j (next) and Ctrl+k (previous) and view the file with Ctrl+o.
Tip: You can also navigate files with Alt+j (next) and Alt+k (previous) and view the file with Alt+o.