kyleheadley/functor.rs

## functor.rs
//! This file is a translation of the example code in the OCaml manual
//! chapter two,"The module system", into Rust code.
//!
//! The intent is to translate as directly as possible, to show OCaml
//! users a way to implement their functionality. This means that
//! later, more complex sections are neither idiomatic Rust nor a
//! perfect translation of the OCaml. Further study would be required,
//! but hopefully this helps explain some of the concepts.
//!
//! There are two constructs in Rust that might match OCaml modules,
//! namespaces (called "modules" in Rust) and implementations of types
//! and traits. Rust modules are concrete code blocks and generally
//! distinguish files from one another in a project (called a "crate"
//! in Rust). Types may have functions "implemented" on them, and may
//! also be polymorphic in a type variable. Traits function as
//! interfaces to types, allowing greater flexibility with their own
//! type variables and associated types. Traits must be implemented
//! for types, providing the code and optionally some type variables.
//!
//! Rust is actually capable of more abstraction than was used in
//! these examples. Traits, which correspond to OCaml signatures, may
//! themselves be parametrized. Trait parameterizations are best used
//! for behavior abstractions, while type parameterizations are for
//! data abstractions. This separation is an important feature of the
//! user-defined type system in Rust. Using a parametrized trait, Rust
//! code may emulate type functions (rather than the type constructors
//! use below). This is demonstrated below. The syntax is terrible, but
//! the use is pretty straight-forward.
//!
//! All the abstractions used below are _static_, or handled at
//! compile-time. This is preferred in Rust where possible, because it
//! makes for faster code. Dynamic dispatch is available, by binding
//! or taking as a parameter a variable with a trait as its type.
//! Theses are called "trait objects" and usually "boxed", or after a
//! pointer. More complex use of OCaml modules would require trait
//! objects to handle the run-time variability.
//!
//! Rust code cannot have static visibility (OCaml's concrete vs
//! abstract types within modules) changed at run-time. At compile-time,
//! traits with different visibility could be defined, but conversion
//! would be difficult if even possible.
//!
//! The first section of the manual introduces modules without
//! abstraction. Rust modules are sufficient for this use, and
//! demonstrated in the translation. The rest of the manual deals with
//! signatures and functors, which require types and traits.
//!
//! Most of the code can be translated line-for-line, but there are a
//! few major differences between the languages. Rust makes pointers
//! and data copying explicit, so references, dereferences and calls to
//! `clone()` appear in the Rust code. Rust also lacks exceptions,
//! so code returns the sum type `Result<SuccessType,FailureType>`.

/// allows `<A:OCaml>` rather than <A:Clone+PartialEq+Eq>`
pub trait OCaml : Clone + PartialEq + Eq {}
impl<A:Clone+PartialEq+Eq> OCaml for A {}

/// Compile-time example from the OCaml manual 2.1
///
/// "A primary motivation for modules is to package together related definitions..."
/// ```ocaml
/// module PrioQueue =
///   struct
///     type priority = int
///     type 'a queue = Empty | Node of priority * 'a * 'a queue * 'a queue
///     let empty = Empty
///     let rec insert queue prio elt =
///       match queue with
///         Empty -> Node(prio, elt, Empty, Empty)
///       | Node(p, e, left, right) ->
///           if prio <= p
///           then Node(prio, elt, insert right p e, left)
///           else Node(p, e, insert right prio elt, left)
///     exception Queue_is_empty
///     let rec remove_top = function
///         Empty -> raise Queue_is_empty
///       | Node(prio, elt, left, Empty) -> left
///       | Node(prio, elt, Empty, right) -> right
///       | Node(prio, elt, (Node(lprio, lelt, _, _) as left),
///                         (Node(rprio, relt, _, _) as right)) ->
///           if lprio <= rprio
///           then Node(lprio, lelt, remove_top left, right)
///           else Node(rprio, relt, left, remove_top right)
///     let extract = function
///         Empty -> raise Queue_is_empty
///       | Node(prio, elt, _, _) as queue -> (prio, elt, remove_top queue)
///   end;;
/// ```
pub mod prio_queue {
  // modules do not have full access to outer scope by default
  use super::OCaml;
  // needed for shared data structures
  use std::rc::Rc;
  // avoids explicit scoping, contrary to idiomatic Rust
  use self::Queue::*;

  pub type Priority = i32;
  #[derive(Clone, PartialEq, Eq)]
  pub enum Queue<A:OCaml> { Empty, Node(Priority,A,Rc<Queue<A>>,Rc<Queue<A>>) }
  pub fn empty<A:OCaml>() -> Queue<A> { Empty }
  pub fn insert<A:OCaml>(queue: &Queue<A>, prio: Priority, elt:&A) -> Queue<A> {
    match *queue {
      Empty => Node(prio, elt.clone(), Rc::new(Empty), Rc::new(Empty)),
      Node(p,ref e,ref left,ref right) => {
        if prio <= p {
          Node(prio, elt.clone(), Rc::new(insert(&**right, p, e)), left.clone())
        } else { Node(p, e.clone(), Rc::new(insert(&**right, prio, elt)), left.clone()) }
      }
    }
  }
  #[derive(Debug)]
  pub enum Exception { QueueIsEmpty }
  pub(super) fn remove_top<A:OCaml>(q: &Queue<A>) -> Result<Queue<A>,Exception> { match *q {
    Empty => Err(Exception::QueueIsEmpty),
    Node(_, _, ref left, ref right) if **right == Empty => Ok((**left).clone()),
    Node(_, _, ref left, ref right) if **left == Empty => Ok((**right).clone()),
    Node(_, _, ref left, ref right) => match (&**left, &**right) {
      (&Node(lprio, ref lelt, _,_),&Node(rprio, ref relt,_,_)) => {
        if lprio <= rprio {
          Ok(Node(lprio, lelt.clone(), Rc::new(remove_top(&**left)?), right.clone()))
        } else { Ok(Node(rprio, relt.clone(), left.clone(), Rc::new(remove_top(&**right)?))) }
      } _ => unreachable!() //needed inner `match` to handle patterns into linked structure
    }
  }}
  pub fn extract<A:OCaml>(q: &Queue<A>) -> Result<(Priority, A, Queue<A>),Exception> { match *q {
    Empty => Err(Exception::QueueIsEmpty),
    Node(prio, ref elt, _, _) => Ok((prio, elt.clone(), remove_top(q)?)),
  }}
}

