SHARE
TWEET

Untitled

a guest May 19th, 2019 69 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. module Tree = struct
  2.   type t = Leaf | Node of t * t
  3.  
  4.   let rec size = function
  5.     | Leaf -> 0
  6.     | Node (x, y) -> 1 + size x + size y
  7. end
  8.  
  9. type instr = Gen | Build
  10.  
  11. let pop2 = function
  12.   | x :: y :: l -> x, y, l
  13.   | _ -> invalid_arg "pop2"
  14.  
  15. module type Boltz = sig
  16.   val size : unit -> int
  17.   val gen : unit -> Tree.t
  18. end
  19.  
  20. module Specialised = struct
  21.   let size =
  22.     let rec aux s = function
  23.       | 0 -> s
  24.       | n ->
  25.         let n = n - 1 in
  26.         if Random.bool () then aux s n
  27.         else aux (s + 1) (n + 2)
  28.     in
  29.     fun () -> aux 0 1
  30.  
  31.   let gen =
  32.     let rec aux res = function
  33.       | Gen :: stack ->
  34.         if Random.bool () then aux (Tree.Leaf :: res) stack
  35.         else aux res (Gen :: Gen :: Build :: stack)
  36.       | Build :: stack ->
  37.         let x, y, res = pop2 res in
  38.         aux (Tree.Node (x, y) :: res) stack
  39.       | [] -> res
  40.     in
  41.     fun () -> aux [] [Gen] |> List.hd
  42. end
  43.  
  44. module Generic = struct
  45.   let meta ~next ~finish ~do_leaf ~do_node =
  46.     let rec aux state =
  47.       let continue, state = next state in
  48.       if continue then
  49.         if Random.bool () then aux (do_leaf state)
  50.         else aux (do_node state)
  51.       else
  52.         finish state
  53.     in
  54.     aux
  55.  
  56.   let size : unit -> int =
  57.     let next (s, n) = (n <> 0), (s, n - 1) in
  58.     let do_leaf (s, n) = s, n in
  59.     let do_node (s, n) = s + 1, n + 2 in
  60.     let finish (s, _) = s in
  61.     fun () -> meta ~next ~finish ~do_leaf ~do_node (0, 1)
  62.  
  63.   let gen : unit -> Tree.t =
  64.     let rec next (trees, instrs) = match instrs with
  65.       | [] -> false, (trees, [])
  66.       | Gen :: instrs -> true, (trees, instrs)
  67.       | Build :: instrs ->
  68.         let l, r, trees = pop2 trees in
  69.         next (Tree.Node (l, r) :: trees, instrs)
  70.     in
  71.     let do_leaf (trees, instrs) = Tree.Leaf :: trees, instrs in
  72.     let do_node (trees, instrs) = trees, Gen :: Gen :: Build :: instrs in
  73.     let finish (trees, _) = List.hd trees in
  74.     fun () -> meta ~next ~finish ~do_leaf ~do_node ([], [Gen])
  75. end
  76.  
  77. let test ~name (module B: Boltz) =
  78.   Format.printf " ---- %s ---- @." name;
  79.   Random.init 4242424242;
  80.   for _ = 0 to 20 do
  81.     let rand_state = Random.get_state () in
  82.     Format.printf "=> %d / @?" (B.size ());
  83.     Random.set_state rand_state;
  84.     let tree = B.gen () in
  85.     Format.printf "%d@." (Tree.size tree)
  86.   done
  87.  
  88. let () =
  89.   test ~name:"Specialised" (module Specialised);
  90.   test ~name:"Generic" (module Generic);
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top