5.7

Implement map, filter, append, and flatMap using foldRight. The append method should be non-strict in its argument.

Solution

object Solution extends App {
  val stream: Stream[Int] = Stream(1,2,3,4)
  println("Stream: " + stream.toList)

  val streamPlus1 = stream.map(_ + 1)
  println("[Map]Stream+1: " + streamPlus1.toList)

  val streamFilterMultiple2 = stream.filter(_%2 == 0)
  println("streamFilterMultiple2: " + streamFilterMultiple2.toList)

  val stream2: Stream[Int] = Stream(5,6,7)
  println("stream2: " + stream2.toList)

  val appended: Stream[Int] = stream.append(stream2)
  println("appended: " + appended.toList)

  val flatMapped = stream.flatMap((x: Int) => Stream(x * 10))
  println("flatMapped: " + flatMapped.toList)
}

import scala.annotation
trait Stream[+A] {
  import Stream._

  def map[B](f: A => B): Stream[B] = foldRight(empty[B])((h,t) => cons(f(h), t))

  def filter(f: A => Boolean): Stream[A] = 
    foldRight(empty[A])((h,t) => 
                   if (f(h)) cons(h, t)
                   else t)

  def append[B >: A](s: => Stream[B]): Stream[B] =
    foldRight(s)((h,t) => cons(h,t))  

  def flatMap[B](f: A => Stream[B]): Stream[B] = 
    foldRight(empty[B])((h, t) => f(h) append t)

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

  def toList: List[A] = {
    @annotation.tailrec
    def go(l: List[A], s: Stream[A]): List[A] = s match {
      case Empty => l.reverse
      case Cons(h,t) => go(h()::l, t())
    }

    go(List(), this)
  }
}


case object Empty extends Stream[Nothing]
case class Cons[+A](h: () => A, t: () => Stream[A]) extends Stream[A]
object Stream {
  def empty[A]: Stream[A] = Empty

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

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

Output

Stream: List(1, 2, 3, 4) 
[Map]Stream+1: List(2, 3, 4, 5) 
streamFilterMultiple2: List(2, 4) 
stream2: List(5, 6, 7) 
appended: List(1, 2, 3, 4, 5, 6, 7) 
flatMapped: List(10, 20, 30, 40)