/// Compile-time example from OCaml manual 2.1
///
/// "It is also possible to copy the components of a module inside another module..."
/// ```ocaml
/// module PrioQueueOpt =
///   struct
///     include PrioQueue
///     let remove_top_opt x =
///       try Some(remove_top x) with Queue_is_empty -> None
///     let extract_opt x =
///       try Some(extract x) with Queue_is_empty -> None
///   end;;
/// ```
pub mod prio_queue_opt {
  use super::OCaml;

  pub use prio_queue::*;
  #[allow(unused)]
  pub(super) fn remove_top_opt<A:OCaml>(q: &Queue<A>) -> Option<Queue<A>> {
    // to check the exception
    match remove_top(q) {
      Err(Exception::QueueIsEmpty) => None,
      Ok(res) => Some(res),
    }
  }
  pub fn extract_opt<A:OCaml>(q: &Queue<A>) -> Option<(Priority, A, Queue<A>)> {
    // shortcut if you don't need to check the exception
    extract(q).ok()
  }
}

/// Runtime-examples from OCaml manual 2.1
///
/// ```ocaml
/// PrioQueue.insert PrioQueue.empty 1 "hello";;
/// open PrioQueue;;
/// insert empty 1 "hello";;
///
/// let empty = []
/// open PrioQueue;;
/// let x = 1 :: empty ;;
///
/// let open PrioQueue in
/// insert empty 1 "hello";;
/// ````
///
/// This code shows off different syntax for accessing module functions.
/// It has no equivalent in Rust
/// ```ocaml
/// PrioQueue.[empty] = PrioQueue.([empty]);;
///
/// PrioQueue.[|empty|] = PrioQueue.([|empty|]);;
///
/// PrioQueue.{ contents = empty } = PrioQueue.({ contents = empty });;
///
/// PrioQueue.[insert empty 1 "hello"];;
/// ```
fn sec1() {
  // this is altered to show that `prio_queue_opt` contains the items
  // from `prio_queue`, and that the two are compatible
  prio_queue_opt::insert(&prio_queue::empty(), 1, &"hello".to_string());
  use prio_queue::*;
  insert(&empty(),1,&"hello".to_string());

  // this function causes an error in the
  // _previous_ line, but not the next!
  // fn empty() -> () { () }

  {
    use prio_queue::*;
    insert(&empty(),1,&"hello".to_string());
  }
}

/// Compile-time example from OCaml manual 2.2
///
/// ```ocaml
/// module type PRIOQUEUE =
///     sig
///       type priority = int         (* still concrete *)
///       type 'a queue               (* now abstract *)
///       val empty : 'a queue
///       val insert : 'a queue -> int -> 'a -> 'a queue
///       val extract : 'a queue -> int * 'a * 'a queue
///       exception Queue_is_empty
///     end;;
/// ```
pub trait PrioQueueSig where Self:Sized {
  // Concrete types cannot be defined here, use an external definition
  // for types Priority and Exception

  // In Rust we have a self type, which can naturally assume the role
  // of the OCaml `'a queue` (or more generally, Module.t). That
  // leaves us with just the `'a` needing a definition.
  type A : OCaml;
  fn empty() -> Self;
  fn insert(&self, Priority, &Self::A) -> Self;
  fn extract(&self) -> Result<(Priority, Self::A, Self),Exception>;
}

// The following are implementations for using a Rust type like an OCaml
// module. Normally, the code above would be here, but it's all correctly
// typed so we can just call back to it.
pub type Priority = prio_queue::Priority;
pub type Exception = prio_queue::Exception;
pub type PrioQueue<A> = prio_queue::Queue<A>;
impl<A:OCaml> PrioQueueSig for PrioQueue<A> {
  type A = A;
  fn empty() -> Self { prio_queue::empty() }
  fn insert(&self, p: Priority, elt: &A) -> Self {
    prio_queue::insert(&self, p, elt)
  }
  fn extract(&self) -> Result<(Priority, Self::A, Self),Exception> {
    prio_queue::extract(&self)
  }
}
// This is not part of the sig, but part of the original
impl <A:OCaml> PrioQueue<A> {
  pub fn remove_top(&self) -> Result<Self,Exception> {
    prio_queue::remove_top(&self)
  }
}

