^CSE3322/2006/exam^

# Q7

We covered the topic of [structures, signatures and functors] in ML7, [Wednesday 9 August 2006].

NB. Function `toList' can be even simpler(!) for lists than what is given below; the version below is simply to emphasise that the same pattern of use of `next' and `advance' works for lists and for trees (and in fact for any traversable type).

```signature Traversable = sig
type elementType;
type ds;
type state;
val initialise : ds -> state;             (* state 0 *)
val next       : state -> elementType option;
val advance    : state -> state
val toList     : ds -> elementType list
end;

(* --------------------------------------------------- *)
functor TravList( type et ) :Traversable = struct
type elementType = et;
type ds = et list;
type state = et list;
fun initialise v = v;
fun next   []   = NONE
| next (x::_) = SOME x
fun toList v =      (* trivial for the case of lists *)
let fun scan s =
case next s of NONE   => []
| SOME x => x::(scan(advance s))
in scan(initialise v)
end
end;

structure TList = TravList( type et = char );
(* e.g. *) TList.toList (explode "abcd");

datatype 't sbTree = leaf of 't   (* strict binary trees *)
| fork of 't*('t sbTree)*('t sbTree)

functor Trav_sbTree( type et ) :Traversable = struct
type elementType = et;
type ds = et sbTree;
type state = et sbTree list;
fun initialise t = [t];
fun next []                 = NONE
| next ((fork(e,l,r))::_) = SOME e
| next ((leaf e)     ::_) = SOME e ;
fun advance ((fork(e,l,r))::s') = s' @ [l, r]
| advance (((leaf e))   ::s') = s' ;
fun toList v =             (* in breadth-first order *)
let fun scan s =
case next s of NONE   => []
| SOME x => x :: (scan(advance s))
in scan(initialise v)
end
end;

structure TTree = Trav_sbTree( type et = int );
(* e.g. *) TTree.toList (fork(1,(fork(2,leaf 3, leaf 4)),
(leaf 5)))

(* Structures, signatures, functors  LA, CSSE, Monash 23/6/2005 *)
```

Created with "vi (Linux & Solaris)",   charset=iso-8859-1