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 } }