EphemeralStream.scala

import scala.annotation.tailrec

/**
  * Created by emilypi on 5/17/17.
  */
trait Stream[+A] {
  import Stream._

  def head: () => A

  def tail: () => Stream[A]

  def isEmpty: Boolean

  def headOption: Option[A]

  def tailOption: Option[Stream[A]]

  def foldLeft[B](f: => ( => B) => (=> A) => B)(z: => B): B = {
    var t = this
    var acc = z
    while (!t.isEmpty) {
      var head = t.head
      acc = f(acc)(head())
      t = t.tail()
    }
    acc
  }

  def unfold[A, B](b: => B, f: B => Option[(A, B)]): Stream[A] =
    f(b) match {
      case None => Empty
      case Some((a, r)) => cons(a, unfold(r, f))
    }


  def #:::[B >: A](ss: => Stream[B]): Stream[B] = {
    def g(b: => Stream[B])(a: => B): Stream[B] = cons(a, b)
    foldLeft(g)(this)
  }

  def flatMap[B](f: (=> A) => Stream[B]): Stream[B] = {
    def g(b: => Stream[B])(a: => A): Stream[B] = f(a) #::: b
    foldLeft(g)(Empty)
  }

  def map[B](f: (=> A) => B): Stream[B] = {
    def g(b: => Stream[B])(a: => A): Stream[B] = cons(f(a), b)
    foldLeft(g)(Empty)
  }

  def reverse: Stream[A] = {
    var t = this
    var acc: Stream[A] = Empty
    while (!t.isEmpty) {
      acc = t.head() #:: acc
      t = t.tail()
    }
    acc
  }

  def iterator: Iterator[A] = this.to[Iterator]

}

final case class #::[+A](h: () => A, t: () => Stream[A]) extends Stream[A] {

  def head: () => A = h
  def tail: () => Stream[A] = t
  def headOption: Option[A] = Some(h())
  def tailOption: Option[Stream[A]] = Some(t())
  def isEmpty: Boolean = false
  override def toString: String = s"Stream(${head()}, ?)"
 
}

case object Empty extends Stream[Nothing] {

  def head: () => Nothing = throw new NoSuchElementException
  def tail: () => Stream[Nothing] = () => Empty
  def headOption = None
  def tailOption = None
  def peak(i: Int) = Nil
  def isEmpty: Boolean = true
  override def toString: String = "Empty"

}


object #:: {

  def unapply[A](as: Stream[A]): Option[(A, Stream[A])] =
    if (as.isEmpty) None
    else Some((as.head()), as.tail())

}

object Stream {

  //Streams are implicitly wrapped in this class and given the #:: constructor method so we can 3 #:: Empty and so on
  implicit class StreamWrapper[A](s: => Stream[A]) {

    /**
      * This method allows the #:: class constructor to be wrapped in a right-binding operator
      * Basically, instead of calling new #::(_, _), now we can call h #:: t. Standard cons operation.
      *
      * @param h - element to construct new #:: with
      * @return a new Stream with element prepended
      */
    def #::(h: A): Stream[A] = cons(h, s)

    /**
      * Defines "to" methods, similar to toList and toSet, where instead of having individual methods
      * for each, we define a generic way to do it using any Functor F, as long as there is a natural transformation
      * provided to go from Stream ~> F. For more information, see the package object for example instances
      *
      * This is actually more generic than the Scala to* methods
      *
      * @param nt - natural transformation from Stream ~> F
      * @tparam F - Target Functor (e.g. List, Set, Option)
      * @return
      */
    def to[F[_]](implicit nt: (Stream ~> F)): F[A] = nt(s)

  }

  def cons[A](a: => A, tail: => Stream[A]): Stream[A] = {
    lazy val la = a
    lazy val lt = tail
    new #::(() => la, () => lt)
  }


  def apply[A](as: A*): Stream[A] = {
    @tailrec
    def go(acc: Stream[A], as: collection.immutable.Stream[A]): Stream[A] =
      as match {
        case x +: xs => go(cons(x, acc), xs)
        case collection.immutable.Stream.Empty => acc
      }
    go(Empty, as.toStream)
  }

  def apply[A](a: => A): Stream[A] = {
    lazy val aa = a
    new #::(() => aa, () => Empty)
  }
}

package.scala

package object euroscores {

  trait NaturalTransformation[F[_], G[_]] { def apply[A](fa: F[A]): G[A] }

  type ~>[F[_], G[_]] = NaturalTransformation[F, G]

  def concat[A](s: Stream[A]): Seq[A] = {
    @tailrec
    def go(acc: Seq[A], s: Stream[A]): Seq[A] =
      s match {
        case x #:: xs => go(acc :+ x, xs)
        case Empty => acc
      }
    go(Nil, s)
  }

  implicit val streamToList = new (Stream ~> List) {
    def apply[A](s: Stream[A]): List[A] = concat(s).toList
  }

  implicit val streamToSet = new (Stream ~> Set) {
    def apply[A](s: Stream[A]): Set[A] = concat(s).toSet
  }

  implicit val streamToVector = new (Stream ~> Vector) {
    def apply[A](s: Stream[A]): Vector[A] = concat(s).toVector
  }

  implicit val streamToOption = new (Stream ~> Option) {
   def apply[A](fa: Stream[A]): Option[A] = fa.headOption
  }

}