FP in Scala 5.1 - 5.16

gistfile1.scala

package FPinScala

/**
 * Created by BPK_t on 2015/06/24.
 */
object Main {
  def main(args: Array[String]) {

    val s = Stream(1,2,3,4)
    println("toList=" + s.toList)

    val s1 = Stream(1,2,3,4)
    println("take=" + s1.take(1).toList)

    val s2 = Stream(1,2,3,4)
    println("take=" + s2.take(3).toList)

    val s3 = Stream(1,2,3,4)
    println("drop=" + s3.drop(2).toList)

    val s4 = Stream(2, 4, 5, 6)
    println("takeWhile=" + s4.takeWhile(_ % 2 == 0).toList)

    val s5 = Stream(2,4,6,8)
    println("forAll=" + s5.forAll(_ % 2 == 0))

    val s6 = Stream(2,4,5,8)
    println("forAll=" + s6.forAll(_ % 2 == 0))

    val s7 = Stream(2,4,5,6)
    println("takeWhileFR=" + s7.takeWhileFR(_ % 2 == 0).toList)

    val s8 = Stream(1,2,3)
    println("headOption=" + s8.headOption)

    val s9 = Stream()
    println("headOption=" + s9.headOption)

    val s10 = Stream("1", "2", "3", "4")
    println("map=" + s10.map(_.toInt).toList)

    val s11 = Stream(1,2,3)
    println("append=" + s11.append(Stream(4,5,6)).toList)

    val s12 = Stream(Stream(1,2,3), Stream(4,5,6))
    println(s12.flatMap(x => x.map(y => y + 10)).toList)

    val s13 = Stream.constant(1)
    println(s13.take(10).toList)

    val s14 = Stream.from(0)
    println(s14.take(10).toList)

    val s15 = Stream.fibs()
    println(s15.take(10).toList)

    val s16 = Stream.fibsU()
    println(s16.take(10).toList)

    val s17 = Stream.fromU(0)
    println(s17.take(10).toList)

    val s18 = Stream.constantU(0)
    println(s18.take(10).toList)

    val s19 = Stream.ones
    println(s19.take(10).toList)

    val s20 = Stream("1", "2", "3", "4")
    println(Stream.map(s20)(_.toInt).toList)

    val s21 = Stream(1,2,3,4)
    println(Stream.take(s21, 2).toList)

    println(Stream.zipWith(Stream(1,1,1), Stream(2,2,2))(_+_).toList)

    val s22 = Stream(1,2,3,4,5)
    println("startsWith=" + s22.startsWith(Stream(1,4,3,4,5)))

    val s23 = Stream(1,2,3)
    s23.tails.toList.foreach(x => println(x.toList))

    val s24 = Stream(1,2,3)
    println(s24.scanRight(0)(_ + _).toList)
  }
}

trait Stream[+A]
{
  //5.1
  def toList : List[A] = toList_(this)
  private def toList_[A](stm :Stream[A]) : List[A] = {
    stm match {
      case Empty => Nil
      case Cons(h, t) => h() :: toList_(t())
    }
  }

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

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

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

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

  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.4
  def forAll(p:A=>Boolean):Boolean =
    foldRight(true)((a,b) => p(a) && b)

  //5.5
  def takeWhileFR(p: A=>Boolean) : Stream[A] =
    foldRight(Empty : Stream[A])((a,b) => if (p(a)) {Stream.cons(a, b)} else {Empty})

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

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

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

  def append[B >: A](ax: => Stream[B]): Stream[B] =
    foldRight(ax){ (x, a) => Stream.cons(x, a) }

  def flatMap[B](f: A => Stream[B]): Stream[B] =
    foldRight(Empty : Stream[B])((a, b) => f(a).append(b))

  //5.14
  def startsWith[A](s : Stream[A]) : Boolean =
    Stream.zipAll(this, s).forAll(x => {
      x match {
        case (_, None) => true
        case (None, _) => false
        case (Some(x), Some(y)) => x == y
      }
    })

