Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Use of effects and handlers to compute the tree representation of a functional.
(** This code is compatible with Eff 5.0, see http://www.eff-lang.org *)
(** We show that with algebraic effects and handlers a total functional
[(int -> bool) -> bool] has a tree representation. *)
(* A tree representation of a functional. *)
type tree =
| Answer of bool
| Question of int * tree * tree
(** An effect that we will use to report how the functional is using its argument. *)
effect Report : int -> bool
(** Convert a tree to a functional. *)
let rec tree2fun t a =
match t with
| Answer y -> y
| Question (x, t1, t2) -> tree2fun (if a x then t1 else t2) a
(** Convert a functional to a tree. *)
let rec fun2tree h =
handle
Answer (h (fun x -> perform (Report x)))
with
| effect (Report x) k -> Question (x, continue k false, continue k true)
let example1 = fun2tree (fun a -> true)
let example2 = fun2tree (fun a -> a 10; true)
let example3 = fun2tree (fun a -> if a 10 then (a 30 || a 15) else (a 20 && not (a 8)))
(* This one is pretty large, so take care *)
(*
let example4 =
(* convert a string of booleans to an int *)
let rec to_int = function
| [] -> 0
| b :: bs -> (if b then 1 else 0) + 2 * to_int bs
in
fun2tree (fun a -> a (to_int [a 0; a 1; a 2; a 3; a 4; a 5; a 6; a 7; a 8]))
*)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.