Scala 関数型デザイン&プログラミング 5章 Exercise

半分解いた。半分はまたこんど。

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

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

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

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

// 5.4
  def forAll[A](p: A => Boolean): Boolean = this.foldRight(true)((x, a) => p(x) && a)

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

// 5.6
  def headOption: Option[A] = this.foldRight(None: Option[A]){ (x, a) => Some(x) }

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

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

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

  def flatMap[B](f: A => Stream[B]): Stream[B] = 
    this.foldRight(Empty: Stream[B]){ (x, a) => f(x).append(a) }

// 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 fib(n: Int): Int = n match {
      case 0 => 0
      case 1 => 1
      case 2 => 1
      case n => fib(n-2) + fib(n-1)
    }
    def go(n: Int): Stream[Int] = {
      Stream.cons(fib(n), go(n+1))
    }
    go(0)
  }

// 5.11
  def unfold[A, S](z: S)(f: S => Option[(A, S)]): Stream[A] = f(z).map(x => Stream.cons(x._1, unfold(x._2)(f))).getOrElse(Empty)

// 5.12
  def fibs: Stream[Int] = {
    def fib(n: Int): Int = n match {
      case 0 => 0
      case 1 => 1
      case 2 => 1
      case x => fib(x-2) + fib(x-1)
    }
    Stream.unfold(0){ n => Some((fib(n), n + 1)) }
  }

  def from(n: Int): Stream[Int] = Stream.unfold(n){ x => Some((x, x + 1)) }

  def constant(n: Int): Stream[Int] = Stream.unfold(0){ x => Some((n, x + 1)) }

  def ones: Stream[Int] = Stream.unfold(0){ x => Some((1, x + 1)) }

// 5.13
 def map[B](f: A => B): Stream[B] = Stream.unfold(this){ as => as match {
      case Cons(h, t) => Some((f(h()), t()))
      case Empty => None
    }
  }
  def take(n: Int): Stream[A] = Stream.unfold((this, n)){ as => as match {
      case (Cons(h, t), n) if n > 0 => Some((h(), (t(), n - 1)))
      case _ => None
    }
  }
  def takeWhile(p: A => Boolean): Stream[A] = Stream.unfold(this){ as => as match {
      case Cons(h, t) if p(h()) => Some((h(), t()))
      case _ => None
    }
  }
  def zipWith[B, C >: A](xs: Stream[C])(f: (C, C) => B): Stream[B] = Stream.unfold((this, xs)){ tp => tp match {
      case (Empty, _) => None
      case (_, Empty) => None
      case (Cons(h1, t1), Cons(h2, t2)) => Some((f(h1(), h2()), (t1(), t2())))
    }
  }
  def zipAll[B](s2: Stream[B]): Stream[(Option[A], Option[B])] = Stream.unfold((this, s2)) { tp => tp match {
      case (Empty, Empty) => None
      case (Empty, Cons(h, t)) => Some(((None, Some(h())), (Empty, t())))
      case (Cons(h, t), Empty) => Some(((Some(h()), None), (t(), Empty)))
      case (Cons(h1, t1), Cons(h2, t2)) => Some(((Some(h1()), Some(h2())), (t1(), t2())))
    }
  }

// 5.14
  def startsWith[B >: A](s: Stream[B]): Boolean = (this, s) match {
    case (Empty, Empty) => true
    case (Empty, Cons(_, _)) => false
    case (Cons(h1, t1), Cons(h2, t2)) => h1() == h2() && t1().startsWith(t2())
    case _ => true 
  }

// 5.15
  def tails: Stream[Stream[A]] = Stream.unfold((this, this)) { tp => tp match {
      case (Cons(h, t), Cons(_, _)) => Some((tp._1, (t(), this)))
      case (Empty, Cons(_, _)) => Some((Empty, (Empty, Empty)))
      case _ => None
    }
  }