src/Pure/General/balanced_tree.ML

+(*  Title:      Pure/General/balanced_tree.ML
+    ID:         $Id$
+    Author:     Lawrence C Paulson and Makarius
+
+Balanced binary trees.
+*)
+
+signature BALANCED_TREE =
+sig
+  val make: ('a * 'a -> 'a) -> 'a list -> 'a
+  val dest: ('a -> 'a * 'a) -> int -> 'a -> 'a list
+  val access: {left: 'a -> 'a, right: 'a -> 'a, init: 'a} -> int -> int -> 'a
+  val accesses: {left: 'a -> 'a, right: 'a -> 'a, init: 'a} -> int -> 'a list
+end;
+
+structure BalancedTree: BALANCED_TREE =
+struct
+
+fun make _ [] = raise Empty
+  | make _ [x] = x
+  | make f xs =
+      let
+        val m = length xs div 2;
+        val (ps, qs) = chop m xs;
+      in f (make f ps, make f qs) end;
+
+fun dest f n x =
+  if n <= 0 then raise Empty
+  else if n = 1 then [x]
+  else
+    let
+      val m = n div 2;
+      val (left, right) = f x;
+    in dest f m left @ dest f (n - m) right end;
+
+(*construct something of the form f(...g(...(x)...)) for balanced access*)
+fun access {left = f, right = g, init = x} len i =
+  let
+    fun acc 1 _ = x
+      | acc n i =
+          let val m = n div 2 in
+            if i <= m then f (acc m i)
+            else g (acc (n - m) (i - m))
+          end;
+  in if 1 <= i andalso i <= len then acc len i else raise Subscript end;
+
+(*construct ALL such accesses; could try harder to share recursive calls!*)
+fun accesses {left = f, right = g, init = x} len =
+  let
+    fun acc 1 = [x]
+      | acc n =
+          let
+            val m = n div 2;
+            val accs_left = acc m;
+            val accs_right =
+              if n - m = m then accs_left
+              else acc (n - m);
+          in map f accs_left @ map g accs_right end;
+  in if 1 <= len then acc len else raise Subscript end;
+
+end;