/// Run-time examples from OCaml manual 2.2
///
/// ```ocaml
/// module AbstractPrioQueue = (PrioQueue : PRIOQUEUE);;
/// AbstractPrioQueue.remove_top ;;
/// AbstractPrioQueue.insert AbstractPrioQueue.empty 1 "hello";;
/// ```
///
/// This section is a bit different in Rust, because visibility cannot
/// be adjusted in this way. You can reduce visibility within a function
/// that takes the type (analog to OCaml module) as a parameter. However,
/// this reduces the visibility to the compiler as well, so it cannot
/// use the concrete type, even if it's passed to the function. This
/// issue is present in OCaml in other situations and will be demonstrated
/// in a later section.
///
/// Finally, the trait (analog to OCaml sig) can be used directly as if
/// it were an abstract type, but Rust's type inference is not able to
/// handle this situation without a type annotation, since it's the
/// compiler that chooses the implementation.
fn sec2() {
  #[allow(path_statements)] // supress warning generated in body
  fn reduce_visibility<AbstractPrioQueue:PrioQueueSig>() {
    // error: function not found
    // AbstractPrioQueue::remove_top;

    // warning: no effect
    AbstractPrioQueue::insert;

    // types don't match because of abstraction, solution in later section
    // AbstractPrioQueue::insert(&AbstractPrioQueue::empty(), 1, &"hello".to_string());
  }
  reduce_visibility::<PrioQueue<String>>();

  // Rust requires an annotation here
  let _:PrioQueue<String> = PrioQueueSig::insert(&PrioQueueSig::empty(),1,&"hello".to_string());
}

/// Compile-time example from OCaml manual 2.2
///
/// ```ocaml
/// module type PRIOQUEUE_WITH_OPT =
///   sig
///     include PRIOQUEUE
///     val extract_opt : 'a queue -> (int * 'a * 'a queue) option
///   end;;
/// ```
trait PrioQueueSiGWithOpt : PrioQueueSig {
  fn extract_opt(&self) -> Option<(Priority,Self::A,Self)>;
}
impl<A:OCaml> PrioQueueSiGWithOpt for PrioQueue<A> {
  fn extract_opt(&self) -> Option<(Priority,Self::A,Self)>{
    prio_queue_opt::extract_opt(&self)
  }
}

/// Compile-time example from OCaml manual 2.3
///
/// ```ocaml
/// type comparison = Less | Equal | Greater;;
/// module type ORDERED_TYPE =
///   sig
///     type t
///     val compare: t -> t -> comparison
///   end;;
/// module Set =
///   functor (Elt: ORDERED_TYPE) ->
///     struct
///       type element = Elt.t
///       type set = element list
///       let empty = []
///       let rec add x s =
///         match s with
///           [] -> [x]
///         | hd::tl ->
///            match Elt.compare x hd with
///              Equal   -> s         (* x is already in s *)
///            | Less    -> x :: s    (* x is smaller than all elements of s *)
///            | Greater -> hd :: add x tl
///       let rec member x s =
///         match s with
///           [] -> false
///         | hd::tl ->
///             match Elt.compare x hd with
///               Equal   -> true     (* x belongs to s *)
///             | Less    -> false    (* x is smaller than all elements of s *)
///             | Greater -> member x tl
///     end;;
/// module OrderedString =
///   struct
///     type t = string
///     let compare x y = if x = y then Equal else if x < y then Less else Greater
///   end;;
/// ```
pub mod ordered_type {
  use std::rc::Rc;
  use super::OCaml;

  pub enum Comparison { Less, Equal, Greater }
  /// The property of a type with an inherent order
  pub trait OrderedType {
    fn compare(&self, other:&Self) -> Comparison;
  }
  /// Rust lacks cons-lists, they're not efficent and they're easily defined
  #[derive(Clone,PartialEq,Eq)]
  pub enum Set<A> { Nil, Cons(A,Rc<Set<A>>) }

  impl<Elt:OCaml+OrderedType> Set<Elt> {
    pub fn empty() -> Self { Set::Nil }
    pub fn add(&self, x:Elt) -> Self {
      match self {
        &Set::Nil => Set::Cons(x,Rc::new(Set::Nil)),
        &Set::Cons(ref hd,ref tl) => {
          match Elt::compare(&x,hd) {
            Comparison::Equal => self.clone(),
            Comparison::Less => Set::Cons(x,Rc::new(self.clone())),
            Comparison::Greater => Set::Cons(hd.clone(), Rc::new(tl.add(x))),
          }
        }
      }
    }
    pub fn member(&self, x:&Elt) -> bool {
      match self {
        &Set::Nil => false,
        &Set::Cons(ref hd,ref tl) => {
          match Elt::compare(x,hd) {
            Comparison::Equal => true,
            Comparison::Less => false,
            Comparison::Greater => tl.member(x)
          }
        }
      }
    }
  }
  impl OrderedType for String {
    fn compare(&self, other:&Self) -> Comparison {
      if self == other { Comparison::Equal }
      else if self < other { Comparison::Less }
      else { Comparison::Greater }
    }
  }
}

/// Run-time example from OCaml manual 2.3
///
/// ```ocaml
/// module StringSet = Set(OrderedString);;
/// StringSet.member "bar" (StringSet.add "foo" StringSet.empty);;
/// ```
fn sec3() {
  use ordered_type::*;

  // in Rust this is a simple alias, and not worth writing here
  // type StringSet = Set<String>;

  Set::empty().add("foo".to_string()).member(&"bar".to_string());
}


/// Compile-time examples from OCaml manual 2.4
///
/// ```ocaml
/// module type SETFUNCTOR =
///   functor (Elt: ORDERED_TYPE) ->
///     sig
///       type element = Elt.t      (* concrete *)
///       type set                  (* abstract *)
///       val empty : set
///       val add : element -> set -> set
///       val member : element -> set -> bool
///     end;;
///
/// module type SET =
///   sig
///     type element
///     type set
///     val empty : set
///     val add : element -> set -> set
///     val member : element -> set -> bool
///   end;;
///
/// module NoCaseString =
///   struct
///     type t = string
///     let compare s1 s2 =
///       OrderedString.compare (String.lowercase_ascii s1) (String.lowercase_ascii s2)
///   end;;
/// ```
pub mod man24 {
  use std::rc::Rc;
  use super::OCaml;
  use ordered_type::*;

