- datatype 'a btree = emptyTree | node of 'a * 'a btree * 'a btree;
> New type names: =btree
  datatype 'a btree =
  ('a btree,
   {con 'a emptyTree : 'a btree,
    con 'a node : 'a * 'a btree * 'a btree -> 'a btree})
  con 'a emptyTree = emptyTree : 'a btree
  con 'a node = fn : 'a * 'a btree * 'a btree -> 'a btree

- fun preOrder    emptyTree    = nil 
 |  preOrder (node (r, sx, dx)) = r::(append (preOrder sx) (preOrder dx));
> val 'a preOrder = fn : 'a btree -> 'a list

- fun inOrder     emptyTree   = nil
 |  inOrder (node (r, sx, dx)) = append (inOrder sx) (r::(inOrder dx));
> val 'a inOrder = fn : 'a btree -> 'a list

- fun postOrder     emptyTree   = nil
 |  postOrder (node (r, sx, dx)) = append (postOrder sx) (append (postOrder dx) [r]);
> val 'a postOrder = fn : 'a btree -> 'a list

> val 'a vlAux = fn : 'a btree list -> 'a list
- fun vlAux nil = nil
 |  vlAux (emptyTree::t) = vlAux t
 |  vlAux (node(r,sx,dx)::t) = r::(vlAux (append t [sx,dx]));
> val 'a vlAux = fn : 'a btree list -> 'a list

- fun visitaLivelli t = vlAux [t];
> val 'a visitaLivelli = fn : 'a btree -> 'a list


#  Scriviamo il seguente albero: (* per l'albero vuoto)
#  scritto in orizzontale ... 1 e' la radice 2 e 4 i suoi figli...
#    2
#       3
#  1
#       5
#         6
#    4
   
- val t = node(1,
              node(2, emptyTree, node(3, emptyTree, emptyTree)),
              node(4, node(5, emptyTree, node(6, emptyTree, emptyTree)), 
									emptyTree));
> val t =
    node(1, node(2, emptyTree, node(3, emptyTree, emptyTree)),
         node(4, node(5, emptyTree, node(6, emptyTree, emptyTree)), emptyTree))
     : int btree

- preOrder t;
> val it = [1, 2, 3, 4, 5, 6] : int list

- postOrder t;
> val it = [3, 2, 6, 5, 4, 1] : int list

- inOrder t;
> val it = [2, 3, 1, 5, 6, 4] : int list

- visitaLivelli t;
> val it = [1, 2, 4, 3, 5, 6] : int list

# i pattern DEVONO essere lineari
- fun eq (x, x) = true
   |  eq (x, y) = false;
! Toplevel input:
! fun eq (x, x) = true
!            ^
! Illegal rebinding of x: the same value identifier is bound twice in a pattern

- fun eqtree emptyTree emptyTree = true
   |  eqtree emptyTree _ = false
   |  eqtree _ emptyTree = false
   |  eqtree (node(r1, s1, d1)) (node(r2, s2, d2)) = 
          if r1=r2 then if (eqtree s1 s2) 
                           then (eqtree d1 d2)
                           else false
                   else false;
> val ''a eqtree = fn : ''a btree -> ''a btree -> bool

- fun subtree emptyTree emptyTree  = true
   |  subtree _ emptyTree = false
   |  subtree t1 (t2 as node(r, s, d)) = 
         if (eqtree t1 t2) then true
                           else if (subtree t1 s) then true
                                                  else if (subtree t1 d) then true
                                                                         else false;   
> val ''a subtree = fn : ''a btree -> ''a btree -> bool

# gli alberi n-ari possono essere definiti per mutua induzione:
- datatype 'a ntree = nt of 'a * 'a forest 
    and 'a forest = ef | mkf of 'a ntree * 'a forest;
> New type names: =forest, =ntree
  datatype 'a ntree = ('a ntree,{con 'a nt : 'a * 'a forest -> 'a ntree})
  datatype 'a forest =
  ('a forest,
   {con 'a ef : 'a forest, con 'a mkf : 'a ntree * 'a forest -> 'a forest})
  con 'a nt = fn : 'a * 'a forest -> 'a ntree
  con 'a ef = ef : 'a forest
  con 'a mkf = fn : 'a ntree * 'a forest -> 'a forest

# la mutua ricorsione sui dati si trasforma in mutua ricorsione sulle procedure...
- fun preOrderF ef = []
   |  preOrderF (mkf(t, f)) = append (preOrderT t) (preOrderF f)
  and preOrderT (nt(r, f)) = r::(preOrderF(f));
> val 'a preOrderF = fn : 'a forest -> 'a list
  val 'a preOrderT = fn : 'a ntree -> 'a list

# un albero n-ario si puo' anche "rappresentare" con un albero binario, a patto di
# leggerlo opportunamente: ad esempio convenendo che l'albero sinistro rappresenti i
# figli e l'albero destro i fratelli....
# osservate che translateTree non restituisce mai alberi vuoti...
fun translateForest ef = emptyTree
 |  translateForest (mkf(t,f)) = 
           let val node(r, d, s)= translateTree t
               in node(r, d, (translateForest f))
           end
and translateTree (nt(n,f)) = node(n, (translateForest f), emptyTree);
! Toplevel input:
!            let val node(r, d, s)= translateTree t
!                    ^^^^^^^^^^^^^
! Warning: pattern matching is not exhaustive

> val 'a translateForest = fn : 'a forest -> 'a btree
  val 'a translateTree = fn : 'a ntree -> 'a btree

# possiamo anche scrivere l'inversa...
fun translateBTree emptyTree = ef
 |  translateBTree (node (r, s, d)) = mkf(nt (r, translateBTree s), translateBTree d);
> val 'a translateBTree = fn : 'a btree -> 'a forest

# l'output e' quello che e'...
- translateBTree t;
> val it =
    mkf(nt(1, mkf(nt(2, ef), mkf(nt(3, ef), ef))),
        mkf(nt(4, mkf(nt(5, ef), mkf(nt(6, ef), ef))), ef)) : int forest

- preOrderF (translateBTree t);
> val it = [1, 2, 3, 4, 5, 6] : int list

# ma la matematica ci aiuta a verificare che le nostre funzioni funzionano...
- eqtree (translateForest (translateBTree t)) t;
> val it = true : bool


# un tipo di dato interessante: la somma NON coalescente
# un elemento di questo tipo o e' un elemento di tipo 'a o di tipo 'b...
- datatype ('a, 'b) union = inl of 'a | inr of 'b;
> New type names: =union
  datatype ('a, 'b) union =
  (('a, 'b) union,
   {con ('a, 'b) inl : 'a -> ('a, 'b) union,
    con ('a, 'b) inr : 'b -> ('a, 'b) union})
  con ('a, 'b) inl = fn : 'a -> ('a, 'b) union
  con ('a, 'b) inr = fn : 'b -> ('a, 'b) union

- datatype 'a bctree = leaf of 'a | cnode of 'a * 'a bctree * 'a bctree;
> New type names: =bctree
  datatype 'a bctree =
  ('a bctree,
   {con 'a cnode : 'a * 'a bctree * 'a bctree -> 'a bctree,
    con 'a leaf : 'a -> 'a bctree})
  con 'a cnode = fn : 'a * 'a bctree * 'a bctree -> 'a bctree
  con 'a leaf = fn : 'a -> 'a bctree

- datatype operazioni = P | M | S | D;
> New type names: =operazioni
  datatype operazioni =
  (operazioni,
   {con D : operazioni,
    con M : operazioni,
    con P : operazioni,
    con S : operazioni})
  con D = D : operazioni
  con M = M : operazioni
  con P = P : operazioni
  con S = S : operazioni

- exception error;
> exn error = error : exn

- type espressione = ((operazioni, int) union) bctree;
> type espressione = (operazioni, int) union bctree

- fun esegui P x y = x+y
   |  esegui S x y = x-y
   |  esegui M x y = x*y
   |  esegui D x y = x div y;
> val esegui = fn : operazioni -> int -> int -> int


fun valuta (leaf(inr(n)):espressione) = n
   |  valuta (leaf(inl(_))) = raise error
   |  valuta (cnode(inr(_), _,_)) = raise error
   |  valuta (cnode(inl(a), left, right)) = esegui a (valuta(left)) (valuta(right));
> val valuta = fn : (operazioni, int) union bctree -> int

# ok la sintassi delle espressioni come albero non e' il massimo...
- val expr = cnode(inl(P), leaf(inr(3)), cnode(inl(M), leaf(inr(2)), leaf(inr(3))));
> val expr = cnode(inl P, leaf(inr 3), cnode(inl M, leaf(inr 2), leaf(inr 3)))
     : (operazioni, int) union bctree

- valuta expr;
> val it = 9 : int