ListsAndTrees2.sml

(* 1 *)

fun propercuts (x::xs) =
      let fun propcut (y::ys) ac = (rev (ac), y::ys) :: (propcut ys (y::ac))
            | propcut [] _ = []
      in propcut xs [x]
      end
  | propercuts _ = [];


(* 2 *)

datatype 'a tree = leaf of 'a | node of 'a tree * 'a tree ;
datatype 'a symbol = Lbracket | Rbracket | token of 'a ;

fun rep (leaf x) = [token x]
  | rep (node(l,r)) = [Lbracket] @ (rep l) @ (rep r) @ [Rbracket];

fun istree [token x] = true
  | istree (Lbracket::totest) =
      let fun any2 pr ((x1,x2)::xs) = (pr x1 andalso pr x2) orelse any2 pr xs
            | any2 pr [] = false
          fun droplast (x::[]) = []
            | droplast (x::xs) = x::(droplast xs)
            | droplast _ = []
      in any2 istree (propercuts (droplast totest))
      end
  | istree _ = false;


val tree1 = (leaf 1);
val tree1l = rep tree1;
val tree2 = node(node(leaf 1, leaf 2), leaf 3);
val tree2l = rep tree2;
val tree3 = node(node(leaf 1, leaf 2), node(node(leaf 3, leaf 4), leaf 5));
val tree3l = rep tree3;
  (* > istree tree1l;
   * val it = true: bool
   * > istree tree2l;
   * val it = true: bool
   * > istree tree3l;
   * val it = true: bool
   *)
val nottree1l =  [Lbracket, token 1, token 2, Rbracket, token 3, Rbracket];
val nottree2l =  [Lbracket, Lbracket, token 2, Rbracket, token 3, Rbracket];
  (* > istree nottree1l;
   * val it = false: bool
   * > istree nottree2l;
   * val it = false: bool
   *)



(* Make a tree from the symbol list *)
exception Error;

fun maketree ((token x)::rest) = (leaf x, rest)
  | maketree (Lbracket::rest) =
      let val one = maketree rest
          val two = maketree (#2 (maketree(rest)))
      in (node(#1 one, #1 two), #2 two)
      end
  | maketree (Rbracket::rest) = maketree rest
  | maketree _ = raise Error;  (* For Match Exhaustion *)

 (* > tree3;
  * val it = node (node (leaf 1, leaf 2), node (node (leaf 3, leaf 4), leaf 5)):int tree
  * > rep tree3;
  * val it = [Lbracket, Lbracket, token 1, token 2, Rbracket, Lbracket, Lbracket,
  *           token 3, token 4, Rbracket, ...]: int symbol list
  * > #1 (maketree (rep tree3));
  * val it = node (node (leaf 1, leaf 2), node (node (leaf 3, leaf 4), leaf 5)):int tree
  *)