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 advance (_::s) = s
  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 *)