  // A type may be
  // 'abstract' by keeping its internal structure private. The following
  // is a public interface to a struct with private elements. It can only be
  // constructed and deconstructed by its own methods.
  #[derive(Clone,PartialEq,Eq)]
  pub struct AbstractOrderedSet<A:Ordering> { set: Set<A::Type> }

  // To allow multiple combinations of type and order, we can create a more
  // general trait that more closely matches the OCaml version. We also require
  // that the implementing type is clonable.
  pub trait Ordering : Clone {
    type Type: OCaml + OrderedType;
    fn compare(one: &Self::Type, two: &Self::Type) -> Comparison;
  }

  // impl mostly copied from above, but with `Elt` changed to `Order` or
  // `Order::Type` as appropriate and using our new defn of AbstractOrderedSet
  impl<Order:Ordering> AbstractOrderedSet<Order> {
    pub fn empty() -> Self { AbstractOrderedSet{set: Set::Nil} }
    pub fn add(&self, x:Order::Type) -> Self {
      match self.set {
        Set::Nil => AbstractOrderedSet{set:Set::Cons(x,Rc::new(Set::Nil))},
        Set::Cons(ref hd,ref tl) => {
          match Order::compare(&x,hd) {
            Comparison::Equal => (*self).clone(),
            Comparison::Less => AbstractOrderedSet{set:Set::Cons(x,Rc::new(self.set.clone()))},
            Comparison::Greater => AbstractOrderedSet{set:Set::Cons(hd.clone(), Rc::new(tl.add(x)))},
          }
        }
      }
    }
    pub fn member(&self, x:&Order::Type) -> bool {
      match self.set {
        Set::Nil => false,
        Set::Cons(ref hd,ref tl) => {
          match Order::compare(x,hd) {
            Comparison::Equal => true,
            Comparison::Less => false,
            Comparison::Greater => tl.member(x)
          }
        }
      }
    }
  }

  // helper for types that have an inherent order as defined previously. This is
  // to be used as a 'marker type' and we won't ever use the value consructor.
  // This is a blanket implemetation, all types with a order defined may now be used
  // with our new abstract `Set` by e.g. `AbstractOrderedSet<DefaultOrdering<String>>`
  #[derive(Clone,PartialEq,Eq)]
  pub struct DefaultOrdering<A>(A);
  impl<A:OCaml+OrderedType> Ordering for DefaultOrdering<A> {
    type Type = A;
    fn compare(one: &Self::Type, two: &Self::Type) -> Comparison {
      A::compare(one, two)
    }
  }

  // new string ordering
  #[derive(Clone,PartialEq,Eq)]
  pub struct NoCaseString;
  impl Ordering for NoCaseString {
    type Type = String;
    fn compare(one: &Self::Type, two: &Self::Type) -> Comparison {
      String::compare(&one.to_lowercase(),&two.to_lowercase())
    }
  }

  // As seen above, Rust does not have the same semantics of
  // abstract interfaces as OCaml. However, there is still the
  // problem of matching two of them up, and Rust has its own
  // `with` clause, `where`:
  #[derive(Clone,PartialEq,Eq)]
  pub struct DoubleOrder<A,B>(A,B);
  impl<A:Ordering,B:Ordering,C:OCaml+OrderedType> DoubleOrder<A,B> where
    A:Ordering<Type=C>,
    B:Ordering<Type=C>
  {
    // without the where clause above, these are different types.
    pub fn compare(a:&A::Type,b:&B::Type) -> Comparison {
      A::compare(a,b)
    }
  }

  // A type function for the AbstractOrderedSet constructor, using the
  // associated type of a parametrized trait
  trait Func<In> { type Out; }
  #[allow(unused)]
  struct AOSfn;
  impl<In: Ordering> Func<In> for AOSfn { type Out = AbstractOrderedSet<In>; }
  #[allow(unused)]
  type Derived = <AOSfn as Func<NoCaseString>>::Out;
}

/// Run-time examples from OCaml manual 2.4
///
/// ```ocaml
/// module AbstractSet = (Set : SETFUNCTOR);;
/// module AbstractStringSet = AbstractSet(OrderedString);;
/// AbstractStringSet.add "gee" AbstractStringSet.empty;;
/// module WrongSet = (Set : functor(Elt: ORDERED_TYPE) -> SET);;
/// module WrongStringSet = WrongSet(OrderedString);;
/// WrongStringSet.add "gee" WrongStringSet.empty ;;
/// module AbstractSet2 = (Set : functor(Elt: ORDERED_TYPE) -> (SET with type element = Elt.t));;
/// module NoCaseStringSet = AbstractSet(NoCaseString);;
/// NoCaseStringSet.add "FOO" AbstractStringSet.empty ;;
/// ```
fn sec4() {
  use man24::*;
  // As before, visibility is not adjustable at runtime.
  // module AbstractSet = (Set : SETFUNCTOR);;

  #[allow(unused)]
  type AbstractStringSet = AbstractOrderedSet<DefaultOrdering<String>>;

  // The `WrongSet` examples would be meaningless in static Rust, because the
  // compiler does know that the types match (They're both litterally the same).
  // The demonstration of the `with` clause is unnessecary here, but a different
  // one was included above (see DoubleOrder).

  #[allow(unused)]
  type NoCaseStringSet = AbstractOrderedSet<NoCaseString>;

  // Error: two different types
  // NoCaseStringSet::add(&AbstractStringSet::empty(), "FOO".to_string());
}


