We covered the topic of
[structures, signatures and functors]
in ML7,
[Wednesday
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 *)