structure Generated =
struct

datatype 'a tree = Node of 'a * 'a tree list;

fun Let s f = f s;

fun split x = (fn p => x (fst p) (snd p));

fun op__64 [] ys = ys
  | op__64 (x :: xs) ys = (x :: op__64 xs ys);

datatype 'a option = None | Some of 'a;

fun if_none None y = y
  | if_none (Some x) y = x;

fun assoc [] key = None
  | assoc (x :: xs) key =
    (if (fst x = key) then Some (snd x) else assoc xs key);

fun succs g x = if_none (assoc g x) [];

fun op_mem x [] = false
  | op_mem x (y :: ys) = (if (y = x) then true else op_mem x ys);

fun remdups_mem [] = []
  | remdups_mem (x :: xs) =
    (if op_mem x xs then remdups_mem xs else (x :: remdups_mem xs));

fun remdups xs = remdups_mem xs;

fun flatten [] = []
  | flatten (x :: xs) = op__64 x (flatten xs);

fun map f [] = []
  | map f (x :: xs) = (f x :: map f xs);

fun vertices g = remdups (op__64 (map fst g) (flatten (map snd g)));

fun dfsm ((g, ms), []) = ([], ms)
  | dfsm ((g, ms), (x :: xs)) =
    (if not (op_mem x (vertices g)) then ([], ms)
      else (if op_mem x ms then dfsm ((g, ms), xs)
             else Let (dfsm ((g, (x :: ms)), succs g x))
                    (split
                      (fn tsx => fn msx =>
                        Let (dfsm ((g, op__64 msx (x :: ms)), xs))
                          (split
                            (fn tsxs => fn msxs =>
                              ((Node (x, tsx) :: tsxs), msxs)))))));

fun dfs g = fst (dfsm ((g, []), vertices g));

val dfs = dfs;

end;

open Generated;