Skip to content

HTTPS clone URL

Subversion checkout URL

You can clone with HTTPS or Subversion.

Download ZIP
Fetching contributors…

Cannot retrieve contributors at this time

298 lines (247 sloc) 9.623 kb
package scalaz
import java.lang.ref.WeakReference
/** Like [[scala.collection.immutable.Stream]], but doesn't save
* computed values. As such, it can be used to represent similar
* things, but without the space leak problem frequently encountered
* using that type.
*/
sealed abstract class EphemeralStream[A] {
import EphemeralStream._
def isEmpty: Boolean
@deprecated("unsafe; use headOption", "7.1")
def head: () => A
@deprecated("unsafe; use tailOption", "7.1")
def tail: () => EphemeralStream[A]
def headOption: Option[A] = {
if(isEmpty) None
else Some(head())
}
def tailOption: Option[EphemeralStream[A]] = {
if(isEmpty) None
else Some(tail())
}
def toList: List[A] = {
def lcons(xs: => List[A])(x: => A) = x :: xs
foldLeft(Nil: List[A])(lcons _).reverse
}
def foldRight[B](z: => B)(f: (=> A) => (=> B) => B): B =
if (isEmpty) z else f(head())(tail().foldRight(z)(f))
def foldLeft[B](z: => B)(f: (=> B) => (=> A) => B): B = {
var t = this
var acc = z
while (!t.isEmpty) {
acc = f(acc)(t.head())
t = t.tail()
}
acc
}
def filter(p: A => Boolean): EphemeralStream[A] = {
val rest = this dropWhile (!p(_))
if (rest.isEmpty) emptyEphemeralStream
else cons(rest.head(), rest.tail() filter p)
}
def dropWhile(p: A => Boolean): EphemeralStream[A] = {
var these: EphemeralStream[A] = this
while (!these.isEmpty && p(these.head())) these = these.tail()
these
}
def ++(e: => EphemeralStream[A]): EphemeralStream[A] =
foldRight[EphemeralStream[A]](e)((cons[A](_, _)).curried)
def flatMap[B](f: A => EphemeralStream[B]): EphemeralStream[B] =
foldRight[EphemeralStream[B]](emptyEphemeralStream)(h => t => f(h) ++ t)
def map[B](f: A => B): EphemeralStream[B] =
flatMap(x => EphemeralStream(f(x)))
def length = {
def addOne(c: => Int)(a: => A) = 1 + c
foldLeft(0)(addOne _)
}
def tails: EphemeralStream[EphemeralStream[A]] =
if (isEmpty) EphemeralStream(emptyEphemeralStream)
else cons(this, tail().tails)
def inits: EphemeralStream[EphemeralStream[A]] =
if (isEmpty) EphemeralStream(emptyEphemeralStream)
else cons(emptyEphemeralStream, tail().inits.map(cons(head(), _)))
def findM[M[_]: Monad](p: A => M[Boolean]): M[Option[A]] =
if(isEmpty)
Monad[M].point(None)
else {
val hh = head()
Monad[M].bind(p(hh))(if (_) Monad[M].point(Some(hh)) else tail() findM p)
}
def reverse: EphemeralStream[A] = {
def lcons(xs: => List[A])(x: => A) = x :: xs
apply(foldLeft(Nil: List[A])(lcons _) : _*)
}
def zip[B](b: => EphemeralStream[B]): EphemeralStream[(A, B)] =
if(isEmpty || b.isEmpty)
emptyEphemeralStream
else
cons((head(), b.head()), tail() zip b.tail())
def unzip[X, Y](implicit ev: A <:< (X, Y)): (EphemeralStream[X], EphemeralStream[Y]) =
foldRight((emptyEphemeralStream[X], emptyEphemeralStream[Y]))(q => r =>
(cons(q._1, r._1), cons(q._2, r._2)))
def alignWith[B, C](f: A \&/ B => C)(b: EphemeralStream[B]): EphemeralStream[C] =
if(b.isEmpty)
map(x => f(\&/.This(x)))
else if(isEmpty)
b.map(x => f(\&/.That(x)))
else
cons(f(\&/.Both(head(), b.head())), tail().alignWith(f)(b.tail()))
def interleave(q: EphemeralStream[A]): EphemeralStream[A] =
if(isEmpty)
q
else if (q.isEmpty)
this
else
cons(head(), cons(q.head(), tail() interleave q.tail()))
def take(n: Int): EphemeralStream[A] =
unfold((n, this)){ case (len, xs) =>
if(len > 0 && !xs.isEmpty)
Some((xs.head(), (len - 1, xs.tail())))
else
None
}
def takeWhile(p: A => Boolean): EphemeralStream[A] =
if(!isEmpty){
val h = head()
if(p(h)) cons(h, tail().takeWhile(p))
else emptyEphemeralStream
}else this
}
object EphemeralStream extends EphemeralStreamInstances with EphemeralStreamFunctions {
def apply[A]: EphemeralStream[A] =
emptyEphemeralStream
def apply[A](as: A*): EphemeralStream[A] = {
val as0 = as match{
case indexedSeq: collection.IndexedSeq[A] => indexedSeq
case other => other.toIndexedSeq
}
val size = as.size
unfold(0)(b =>
if (b < size) Some((as0(b), b + 1))
else None)
}
class ConsWrap[A](e: => EphemeralStream[A]) {
def ##::(h: A): EphemeralStream[A] = cons(h, e)
}
implicit def consWrapper[A](e: => EphemeralStream[A]): ConsWrap[A] =
new ConsWrap[A](e)
object ##:: {
def unapply[A](xs: EphemeralStream[A]): Option[(A, EphemeralStream[A])] =
if (xs.isEmpty) None
else Some((xs.head(), xs.tail()))
}
}
sealed abstract class EphemeralStreamInstances {
// TODO more instances
implicit val ephemeralStreamInstance: MonadPlus[EphemeralStream] with Zip[EphemeralStream] with Unzip[EphemeralStream] with Align[EphemeralStream] with Traverse[EphemeralStream] with Cobind[EphemeralStream] = new MonadPlus[EphemeralStream] with Zip[EphemeralStream] with Unzip[EphemeralStream] with Align[EphemeralStream] with Traverse[EphemeralStream] with Cobind[EphemeralStream] {
import EphemeralStream._
override def cojoin[A](a: EphemeralStream[A]): EphemeralStream[EphemeralStream[A]] = a match {
case _ ##:: tl => if (tl.isEmpty) EphemeralStream(a)
else cons(a, cojoin(tl))
case _ => emptyEphemeralStream
}
def cobind[A, B](fa: EphemeralStream[A])(f: EphemeralStream[A] => B): EphemeralStream[B] = map(cojoin(fa))(f)
def plus[A](a: EphemeralStream[A], b: => EphemeralStream[A]) = a ++ b
def bind[A, B](fa: EphemeralStream[A])(f: A => EphemeralStream[B]) = fa flatMap f
def point[A](a: => A) = EphemeralStream(a)
def empty[A] = EphemeralStream()
def zip[A, B](a: => EphemeralStream[A], b: => EphemeralStream[B]) = a zip b
def unzip[A, B](a: EphemeralStream[(A, B)]) = a.unzip
def alignWith[A, B, C](f: A \&/ B => C) =
(a, b) =>
a.alignWith(f)(b)
override def toEphemeralStream[A](fa: EphemeralStream[A]) = fa
override def foldRight[A, B](fa: EphemeralStream[A], z: => B)(f: (A, => B) => B): B =
if(fa.isEmpty) z else f(fa.head(), foldRight(fa.tail(), z)(f))
override def foldMap[A, B](fa: EphemeralStream[A])(f: A => B)(implicit M: Monoid[B]) =
this.foldRight(fa, M.zero)((a, b) => M.append(f(a), b))
override def foldLeft[A, B](fa: EphemeralStream[A], z: B)(f: (B, A) => B) =
fa.foldLeft(z)(b => a => f(b, a))
override def zipWithL[A, B, C](fa: EphemeralStream[A], fb: EphemeralStream[B])(f: (A, Option[B]) => C) = {
if(fa.isEmpty) emptyEphemeralStream
else {
val (bo, bTail) = if(fb.isEmpty) (None, emptyEphemeralStream[B])
else (Some(fb.head()), fb.tail())
cons(f(fa.head(), bo), zipWithL(fa.tail(), bTail)(f))
}
}
override def zipWithR[A, B, C](fa: EphemeralStream[A], fb: EphemeralStream[B])(f: (Option[A], B) => C) =
zipWithL(fb, fa)((b, a) => f(a, b))
def traverseImpl[G[_], A, B](fa: EphemeralStream[A])(f: A => G[B])(implicit G: Applicative[G]): G[EphemeralStream[B]] = {
val seed: G[EphemeralStream[B]] = G.point(EphemeralStream[B]())
fa.foldRight(seed) {
x => ys => G.apply2(f(x), ys)((b, bs) => EphemeralStream.cons(b, bs))
}
}
override def index[A](fa: EphemeralStream[A], i: Int): Option[A] = {
if(i < 0)
None
else{
var n = i
var these = fa
while (!these.isEmpty && n > 0){
n -= 1
these = these.tail()
}
if (these.isEmpty) None else Some(these.head())
}
}
}
import std.list._
implicit def ephemeralStreamEqual[A: Equal]: Equal[EphemeralStream[A]] = Equal[List[A]] contramap {(_: EphemeralStream[A]).toList}
}
trait EphemeralStreamFunctions {
type EStream[A] = EphemeralStream[A]
def emptyEphemeralStream[A]: EphemeralStream[A] = new EphemeralStream[A] {
def isEmpty = true
def head: () => Nothing = () => sys.error("head of empty stream")
def tail: () => Nothing = () => sys.error("tail of empty stream")
}
def cons[A](a: => A, as: => EphemeralStream[A]) = new EphemeralStream[A] {
def isEmpty = false
val head = weakMemo(a)
val tail = weakMemo(as)
}
def unfold[A, B](b: => B)(f: B => Option[(A, B)]): EphemeralStream[A] =
f(b) match {
case None => emptyEphemeralStream
case Some((a, r)) => cons(a, unfold(r)(f))
}
def iterate[A](start: A)(f: A => A): EphemeralStream[A] =
unfold(start){ a =>
val fa = f(a)
Some((fa, fa))
}
def range(lower: Int, upper: Int): EphemeralStream[Int] =
if (lower >= upper) emptyEphemeralStream else cons(lower, range(lower + 1, upper))
def fromStream[A](s: => Stream[A]): EphemeralStream[A] = s match {
case Stream() => emptyEphemeralStream
case h #:: t => cons(h, fromStream(t))
}
def toIterable[A](e: EphemeralStream[A]): Iterable[A] = new Iterable[A] {
def iterator = new Iterator[A] {
var cur = e
def next() = {
val t = cur.head()
cur = cur.tail()
t
}
def hasNext = !cur.isEmpty
}
}
def weakMemo[V](f: => V): () => V = {
val latch = new Object
// TODO I don't think this annotation does anything, as `v` isn't a class member.
@volatile var v: Option[WeakReference[V]] = None
() => {
val a = v.map(x => x.get)
if (a.isDefined && a.get != null) a.get
else latch.synchronized {
val x = f
v = Some(new WeakReference(x))
x
}
}
}
}
Jump to Line
Something went wrong with that request. Please try again.