Ocaml:

module type TreeSignature = sig (** The type of binary trees. *) type 'a t = Leaf | Node of 'a * 'a t * 'a t (** [empty] is [Leaf]. *) val empty : 'a t (** Document your [singleton] here *) val singleton : 'a -> 'a t (** [size t] returns the size of [t] (leaves don't count for this lab). *) val size : 'a t -> int (** Document your [leftmost] here *) val leftmost : 'a t -> 'a option (** Document your [rightmost] here *) val rightmost : 'a t -> 'a option (** [reverse t] flips the tree [t] horizontally. (This is [flip] but renamed for this lab.) *) val reverse : 'a t -> 'a t (** Document your [map] here *) val map : ('a -> 'b) -> 'a t -> 'b t end (* Define a module [Tree] of type [TreeSignature] Put the top-level comments about the interface (public-facing comments) in the module type (signature), not in the module (structure). *) module type ListSignature = sig (** Document it *) type 'a t = 'a list (** Document it *) val empty : 'a t (** Document it *) val singleton : 'a -> 'a t (** Document it *) val size : 'a t -> int (** Document it *) val leftmost : 'a t -> 'a option (** Document it *) val rightmost : 'a t -> 'a option (** Document it *) val reverse : 'a t -> 'a t (** Document it *) val map : ('a -> 'b) -> 'a t -> 'b t end

(* Define a module [MyList] of type [ListSignature] You should use functions in [List] only if you know how to define them. [reverse] is challenging, but I wrote a version of it using fold_left during one of the lectures. Again, put the public-facing top-level comments in the module type (signature), not in the module (structure). *) module type Sequence = sig (** The abstract type of sequences. *) type 'a t (** [empty] is an empty sequence. *) val empty : 'a t (* Fill out the content of [Sequence] such that 1. All value definitions ([empty], [map], etc.) are still visible. 2. It is properly documented; that is, you should not refer to trees or lists because you would not even know what the underlying implementation is. 3. The following two lines should type check: {[ module SealedTree = (Tree : Sequence) module SealedList = (MyList : Sequence) ]} *) end