modules.scala

// Simple module type...
//
trait Ordering {
  type T

  def cmp(a: T, b: T): Int
}

// ...and implementation
//
object IntOrdering extends Ordering {
  type T = Int

  override def cmp(a: T, b: T): T =
    if (a < b) -1
    else if (a == b) 0
    else 1
}

// Trying to create some abstract modules  
//
trait Queue {
  type T[_]

  def empty[A]: T[A]

  def queue[A](elem: A, queue: T[A]): T[A]

  def peek[A](queue: T[A]): (Option[A], T[A])
}

object Queue extends Queue {
  type T[A] = (List[A], List[A])

  def empty[A]: T[A] = (Nil, Nil)

  override def queue[A](elem: A, queue: T[A]): T[A] =
    (elem :: queue._1, queue._2)

  @annotation.tailrec
  override def peek[A](queue: T[A]): (Option[A], T[A]) =
    queue match {
      case (i, h :: t) => (Some(h), (i, t))
      case (Nil, o) => (o.headOption, (Nil, o.drop(1)))
      case (i, Nil) => peek((Nil, i.reverse))
    }
}

trait Stack {
  type T[_]

  def empty[A]: T[A]

  def stack[A](elem: A, set: T[A]): T[A]
}

object Stack extends Stack {
  type T[A] = List[A]

  override def empty[A]: T[A] = List()

  override def stack[A](elem: A, set: T[A]): T[A] =
    elem :: set
}

// Invariants are enforced by accessing the module through the trait
//
val Q: Queue = Queue
val S: Stack = Stack

val queue = Q.queue(1, Q.empty)
val stack = S.stack(1, S.empty)


// Applicative Functor
//
trait Max {
  type T

  def max(a: T, b: T): T
}

object Max {
  def Make(O: Ordering) =
    new Max {
      type T = O.T

      def max(a: T, b: T): T =
        if (O.cmp(a, b) > 0) a else b
    }
}

// M1.T =:= M2.T
//
val M1 = Max.Make(IntOrdering)
val M2 = Max.Make(IntOrdering)

M2.gt(M1.max(1, 2), 4)

Mapping OCaml concepts to Scala.