fp in scala第三章練習問題1-10

sealed trait List[+A]

case object Nil extends List[Nothing]

case class Cons[+A](head: A, tail: List[A]) extends List[A]

1

  val x = List(1, 2, 3, 4, 5) match {
    case Cons(x, Cons(2, Cons(4, _))) => x
    case Nil => 42
    case Cons(x, Cons(y, Cons(3, Cons(4, _)))) => x + y
    case Cons(h, t) => h + List.sum(t)
    case _ => 101
  }

xの値を聞くと、パターンマッチングの問題で、結果は3で、私たちは第1のcaseが第3の数が3ではなく4であるため、次の1つを歩いて、Nilではないため、更に次の1つを歩いて、結果は一致することができて、xバインド1、yバインド2、結果は3です
2
一つのListを実現するtailメソッド実装構想は,一つのNilであれば異常を投げ出し,そうでなければlistをConsで分割するとtがtailとなる.

  def tail[A](list: List[A]): List[A] =
    list match {
      case Nil => throw new Exception("error")
      case Cons(_, t) => t
    }

3
setHeadメソッドを実装し,ヘッダ要素実装の考え方を置き換え,listがNilであるか否かを判断し,Nilであれば異常を投げ出し,そうでなければヘッダをxにバインドすればよい.

  def setHead[A](x: A, list: List[A]): List[A] = {
    list match {
      case Nil => throw new Exception("error")
      case Cons(_, xs) => Cons(x, xs)
    }

4
dropを実装し、指定された要素を除去する実装構想:除去要素の個数が0以下の場合、list自体を返し、そうでない場合、listが空の場合、空を返し、Consの場合、再帰的に除去し、呼び出し自体を呼び出し、末尾をlistとし、除去個数は最初の要素が除去されたため、n-1

  @tailrec
  def drop[A](list: List[A], n: Int): List[A] = {
    if (n <= 0) list
    else list match {
      case Nil => Nil
      case Cons(_, xs) => drop(xs, n - 1)
    }

  }

5
dropWhileを実装し、条件に合致する要素を除去し、最初の条件に合致しない実装構想がlistがConsであれば、最初の要素が除去できるかどうかを判断し、できればtailは除去方法を再帰的に呼び出し、そうでなければlistに直接戻る

  @tailrec
  def dropWhile[A](l: List[A], f: A => Boolean): List[A] = {
    l match {
      //case Cons(x, xs) => if (f(x)) dropWhile(xs, f) else l
         case Cons(x, xs) if f(x) => dropWhile(xs, f)
      case _ => l
    }
  }

6
実装initは,最後の要素を除いた他の要素実装構想を返し,listがNilであれば異常を投げ出し,Cons(x,Nil)であればNilを返し,Cons(x,xs)であれば新しいConsのheadがx,末尾がinit(xs)である.

  def init[A](l: List[A]): List[A] = l match {
    case Nil => throw new Exception("empty")
    case Cons(x, Nil) => Nil
    case Cons(x, xs) => Cons(x, init(xs))
  }

8
ひとつのfoldRightを実現するのは実は1つの初期値で、1つの操作関数で、それからListの各要素に対して順次関数を呼び出して構想を実現します:もしListがNilであれば、初期値zは最終結果として、さもなくば、f関数を呼び出して、fのタイプの署名を見てみましょう、2つのパラメータを受け取って、それぞれAとBのタイプで、最終結果はBのタイプで、ここで我々Aタイプは自然にxであり,Bタイプは再帰呼び出しxsの戻り値タイプがBであることを知ることができるので,最終的な書き方はf(x,foldRight(xs,z)(f))である.

  def foldRight[A, B](as: List[A], z: B)(f: (A, B) => B): B = as match {
    case Nil => z
    case Cons(x, xs) => f(x, foldRight(xs, z)(f))
  }

9
これを実現するにはfoldRightの考え方を用い,初期値は1,foldRightに伝達されるf関数は(xs,acc)=>acc+1,すなわち再帰時に元の結果に+1の要素があり,foldRightのタイプ署名がAタイプのasとIntタイプのaccであるのに,なぜaccがIntなのかを見てみよう.彼のタイプは(as,1)の時に確定され,1と同じタイプである.

  def length[A](as: List[A]): Int = foldRight(as, 1)((xs, acc) => acc + 1)

10
実現foldLeftの実現構想はfoldRightと類似しており、関数fが変化している.ここではBとAをBに変換し、すなわち左から右へ、右から左への区別である.したがって、Cons(x,xs)については、テール再帰が可能であり、fはzをBタイプとして伝達し、Consの最初の要素に伝達し、Bタイプを得、テールとfoldLeftを行うことができる.

  @tailrec
  def foldLeft[A, B](as: List[A], z: B)(f: (B, A) => B): B = as match {
    case Nil => z
    case Cons(x, xs) => foldLeft(xs, f(z, x))(f)
  }