recursion - Modifying tuples after counting a tree in SML -

i have question i'm working on, have traverse tree once , count how many children each node has.

there 2 parts this, datatype, , function itself.

---

datatype

the datatype requires internal nodes store value of type , have anywhere 1-3 children. leaves store either real number or string list.

datatype leaf = slist of string list | real of real; datatype tree = empty               | leaf of leaf               | node of leaf * 'a tree               | node of leaf * 'a tree * 'a tree               | node of leaf * 'a tree * 'a tree * 'a tree 

---

function

next, have define function takes tree, , returns tuple (n1, n2, n3), n1 number of nodes having 1 child, n2 number of nodes 2 children, n3 number of nodes 3 children.

fun mychildren (t:'a tree) = childhelper (t, (0,0,0));   fun childhelper (t: 'a tree, (n1, n2, n3):int*int*int) =   case t of     empty => 0     | node (x) => childrenhelper(t, (n1 + 1, n2, n3))     | node (x, y) => childrenhelper(t, (n1 + 1, n2 + 1, n3))     | node (x, y, z) => childrenhelper(t, (n1 + 1, n2 + 1, n3 + 1)); 

---

i'm starting use datatypes , cases, it's confusing me. wondering, datatypes best way represent tree? , how make function recursively go through tree? stands, counts first node of tree instead of of it. i'm leaving off case it's leaf, since @ point don't need anything.

i know in list, can hd::tl, there way can on tree that, having gone through node, call function on each node?

for example, node (x, y, z), should call childrenhelper on each node, @ same time, maintain number on tuples. ideas on how go forward this?

first off, cannot have datatype multiple constructors named same. 1 inevitably shadow on other. run code, you'd warning similar to:

! datatype tree = empty !               | leaf of leaf !               | node of leaf * 'a tree !               | node of leaf * 'a tree * 'a tree !               | node of leaf * 'a tree * 'a tree * 'a tree ! unguarded type variables @ top-level 

this because definition uses type parameter 'a isn't declared part of tree type. changing datatype 'a tree = ..., instead error:

!                  | node of leaf * 'a tree * 'a tree !                    ^^^^ ! illegal constructor specification: constructor cannot specified twice same datatype 

what can instead have 3 different constructors, e.g.

datatype 'a tree = empty                  | node0 of leaf                  | node1 of leaf * 'a tree                  | node2 of leaf * 'a tree * 'a tree                  | node3 of leaf * 'a tree * 'a tree * 'a tree 

are datatypes best way represent tree?

yes, datatype fine.

how make function recursively go through tree?

you can go through tree in different ways. see tree traversal , folding tree.

in list, can hd::tl, there way can on tree that, having gone through node, call function on each node?

you create paramorphic function alike fold, parameterised function takes full node , not element in node argument:

fun para f e t =    let val e1 = f (e, t)    in  case t of             empty                 => e1           | node0 x                => e1           | node1 (x, t1)         => para f e1 t1           | node2 (x, t1, t2)     => para f (para f e1 t1) t2           | node3 (x, t1, t2, t3) => para f (para f (para f e1 t1) t2) t3    end 

counting number of nodes 1, 2 , 3 subtrees specialization of function:

fun nodecount t =     let fun helper ((one, two, three), t) =             case t of                  empty   => e1                | node0 _  => (one, two, three)                | node1 _ => (one+1, two, three)                | node2 _ => (one, two+1, three)                | node3 _ => (one, two, three+1)     in para helper (0,0,0) t end 

---

edit: yes, datatype above in fact redundant, since tree 1 leaf x written as:

val one_leaf = node0 (x) val one_leaf = node1 (x, empty) val one_leaf = node2 (x, empty, empty) val one_leaf = node3 (x, empty, empty, empty) 

if remove empty, redundancy goes away, can no longer represent empty trees. simple way overcome using 2 types:

datatype 'a tree = empty | nonempty of 'a tree_aux , 'a tree_aux = node0 of leaf                 | node1 of leaf * 'a tree_aux                 | node2 of leaf * 'a tree_aux * 'a tree_aux                 | node3 of leaf * 'a tree_aux * 'a tree_aux * 'a tree_aux  

or if prefer fewer constructors , type composed of pre-existing ones:

datatype leaf = slist of string list | real of real; datatype 'a tree = empty | nonempty of 'a tree_aux , 'a tree_aux = node of leaf * ('a tree_aux * ('a tree_aux * 'a tree_aux option) option) option 

but bothersome.