  //5.15
  //ex. Stream(や,る,め,う) = Stream(Stream(や,る,め,う), Stream(る,め,う), Stream(め,う), Stream(う))
  def tails : Stream[Stream[A]] = {
    Stream.unfold(this)(x => x match {
      case Empty => None
      case Cons(h,t) => Some((x, t()))
    }).append(Stream(Empty))
  }

  //5.16
  def scanRight[B](z : => B)(f:(A, =>B) => B) : Stream[B] =
    Stream.unfold(this)(x => x match {
      case Empty => None
      case Cons(h,t) => Some((x.foldRight(z)((x,y)=>f(x,y)), t()))
    }).append(Stream(z))
}

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

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

  //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(n: Int = 0): Stream[Int] =
    Stream.cons(fibs_(n), fibs(n + 1))

  private def fibs_(n: Int): Int = n match {
    case 0 => 0
    case 1 => 1
    case 2 => 1
    case x => fibs_(x - 1) + fibs_(x - 2)
  }

  //5.11
  /**
   * ストリーム生成めう
   * Someを返す→続ける
   * Empty→もうやめる
   * @param z　初期値
   * @param f　ストリームの次の値を返す関数
   * @tparam A　値
   * @tparam S　インデックス用途とか使いまわす用のアレ
   * @return
   */
  def unfold[A, S](z: S)(f: S => Option[(A, S)]): Stream[A] = {
    f(z) match {
      case Some(t) => Stream.cons(t._1, unfold(t._2)(f))
      case None => Empty
    }
  }

  //5.12
  def fibsU(n: Int = 0): Stream[Int] =
    unfold(n)(x => Some((fibs_(x), x + 1)))

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

  def constantU[A](a: A): Stream[A] =
    unfold(a)(x => Some(x, x))

  def ones : Stream[Int] =
    unfold(1)(x => Some(x, x))

  //5.13
  //頭と胴体を分離して、別の頭にして再構築する感じ
  def map[A,B](ast : Stream[A])(f : A => B):Stream[B] =
    unfold(ast)(x => x match {
      case Empty => None
      case Cons(h,t) => Some((f(h()), t()))
    })

  //5.13
  //カウンタっぽいのを付けて、今の位置が分かるようにした
  def take[A](ast : Stream[A], n :Int) : Stream[A] =
    unfold((ast, 0))(x => {
      x._1 match {
        case Empty => None
        case Cons(h, t) => if (x._2 < n) {Some(h(), (t(), x._2 + 1))} else {None}
      }
    })

  //5.13
  //takeの応用
  def takeWhile[A](ast : Stream[A])(p: A=>Boolean) : Stream[A] =
    unfold(ast)(x => {
      x match {
        case Empty => None
        case Cons(h, t) => if (p(h())) {Some(h(), t())} else {None}
      }
    })

  //5.13
  //2つのStreamをfで新しいStreamを作る
  def zipWith[A,B](st1 : Stream[A], st2 : Stream[A])(f : (A, A) => B) : Stream[B] =
    unfold((st1, st2))(x => {
      x match {
        case (Cons(h1, t1), Cons(h2, t2)) => Some((f(h1(), h2()), (t1(), t2())))
        case _ => None
      }
    })

  //5.13
  //2つのStreamで新しいStream作る、それぞれの長さが違ったら足りない分をNoneで埋める
  def zipAll[A,B](st1 : Stream[A], st2 : Stream[B]): Stream[(Option[A],Option[B])] =
    unfold((st1, st2))(x => {
      x match {
        case (Empty, Empty) => None
        case (Cons(h1, t1), Empty) => Some(((Some(h1()), None), (t1(), Empty)))
        case (Empty, Cons(h2, t2)) => Some(((None, Some(h2())), (Empty, t2())))
        case (Cons(h1, t1), Cons(h2, t2)) => Some(((Some(h1()), Some(h2())), (t1(), t2())))
      }
    })
}