From e1c732db445d1ab0172bc25073ce865acc7d280b Mon Sep 17 00:00:00 2001 From: Adriaan Moors Date: Fri, 6 Apr 2007 09:23:03 +0000 Subject: merged in tcpoly branch (at r10641) --- docs/examples/tcpoly/collection/HOSeq.scala | 167 ++++++++++++++++++++++++++++ docs/examples/tcpoly/monads/Monads.scala | 69 ++++++++++++ 2 files changed, 236 insertions(+) create mode 100644 docs/examples/tcpoly/collection/HOSeq.scala create mode 100644 docs/examples/tcpoly/monads/Monads.scala (limited to 'docs') 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 -- cgit v1.2.3