chapter-five.scala

package me.sent1nel

sealed trait Stream[+A] {
  def headOption: Option[A] = this match {
    case Empty => None
    case Cons(h, t) => Some(h())
  }

  // 5.1
  def toList: List[A] = {
    @annotation.tailrec
    def go(s: Stream[A], acc: List[A]): List[A] = s match {
      case Cons(h,t) => go(t(), h() :: acc)
      case _ => acc
    }
    go(this, List()).reverse
  }

  // 5.2
  def take(n: Int): Stream[A] = this match {
    case Cons(h, t) if n > 0 => Cons(h, () => t().take(n - 1))
    case Cons(h, t) if n == 1 => Cons(h, t)
    case _ => Empty
  }

  def drop(n: Int): Stream[A] = this match {
    case Cons(h, t) if n > 0 => t().drop(n - 1)
    case Cons(h, t) if n == 0 => Cons(h, t)
    case _ => Empty
  }

  // 5.3
  def takeWhile(p: A => Boolean): Stream[A] = this match {
    case Cons(h, t) if p(h()) => Cons(h, () => t().takeWhile(p))
    case _ => Stream()
  }

  def exists(p: A => Boolean): Boolean = this match {
    case Cons(h, t) => p(h()) || t().exists(p)
    case _ => false
  }

  def exists2(p: A => Boolean): Boolean =
    foldRight(false)((a, b) => p(a) || b)

  // 5.4
  def forAll(p: A => Boolean): Boolean =
    foldRight(true)((a, b) => p(a) && b)

  // 5.5
  def takeWhile2(p: A => Boolean): Stream[A] =
    foldRight(Stream())((a, b) => if (p(a)) b else b)

  // 5.6
  def headOption2: Option[A] =
    foldRight(None: Option[A])((a, b) => b orElse Some(a))

  def foldRight[B](z: => B)(f: (A, => B) => B): B = this match {
    case Cons(h, t) => f(h(), t().foldRight(z)(f))
    case _ => z
  }

  // 5.7
  def map[B](f: A => B): Stream[B] =
    foldRight(Stream[B]())((a, b) => Stream.cons(f(a), b))

  def filter(f: A => Boolean): Stream[A] =
    foldRight(Stream[A]())((a, b) => if (f(a)) Stream.cons(a, b) else b)

  def append[B>:A](s: Stream[B]): Stream[B] =
    foldRight(s)((a, b) => Stream.cons(a, b))

  def flatMap[B>:A](f: => A => Stream[B]): Stream[B] =
    foldRight(Stream[B]())((a, b) => b.append(f(a)))
}
case object Empty extends Stream[Nothing]
case class Cons[+A](h: () => A, t: () => Stream[A]) extends Stream[A]

object Stream {
  def cons[A](hd: => A, tl: => Stream[A]): Stream[A] = {
    lazy val head = hd
    lazy val tail = tl
    Cons(() => head, () => tail)
  }
  def empty[A]: Stream[A] = Empty

  // 5.8
  def constant[A](a: A): Stream[A] =
    Stream.cons(a, constant(a))

  // 5.9
  def from(n: Int): Stream[Int] =
    Stream.cons(n, from(n + 1))

  // 5.10
  def fibs(): Stream[Int] = {
    def fibImpl(i: Int, a: Int, acc: Int): Stream[Int] = i match {
      case z if z < 0 => empty
      case 0 => Stream.cons(acc, fibImpl(acc, acc, a + acc))
      case o => Stream.cons(acc, fibImpl(o - 1, acc, a + acc))
    }
    fibImpl(0, 1, 0)
  }

  // 5.11
  def unfold[A, S](z: S)(f: S => Option[(A, S)]): Stream[A] =
    f(z) match {
      case Some((a, s)) => Stream.cons(a, unfold(s)(f))
      case None => Empty
    }

  // 5.12
  def fibsUnfold(): Stream[Int] =
    unfold((0, 1))(state => Some((state._1, (state._2, state._1 + state._2))))

  def fromFold(n: Int): Stream[Int] =
    unfold(n)(state => Some((state, state + 1)))

  def constantUnfold[A](a: A): Stream[A] =
    unfold(a)(s => Some((a, a)))

  def onesUnfold: Stream[Int] =
    constantUnfold(1)

  def apply[A](as: A*): Stream[A] =
    if (as.isEmpty) empty else cons(as.head, apply(as.tail: _*))
}

Alternatively:

val fib = (1, 0).ana(binarySequence(_ + _))

/** Generates an infinite sequence from two seed values.
    *
    * @group algebras
    */
  def binarySequence[A](relation: (A, A) => A): Coalgebra[(A, ?), (A, A)] = {
    case (a1, a2) =>
      val c = relation(a1, a2)
      (c, (a2, c))
  }