fn main() {
  sec1();
  sec2();
  sec3();
  sec4();
}
	//! This file is a translation of the example code in the OCaml manual
	//! chapter two,"The module system", into Rust code.
	//!
	//! The intent is to translate as directly as possible, to show OCaml
	//! users a way to implement their functionality. This means that
	//! later, more complex sections are neither idiomatic Rust nor a
	//! perfect translation of the OCaml. Further study would be required,
	//! but hopefully this helps explain some of the concepts.
	//!
	//! There are two constructs in Rust that might match OCaml modules,
	//! namespaces (called "modules" in Rust) and implementations of types
	//! and traits. Rust modules are concrete code blocks and generally
	//! distinguish files from one another in a project (called a "crate"
	//! in Rust). Types may have functions "implemented" on them, and may
	//! also be polymorphic in a type variable. Traits function as
	//! interfaces to types, allowing greater flexibility with their own
	//! type variables and associated types. Traits must be implemented
	//! for types, providing the code and optionally some type variables.
	//!
	//! Rust is actually capable of more abstraction than was used in
	//! these examples. Traits, which correspond to OCaml signatures, may
	//! themselves be parametrized. Trait parameterizations are best used
	//! for behavior abstractions, while type parameterizations are for
	//! data abstractions. This separation is an important feature of the
	//! user-defined type system in Rust. Using a parametrized trait, Rust
	//! code may emulate type functions (rather than the type constructors
	//! use below). This is demonstrated below. The syntax is terrible, but
	//! the use is pretty straight-forward.
	//!
	//! All the abstractions used below are _static_, or handled at
	//! compile-time. This is preferred in Rust where possible, because it
	//! makes for faster code. Dynamic dispatch is available, by binding
	//! or taking as a parameter a variable with a trait as its type.
	//! Theses are called "trait objects" and usually "boxed", or after a
	//! pointer. More complex use of OCaml modules would require trait
	//! objects to handle the run-time variability.
	//!
	//! Rust code cannot have static visibility (OCaml's concrete vs
	//! abstract types within modules) changed at run-time. At compile-time,
	//! traits with different visibility could be defined, but conversion
	//! would be difficult if even possible.
	//!
	//! The first section of the manual introduces modules without
	//! abstraction. Rust modules are sufficient for this use, and
	//! demonstrated in the translation. The rest of the manual deals with
	//! signatures and functors, which require types and traits.
	//!
	//! Most of the code can be translated line-for-line, but there are a
	//! few major differences between the languages. Rust makes pointers
	//! and data copying explicit, so references, dereferences and calls to
	//! `clone()` appear in the Rust code. Rust also lacks exceptions,
	//! so code returns the sum type `Result<SuccessType,FailureType>`.

	/// allows `<A:OCaml>` rather than <A:Clone+PartialEq+Eq>`
	pub trait OCaml : Clone + PartialEq + Eq {}
	impl<A:Clone+PartialEq+Eq> OCaml for A {}

	/// Compile-time example from the OCaml manual 2.1
	///
	/// "A primary motivation for modules is to package together related definitions..."
	/// ```ocaml
	/// module PrioQueue =
	/// struct
	/// type priority = int
	/// type 'a queue = Empty \| Node of priority * 'a * 'a queue * 'a queue
	/// let empty = Empty
	/// let rec insert queue prio elt =
	/// match queue with
	/// Empty -> Node(prio, elt, Empty, Empty)
	/// \| Node(p, e, left, right) ->
	/// if prio <= p
	/// then Node(prio, elt, insert right p e, left)
	/// else Node(p, e, insert right prio elt, left)
	/// exception Queue_is_empty
	/// let rec remove_top = function
	/// Empty -> raise Queue_is_empty
	/// \| Node(prio, elt, left, Empty) -> left
	/// \| Node(prio, elt, Empty, right) -> right
	/// \| Node(prio, elt, (Node(lprio, lelt, _, _) as left),
	/// (Node(rprio, relt, _, _) as right)) ->
	/// if lprio <= rprio
	/// then Node(lprio, lelt, remove_top left, right)
	/// else Node(rprio, relt, left, remove_top right)
	/// let extract = function
	/// Empty -> raise Queue_is_empty
	/// \| Node(prio, elt, _, _) as queue -> (prio, elt, remove_top queue)
	/// end;;
	/// ```
	pub mod prio_queue {
	// modules do not have full access to outer scope by default
	use super::OCaml;
	// needed for shared data structures
	use std::rc::Rc;
	// avoids explicit scoping, contrary to idiomatic Rust
	use self::Queue::*;

	pub type Priority = i32;
	#[derive(Clone, PartialEq, Eq)]
	pub enum Queue<A:OCaml> { Empty, Node(Priority,A,Rc<Queue<A>>,Rc<Queue<A>>) }
	pub fn empty<A:OCaml>() -> Queue<A> { Empty }
	pub fn insert<A:OCaml>(queue: &Queue<A>, prio: Priority, elt:&A) -> Queue<A> {
	match *queue {
	Empty => Node(prio, elt.clone(), Rc::new(Empty), Rc::new(Empty)),
	Node(p,ref e,ref left,ref right) => {
	if prio <= p {
	Node(prio, elt.clone(), Rc::new(insert(&**right, p, e)), left.clone())
	} else { Node(p, e.clone(), Rc::new(insert(&**right, prio, elt)), left.clone()) }
	}
	}
	}
	#[derive(Debug)]
	pub enum Exception { QueueIsEmpty }
	pub(super) fn remove_top<A:OCaml>(q: &Queue<A>) -> Result<Queue<A>,Exception> { match *q {
	Empty => Err(Exception::QueueIsEmpty),
	Node(_, _, ref left, ref right) if right == Empty => Ok((left).clone()),
	Node(_, _, ref left, ref right) if left == Empty => Ok((right).clone()),
	Node(_, _, ref left, ref right) => match (&left, &right) {
	(&Node(lprio, ref lelt, _,_),&Node(rprio, ref relt,_,_)) => {
	if lprio <= rprio {
	Ok(Node(lprio, lelt.clone(), Rc::new(remove_top(&**left)?), right.clone()))
	} else { Ok(Node(rprio, relt.clone(), left.clone(), Rc::new(remove_top(&**right)?))) }
	} _ => unreachable!() //needed inner `match` to handle patterns into linked structure
	}
	}}
	pub fn extract<A:OCaml>(q: &Queue<A>) -> Result<(Priority, A, Queue<A>),Exception> { match *q {
	Empty => Err(Exception::QueueIsEmpty),
	Node(prio, ref elt, _, _) => Ok((prio, elt.clone(), remove_top(q)?)),
	}}
	}

	/// Compile-time example from OCaml manual 2.1
	///
	/// "It is also possible to copy the components of a module inside another module..."
	/// ```ocaml
	/// module PrioQueueOpt =
	/// struct
	/// include PrioQueue
	/// let remove_top_opt x =
	/// try Some(remove_top x) with Queue_is_empty -> None
	/// let extract_opt x =
	/// try Some(extract x) with Queue_is_empty -> None
	/// end;;
	/// ```
	pub mod prio_queue_opt {
	use super::OCaml;

	pub use prio_queue::*;
	#[allow(unused)]
	pub(super) fn remove_top_opt<A:OCaml>(q: &Queue<A>) -> Option<Queue<A>> {
	// to check the exception
	match remove_top(q) {
	Err(Exception::QueueIsEmpty) => None,
	Ok(res) => Some(res),
	}
	}
	pub fn extract_opt<A:OCaml>(q: &Queue<A>) -> Option<(Priority, A, Queue<A>)> {
	// shortcut if you don't need to check the exception
	extract(q).ok()
	}
	}

	/// Runtime-examples from OCaml manual 2.1
	///
	/// ```ocaml
	/// PrioQueue.insert PrioQueue.empty 1 "hello";;
	/// open PrioQueue;;
	/// insert empty 1 "hello";;
	///
	/// let empty = []
	/// open PrioQueue;;
	/// let x = 1 :: empty ;;
	///
	/// let open PrioQueue in
	/// insert empty 1 "hello";;
	/// ````
	///
	/// This code shows off different syntax for accessing module functions.
	/// It has no equivalent in Rust
	/// ```ocaml
	/// PrioQueue.[empty] = PrioQueue.([empty]);;
	///
	/// PrioQueue.[\|empty\|] = PrioQueue.([\|empty\|]);;
	///
	/// PrioQueue.{ contents = empty } = PrioQueue.({ contents = empty });;
	///
	/// PrioQueue.[insert empty 1 "hello"];;
	/// ```
	fn sec1() {
	// this is altered to show that `prio_queue_opt` contains the items
	// from `prio_queue`, and that the two are compatible
	prio_queue_opt::insert(&prio_queue::empty(), 1, &"hello".to_string());
	use prio_queue::*;
	insert(&empty(),1,&"hello".to_string());

	// this function causes an error in the
	// _previous_ line, but not the next!
	// fn empty() -> () { () }

	{
	use prio_queue::*;
	insert(&empty(),1,&"hello".to_string());
	}
	}

	/// Compile-time example from OCaml manual 2.2
	///
	/// ```ocaml
	/// module type PRIOQUEUE =
	/// sig
	/// type priority = int (* still concrete *)
	/// type 'a queue (* now abstract *)
	/// val empty : 'a queue
	/// val insert : 'a queue -> int -> 'a -> 'a queue
	/// val extract : 'a queue -> int * 'a * 'a queue
	/// exception Queue_is_empty
	/// end;;
	/// ```
	pub trait PrioQueueSig where Self:Sized {
	// Concrete types cannot be defined here, use an external definition
	// for types Priority and Exception

	// In Rust we have a self type, which can naturally assume the role
	// of the OCaml `'a queue` (or more generally, Module.t). That
	// leaves us with just the `'a` needing a definition.
	type A : OCaml;
	fn empty() -> Self;
	fn insert(&self, Priority, &Self::A) -> Self;
	fn extract(&self) -> Result<(Priority, Self::A, Self),Exception>;
	}

	// The following are implementations for using a Rust type like an OCaml
	// module. Normally, the code above would be here, but it's all correctly
	// typed so we can just call back to it.
	pub type Priority = prio_queue::Priority;
	pub type Exception = prio_queue::Exception;
	pub type PrioQueue<A> = prio_queue::Queue<A>;
	impl<A:OCaml> PrioQueueSig for PrioQueue<A> {
	type A = A;
	fn empty() -> Self { prio_queue::empty() }
	fn insert(&self, p: Priority, elt: &A) -> Self {
	prio_queue::insert(&self, p, elt)
	}
	fn extract(&self) -> Result<(Priority, Self::A, Self),Exception> {
	prio_queue::extract(&self)
	}
	}
	// This is not part of the sig, but part of the original
	impl <A:OCaml> PrioQueue<A> {
	pub fn remove_top(&self) -> Result<Self,Exception> {
	prio_queue::remove_top(&self)
	}
	}

	/// Run-time examples from OCaml manual 2.2
	///
	/// ```ocaml
	/// module AbstractPrioQueue = (PrioQueue : PRIOQUEUE);;
	/// AbstractPrioQueue.remove_top ;;
	/// AbstractPrioQueue.insert AbstractPrioQueue.empty 1 "hello";;
	/// ```
	///
	/// This section is a bit different in Rust, because visibility cannot
	/// be adjusted in this way. You can reduce visibility within a function
	/// that takes the type (analog to OCaml module) as a parameter. However,
	/// this reduces the visibility to the compiler as well, so it cannot
	/// use the concrete type, even if it's passed to the function. This
	/// issue is present in OCaml in other situations and will be demonstrated
	/// in a later section.
	///
	/// Finally, the trait (analog to OCaml sig) can be used directly as if
	/// it were an abstract type, but Rust's type inference is not able to
	/// handle this situation without a type annotation, since it's the
	/// compiler that chooses the implementation.
	fn sec2() {
	#[allow(path_statements)] // supress warning generated in body
	fn reduce_visibility<AbstractPrioQueue:PrioQueueSig>() {
	// error: function not found
	// AbstractPrioQueue::remove_top;

	// warning: no effect
	AbstractPrioQueue::insert;

	// types don't match because of abstraction, solution in later section
	// AbstractPrioQueue::insert(&AbstractPrioQueue::empty(), 1, &"hello".to_string());
	}
	reduce_visibility::<PrioQueue<String>>();

	// Rust requires an annotation here
	let _:PrioQueue<String> = PrioQueueSig::insert(&PrioQueueSig::empty(),1,&"hello".to_string());
	}

	/// Compile-time example from OCaml manual 2.2
	///
	/// ```ocaml
	/// module type PRIOQUEUE_WITH_OPT =
	/// sig
	/// include PRIOQUEUE
	/// val extract_opt : 'a queue -> (int * 'a * 'a queue) option
	/// end;;
	/// ```
	trait PrioQueueSiGWithOpt : PrioQueueSig {
	fn extract_opt(&self) -> Option<(Priority,Self::A,Self)>;
	}
	impl<A:OCaml> PrioQueueSiGWithOpt for PrioQueue<A> {
	fn extract_opt(&self) -> Option<(Priority,Self::A,Self)>{
	prio_queue_opt::extract_opt(&self)
	}
	}

	/// Compile-time example from OCaml manual 2.3
	///
	/// ```ocaml
	/// type comparison = Less \| Equal \| Greater;;
	/// module type ORDERED_TYPE =
	/// sig
	/// type t
	/// val compare: t -> t -> comparison
	/// end;;
	/// module Set =
	/// functor (Elt: ORDERED_TYPE) ->
	/// struct
	/// type element = Elt.t
	/// type set = element list
	/// let empty = []
	/// let rec add x s =
	/// match s with
	/// [] -> [x]
	/// \| hd::tl ->
	/// match Elt.compare x hd with
	/// Equal -> s (* x is already in s *)
	/// \| Less -> x :: s (* x is smaller than all elements of s *)
	/// \| Greater -> hd :: add x tl
	/// let rec member x s =
	/// match s with
	/// [] -> false
	/// \| hd::tl ->
	/// match Elt.compare x hd with
	/// Equal -> true (* x belongs to s *)
	/// \| Less -> false (* x is smaller than all elements of s *)
	/// \| Greater -> member x tl
	/// end;;
	/// module OrderedString =
	/// struct
	/// type t = string
	/// let compare x y = if x = y then Equal else if x < y then Less else Greater
	/// end;;
	/// ```
	pub mod ordered_type {
	use std::rc::Rc;
	use super::OCaml;

	pub enum Comparison { Less, Equal, Greater }
	/// The property of a type with an inherent order
	pub trait OrderedType {
	fn compare(&self, other:&Self) -> Comparison;
	}
	/// Rust lacks cons-lists, they're not efficent and they're easily defined
	#[derive(Clone,PartialEq,Eq)]
	pub enum Set<A> { Nil, Cons(A,Rc<Set<A>>) }

	impl<Elt:OCaml+OrderedType> Set<Elt> {
	pub fn empty() -> Self { Set::Nil }
	pub fn add(&self, x:Elt) -> Self {
	match self {
	&Set::Nil => Set::Cons(x,Rc::new(Set::Nil)),
	&Set::Cons(ref hd,ref tl) => {
	match Elt::compare(&x,hd) {
	Comparison::Equal => self.clone(),
	Comparison::Less => Set::Cons(x,Rc::new(self.clone())),
	Comparison::Greater => Set::Cons(hd.clone(), Rc::new(tl.add(x))),
	}
	}
	}
	}
	pub fn member(&self, x:&Elt) -> bool {
	match self {
	&Set::Nil => false,
	&Set::Cons(ref hd,ref tl) => {
	match Elt::compare(x,hd) {
	Comparison::Equal => true,
	Comparison::Less => false,
	Comparison::Greater => tl.member(x)
	}
	}
	}
	}
	}
	impl OrderedType for String {
	fn compare(&self, other:&Self) -> Comparison {
	if self == other { Comparison::Equal }
	else if self < other { Comparison::Less }
	else { Comparison::Greater }
	}
	}
	}

	/// Run-time example from OCaml manual 2.3
	///
	/// ```ocaml
	/// module StringSet = Set(OrderedString);;
	/// StringSet.member "bar" (StringSet.add "foo" StringSet.empty);;
	/// ```
	fn sec3() {
	use ordered_type::*;

	// in Rust this is a simple alias, and not worth writing here
	// type StringSet = Set<String>;

	Set::empty().add("foo".to_string()).member(&"bar".to_string());
	}


	/// Compile-time examples from OCaml manual 2.4
	///
	/// ```ocaml
	/// module type SETFUNCTOR =
	/// functor (Elt: ORDERED_TYPE) ->
	/// sig
	/// type element = Elt.t (* concrete *)
	/// type set (* abstract *)
	/// val empty : set
	/// val add : element -> set -> set
	/// val member : element -> set -> bool
	/// end;;
	///
	/// module type SET =
	/// sig
	/// type element
	/// type set
	/// val empty : set
	/// val add : element -> set -> set
	/// val member : element -> set -> bool
	/// end;;
	///
	/// module NoCaseString =
	/// struct
	/// type t = string
	/// let compare s1 s2 =
	/// OrderedString.compare (String.lowercase_ascii s1) (String.lowercase_ascii s2)
	/// end;;
	/// ```
	pub mod man24 {
	use std::rc::Rc;
	use super::OCaml;
	use ordered_type::*;

	// A type may be
	// 'abstract' by keeping its internal structure private. The following
	// is a public interface to a struct with private elements. It can only be
	// constructed and deconstructed by its own methods.
	#[derive(Clone,PartialEq,Eq)]
	pub struct AbstractOrderedSet<A:Ordering> { set: Set<A::Type> }

	// To allow multiple combinations of type and order, we can create a more
	// general trait that more closely matches the OCaml version. We also require
	// that the implementing type is clonable.
	pub trait Ordering : Clone {
	type Type: OCaml + OrderedType;
	fn compare(one: &Self::Type, two: &Self::Type) -> Comparison;
	}

	// impl mostly copied from above, but with `Elt` changed to `Order` or
	// `Order::Type` as appropriate and using our new defn of AbstractOrderedSet
	impl<Order:Ordering> AbstractOrderedSet<Order> {
	pub fn empty() -> Self { AbstractOrderedSet{set: Set::Nil} }
	pub fn add(&self, x:Order::Type) -> Self {
	match self.set {
	Set::Nil => AbstractOrderedSet{set:Set::Cons(x,Rc::new(Set::Nil))},
	Set::Cons(ref hd,ref tl) => {
	match Order::compare(&x,hd) {
	Comparison::Equal => (*self).clone(),
	Comparison::Less => AbstractOrderedSet{set:Set::Cons(x,Rc::new(self.set.clone()))},
	Comparison::Greater => AbstractOrderedSet{set:Set::Cons(hd.clone(), Rc::new(tl.add(x)))},
	}
	}
	}
	}
	pub fn member(&self, x:&Order::Type) -> bool {
	match self.set {
	Set::Nil => false,
	Set::Cons(ref hd,ref tl) => {
	match Order::compare(x,hd) {
	Comparison::Equal => true,
	Comparison::Less => false,
	Comparison::Greater => tl.member(x)
	}
	}
	}
	}
	}

	// helper for types that have an inherent order as defined previously. This is
	// to be used as a 'marker type' and we won't ever use the value consructor.
	// This is a blanket implemetation, all types with a order defined may now be used
	// with our new abstract `Set` by e.g. `AbstractOrderedSet<DefaultOrdering<String>>`
	#[derive(Clone,PartialEq,Eq)]
	pub struct DefaultOrdering<A>(A);
	impl<A:OCaml+OrderedType> Ordering for DefaultOrdering<A> {
	type Type = A;
	fn compare(one: &Self::Type, two: &Self::Type) -> Comparison {
	A::compare(one, two)
	}
	}

	// new string ordering
	#[derive(Clone,PartialEq,Eq)]
	pub struct NoCaseString;
	impl Ordering for NoCaseString {
	type Type = String;
	fn compare(one: &Self::Type, two: &Self::Type) -> Comparison {
	String::compare(&one.to_lowercase(),&two.to_lowercase())
	}
	}

	// As seen above, Rust does not have the same semantics of
	// abstract interfaces as OCaml. However, there is still the
	// problem of matching two of them up, and Rust has its own
	// `with` clause, `where`:
	#[derive(Clone,PartialEq,Eq)]
	pub struct DoubleOrder<A,B>(A,B);
	impl<A:Ordering,B:Ordering,C:OCaml+OrderedType> DoubleOrder<A,B> where
	A:Ordering<Type=C>,
	B:Ordering<Type=C>
	{
	// without the where clause above, these are different types.
	pub fn compare(a:&A::Type,b:&B::Type) -> Comparison {
	A::compare(a,b)
	}
	}

	// A type function for the AbstractOrderedSet constructor, using the
	// associated type of a parametrized trait
	trait Func<In> { type Out; }
	#[allow(unused)]
	struct AOSfn;
	impl<In: Ordering> Func<In> for AOSfn { type Out = AbstractOrderedSet<In>; }
	#[allow(unused)]
	type Derived = <AOSfn as Func<NoCaseString>>::Out;
	}

	/// Run-time examples from OCaml manual 2.4
	///
	/// ```ocaml
	/// module AbstractSet = (Set : SETFUNCTOR);;
	/// module AbstractStringSet = AbstractSet(OrderedString);;
	/// AbstractStringSet.add "gee" AbstractStringSet.empty;;
	/// module WrongSet = (Set : functor(Elt: ORDERED_TYPE) -> SET);;
	/// module WrongStringSet = WrongSet(OrderedString);;
	/// WrongStringSet.add "gee" WrongStringSet.empty ;;
	/// module AbstractSet2 = (Set : functor(Elt: ORDERED_TYPE) -> (SET with type element = Elt.t));;
	/// module NoCaseStringSet = AbstractSet(NoCaseString);;
	/// NoCaseStringSet.add "FOO" AbstractStringSet.empty ;;
	/// ```
	fn sec4() {
	use man24::*;
	// As before, visibility is not adjustable at runtime.
	// module AbstractSet = (Set : SETFUNCTOR);;

	#[allow(unused)]
	type AbstractStringSet = AbstractOrderedSet<DefaultOrdering<String>>;

	// The `WrongSet` examples would be meaningless in static Rust, because the
	// compiler does know that the types match (They're both litterally the same).
	// The demonstration of the `with` clause is unnessecary here, but a different
	// one was included above (see DoubleOrder).

	#[allow(unused)]
	type NoCaseStringSet = AbstractOrderedSet<NoCaseString>;

	// Error: two different types
	// NoCaseStringSet::add(&AbstractStringSet::empty(), "FOO".to_string());
	}



	fn main() {
	sec1();
	sec2();
	sec3();
	sec4();
	}