merged in tcpoly branch (at r10641)

2 files changed, 236 insertions, 0 deletions

diff --git a/docs/examples/tcpoly/collection/HOSeq.scala b/docs/examples/tcpoly/collection/HOSeq.scala
new file mode 100644
index 0000000000..f2fbf720e6
--- /dev/null
+++ b/docs/examples/tcpoly/collection/HOSeq.scala
@@ -0,0 +1,167 @@
+package examples.tcpoly.collection;
+
+trait HOSeq {
+  // an internal interface that encapsulates the accumulation of elements (of type elT) to produce
+  // a structure of type coll[elT] -- different kinds of collections should provide different implicit
+  // values implementing this interface, in order to provide more performant ways of building that structure
+  trait Accumulator[+coll[x], elT] {
+    def += (el: elT): Unit
+    def result: coll[elT]
+  }
+
+
+  // Iterable abstracts over the type of its structure as well as its elements (see PolyP's Bifunctor)
+  // m[x] is intentionally unbounded: fold can then be defined nicely
+  // variance: if we write m[+x] instead of +m[+x], x is an invariant position because its enclosing type
+  //           is an invariant position -- should probably rule that out?
+  trait Iterable[+m[+x], +t] {
+    //def unit[a](orig: a): m[a]
+    def elements: Iterator[t]
+
+    // construct an empty accumulator that will produce the same structure as this iterable, with elements of type t
+    def accumulator[t]: Accumulator[m, t]
+
+    def filter(p: t => Boolean): m[t] = {
+      val buf = accumulator[t]
+      val elems = elements
+      while (elems.hasNext) { val x = elems.next; if (p(x)) buf += x }
+      buf.result
+    }
+
+    def map[s](f: t => s): m[s] = {
+      val buf = accumulator[s]
+      val elems = elements
+      while (elems.hasNext) buf += f(elems.next)
+      buf.result
+    }
+
+    // flatMap is a more specialized map, it only works if the mapped function produces Iterable values,
+    // which are then added to the result one by one
+    // the compiler should be able to find the right accumulator (implicit buf) to build the result
+    // to get concat, resColl = SingletonIterable, f = unit for SingletonIterable
+    def flatMap[resColl[x] <: Iterable[resColl, x], s](f: t => resColl[s])(implicit buf: Accumulator[resColl, s]): resColl[s] = {
+        // TODO:  would a viewbound for resColl[x] be better?
+        // -- 2nd-order type params are not yet in scope in view bound
+      val elems = elements
+      while (elems.hasNext) {
+        val elemss: Iterator[s] = f(elems.next).elements
+        while (elemss.hasNext) buf += elemss.next
+      }
+      buf.result
+    }
+  }
+
+  final class ListBuffer[A] {
+    private var start: List[A] = Nil
+    private var last: ::[A] = _
+    private var exported: boolean = false
+
+    /** Appends a single element to this buffer.
+     *
+     *  @param x  the element to append.
+     */
+    def += (x: A): unit = {
+      if (exported) copy
+      if (start.isEmpty) {
+        last = new HOSeq.this.:: (x, Nil)
+        start = last
+      } else {
+        val last1 = last
+        last = new HOSeq.this.:: (x, null) // hack: ::'s tail will actually be last
+        //last1.tl = last
+      }
+    }
+
+    /** Converts this buffer to a list
+     */
+    def toList: List[A] = {
+      exported = !start.isEmpty
+      start
+    }
+
+    /** Clears the buffer contents.
+     */
+    def clear: unit = {
+      start = Nil
+      exported = false
+    }
+
+    /** Copy contents of this buffer */
+    private def copy = {
+      var cursor = start
+      val limit = last.tail
+      clear
+      while (cursor ne limit) {
+        this += cursor.head
+        cursor = cursor.tail
+      }
+    }
+  }
+
+  implicit def listAccumulator[elT]: Accumulator[List, elT] = new Accumulator[List, elT] {
+          private[this] val buff = new ListBuffer[elT]
+          def += (el: elT): Unit = buff += el
+          def result: List[elT] = buff.toList
+  }
+
+  trait List[+t] extends Iterable[List, t] {
+          def head: t
+          def tail: List[t]
+          def isEmpty: Boolean
+          def elements: Iterator[t] = error("TODO")
+
+          // construct an empty accumulator that will produce the same structure as this iterable, with elements of type t
+          def accumulator[t]: Accumulator[List, t] = error("TODO")
+  }
+
+  // TODO: the var tl approach does not seem to work because subtyping isn't fully working yet
+  final case class ::[+b](hd: b, private val tl: List[b]) extends List[b] {
+    def head = hd
+    def tail = if(tl==null) this else tl // hack
+    override def isEmpty: boolean = false
+  }
+
+  case object Nil extends List[Nothing] {
+    def isEmpty = true
+    def head: Nothing =
+      throw new NoSuchElementException("head of empty list")
+    def tail: List[Nothing] =
+      throw new NoSuchElementException("tail of empty list")
+  }
+}
+
+
+
+// misc signatures collected from mailing list / library code:
+    /*override def flatMap[B](f: A => Iterable[B]): Set[B]
+    final override def flatMap[b](f: Any => Iterable[b]): Array[b]
+     def flatMap[b](f: a => Parser[b]) = new Parser[b]
+     override def flatMap[b](f: a => Iterable[b]): List[b]
+
+
+    MapResult[K] <: Seq[K]
+    FilterResult <: Seq[T]
+    Concat <: Seq[T]
+    Subseq <: Seq[T]
+
+
+    def map[K](f: T=>K): MapResult[K]
+    def filter(f: T=>Boolean): FilterResult
+    def subseq(from: int, to: int): Subseq
+    def flatMap[S <: Seq[K], K](f: T => S): S#Concat  // legal?
+    def concat(others: Seq[T]): Concat
+     */
+
+/*trait Iterator[t] {
+  // @post hasAdvanced implies hasNext
+  // model def hasAdvanced: Boolean
+
+  def hasNext: Boolean // pure
+
+  // @pre hasAdvanced
+  def current: t       // pure
+
+  // @pre hasNext
+  // @post hasAdvanced
+  def advance: Unit
+}*/
\ No newline at end of file
diff --git a/docs/examples/tcpoly/monads/Monads.scala b/docs/examples/tcpoly/monads/Monads.scala
new file mode 100644
index 0000000000..5fcb4cd35f
--- /dev/null
+++ b/docs/examples/tcpoly/monads/Monads.scala
@@ -0,0 +1,69 @@
+package examples.tcpoly.monad;
+
+trait Monads {
+  /**
+   * class Monad m where
+   *   (>>=)  :: m a -> (a -> m b) -> m b
+   *   return :: a -> m a
+   *
+   * MonadTC encodes the above Haskell type class,
+   * an instance of MonadTC corresponds to a method dictionary.
+   * (see http://lampwww.epfl.ch/~odersky/talks/wg2.8-boston06.pdf)
+   *
+   * Note that the identity (`this') of the method dictionary does not really correspond
+   * to the instance of m[x] (`self') that is `wrapped': e.g., unit does not use `self' (which
+   * corresponds to the argument of the implicit conversion that encodes an instance of this type class)
+   */
+   // Option =:= [x] => Option[x] <: [x] => Any
+//  trait MonadTC[m <: [x] => Any, a] {
+    // MonadTC[m[x], a] x is a type parameter too -- should not write e.g., m[Int] here
+  trait MonadTC[m[x], a] {
+    def unit[a](orig: a): m[a]
+
+    // >>='s first argument comes from the implicit definition constructing this "method dictionary"
+    def >>=[b](fun: a => m[b]): m[b]
+  }
+}
+
+/**
+ * instance Monad Maybe where
+ *   (Just x) >>= k = k x
+ *   Nothing  >>= _ = Nothing
+ */
+trait OptionMonad extends Monads {
+  // this implicit method encodes the Monad type class instance for Option
+  implicit def OptionInstOfMonad[a](self: Option[a]): MonadTC[Option, a]
+    = new MonadTC[Option, a] {
+        def unit[a](orig: a) = Some(orig)
+        def >>=[b](fun: a => Option[b]): Option[b] = self match {
+          case Some(x) => fun(x)
+          case None => None
+        }
+      }
+}
+
+object main extends OptionMonad with Application {
+  Console.println(Some("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa") >>= (x => Some(x.length)))
+}
+
+
+/*
+trait MonadTC[m[x], a] requires m[x] {
+  def unit[a](orig: a): m[a]
+
+  // >>='s first argument comes from the implicit definition constructing this "method dictionary"
+  def >>=[b](fun: a => m[b]): m[b]
+}
+
+abstract class OptionIsMonad[t[x] <: Option[x], a] implicit extends MonadTC[t, a] {
+  def unit[a](orig: a) = Some(orig) // TODO: problematic.. is a meta-member: not invoked on this
+}
+
+class SomeIsMonad[a] extends OptionIsMonad[Some, a] {
+  def >>=[b](fun: a => Option[b]): Option[b] = fun(x)
+}
+
+class NoneIsMonad[a] extends OptionIsMonad[None, a] {
+  def >>=[b](fun: a => Option[b]): Option[b] = None
+}
+*/
\ No newline at end of file