fp in scala

0_fp in scala

-fp in scalaのexercuseの解をUp 

exercuse 2.1

// answer
def fib(n: Int): Int = {
  @annotation.tailrec
  def loop(v: (Int,Int), count: Int): Int = {
    val (x, y) = v
    if (n > count) loop((y,x+y),count+1)
    else x
  }
  loop((0, 0+1), 0)
}

// 公式のanswer
def fib(n: Int): Int = {
  @annotation.tailrec
  def loop(n: (Int,Int), max: Int): Int = {
    val (x,y) = n
    if (max <= 0) x
    else loop((y,x+y),max-1)
  }
  loop((0,1),n)
}

exercuse 2.2

// answer
def isSorted[A](as: Array[A], ordered: (A,A) => Boolean) = {
  @annotation.tailrec
  def loop(ar: Seq[A]): Boolean = {
    ar match {
      case Seq(x ,y, vs@_*) =>
        if (ordered(x,y)) loop(y +: vs)
        else false
      case _ => true
    }
  }
  loop(as.toSeq)
}

// 公式のanswer
def isSorted[A](as: Array[A], ordered:(A,A) => Boolean): Boolean = {
  @annotation.tailrec
  def loop(n: Seq[A]): Boolean = {
    n match {
      case Seq(x, y, vs@_*) =>
        if (ordered(x, y)) loop(y +: vs)
        else false
      case _ => true
    }
  }
  loop(as.toSeq)
}

isSorted[Int](Array(1,2,3), (x:Int,y:Int) => if (x < y) true else false)

exercuse 2.3

// answer
def curry[A,B,C](f: (A,B) => C): A => (B => C) = (a: A) => (b: B) => f(a, b)

// 公式のanswer
def curry[A,B,C](f: (A,B) => C): A => (B => C) = (a: A) => ((b: B) => f(a,b))

exercuse 2.4

// answer
def uncurry[A,B,C](f: A => B => C): (A,B) => C = (a: A, b: B) => f(a)(b)

//公式のanswer
def uncurry[A,B,C](f: A => B => C): (A,B) => C = (a: A,b: B) => f(a)(b)

exercuse 2.5

// answer
def compose[A,B,C](f: B => C, g: A => B): A => C = (a: A) => f(g(a))

// 公式のanswer
def compose[A,B,C](f: B => C, g: A => B): A => C = (a: A) => f(g(a))

exercuse 3.1

scala> 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: Int = 3

exercuse 3.10

// answer
def foldLeft[A,B](l: List[A], z: B)(f: (B, A) => B): B = l match {
  case Nil => z
  case Cons(h,t) => foldLeft(t, f(z,h))(f)
}

// 公式のanswer

exercuse 3.11

foldLeftを使ってsum,product,およびリストの長さを計算する関数を記述せよ。

// answer
def sum(l: List[Int]): Int = foldLeft(l,0)(_+_)
def product(l: List[Int]): Int = foldLeft(l,1.0)(_*_)
def length[A](l: List[A]): Int = foldLeft(l,0)( (acc,_) => cnt + 1)

// 公式のanswer
def sum3(l: List[Int]) = foldLeft(l, 0)(_ + _)
def product3(l: List[Double]) = foldLeft(l, 1.0)(_ * _)
def length2[A](l: List[A]): Int = foldLeft(l, 0)((acc,h) => acc + 1)

exercuse 3.12

要素が逆に並んだリストを返す関数を記述せよ。List(1,2,3)が与えられた場合、この関数はList(3,2,1)を返す。
畳み込みを使って記述できるかどうかを確認すること。

// answer
def reverse[A](l: List[A]): List[A] = foldLeft(l, List[A]())((acc,h) => Cons(h,acc))

// 公式のanswer
def reverse[A](l: List[A]): List[A] = foldLeft(l, List[A]())((acc,h) => Cons(h,acc))

exercuse 3.13

難問: foldRightをベースとしてfoldLeftを記述することは可能か。その逆はどうか。
foldLeftを使ってfoldRightを実装すると、foldRightを末尾再帰的に実装することが可能となり、
大きなリストでもスタックオーバーフローが発生しなくなるので便利である。

// answer
def foldRightLeft[A,B](l: List[A], z: B)(f: (A,B) => B): B = foldLeft(l, (b:B) => b)((e,a) => b => e(f(a,b)))(z)
def foldLeftRight[A,B](l: List[A], z: B)(f: (B,A) => B): B = foldRight(l, (b:B) => b)((a,e) => b => e(f(b,a)))(z)

exercuse 3.14

foldLeftまたはfoldRightをベースとしてappendを実装せよ。

// answer
def append[A](l: List[A], z: A) = foldRight(l,List(z))(Cons(_,_))
def append[A](l: List[A], z: List[A]) = foldRight(l,z)(Cons(_,_))

exercuse 3.15

難問: 複数のリストからなるリストを1つのリストとして連結する関数を記述せよ。
この関数の実行時間はすべてのリストの長さの合計に対して線形になるはずである。
すでに定義した関数を使ってみること。
def flatten[A](l: List[List[A]]): List[A] = foldRight(l, List[A]())((l,h) => append(_,_))

exercuse 3.16

各要素に1を足すことで整数のリストを変換する関数を記述せよ。
注意: これは新しいListを返す純粋関数になるはずである。

exercuse 3.17

List[Double]の各値をStringに変換する関数を記述せよ。
d.toStringという式を使ってd: DoubleをStringに変換できる

exercuse 3.18

リストの各要素を変更し、かつリストの構造をそのまま保つ総称関数mapを記述せよ。
この関数のシグネチャは以下のとおり
def map[A,B](as: List[A])(f: A => B): List[B]

exercuse 3.19

与えられた述語条件が満たされるまでリストから要素を削除するfilter関数を記述せよ。この関数を使ってList[Int]から奇数をすべて削除せよ。
def filter[A](as: List[A])(f: A => Boolean): List[A]

exercuse 3.2

// answer
def tail[A](l: List[A]): List[A] = {
  l match {
    case Nil => throw new RuntimeException("empty list")
    case Cons(_,t) => t
  }
}

// 公式のanswer
def tail[A](l: List[A]): List[A] = l match {
    case Nil => sys.error("tail of empty list")
    case Cons(_,t) => t
  }
}

exercuse 3.20

mapと同じような動きをするflatMap関数を記述せよ。
この関数は単一の結果ではなくリストを返し、そのリストは最終的な結果のリストに挿入されなければならない。
この関数のシグネチャは以下のとおり。
def flatMap[A,B](as: List[A])(f: A => List[B]): List[B]

exercuse 3.21

flatMapを使ってfilterを実装せよ

exercuse 3.22

リストを2つ受け取り、対応する要素動詞を足しあわせて新しいリストを生成する関数を記述せよ。
たとえば、List(1,2,3)とList(4,5,6)はList(5,7,9)になる。

exercuse 3.23

EXERCISE 3.22で作成した関数を、整数又は加算に限定されないように一般化せよ。
一般化された関数にはzipWithという名前をつけること。

exercuse 3.24

難問: 例として、Listに別ののListがサブシーケンスとして含まれているかどうかを調べるhasSubsequenceを実装せよ。
たとえばList(1,2,3,4)には、List(1,2),List(2,3),List(4)などがサブシーケンスとして含まれている。
純粋関数型で、コンパクトで、かつ効率的な実装を見つけ出すのは難しいかもしれない。その場合は、それでかまわない。
どのようなものであれ、最も自然な関数を実装すること。この実装については、第5章で改めて取り上げ、改良する予定である。
なおScalaでは、任意の値xおよびyに対し、x == yという式を使って等しいかどうかを比較できる。
def hasSubsequence[A](sup: List[A], sub: List[A]): Boolean

exercuse 3.25

2分木のノード(LeafとBranch)の数を数えるsize関数を記述せよ。

exercuse 3.26

Tree[Int]の最大の要素を返すmaximum関数を記述せよ。
なおScalaでは、x.max(y)またはx max yを使って2つの整数xとyの最大値を計算できる

exercuse 3.27

2分木のルートから任意のLeafまで最長のパスを返すdepth関数を記述せよ。  

exercuse 3.28

2分木の各要素を特定の関数を使って変更するmap関数を記述せよ。
この関数はListの同じ名前のメソッドに類似している。

exercuse 3.3

// answer
def setHead[A](l: List[A], h: A): List[A] = {
  l match {
    case Nil => throw new RuntimeException("empty list")
    case Cons(_,t) => Cons(h,t)
  }
}

// 公式のanswer
def setHead[A](l: List[A], h: A): List[A] = l match {
  case Nil => sys.error("setHead on empty list")
  case Cons(_,t) => Cons(h,t)
}

exercuse 3.4

// answer
def drop[A](l: List[A], n: Int): List[A] = {
  if (0 <= n) drop(tail(l), n-1)
  else tail(l)
}

// 公式のanswer
def drop[A](l: List[A], n: Int): List[A] =
  if (n <= 0) l
  else l match {
    case Nil => Nil
    case Cons(_,t) => drop(t, n-1)
  }

exercuse 3.5

// answer
def dropWhile[A](l: List[A], f: A => Boolean): List[A] = {
  l match {
    case Cons(h,t) if f(h) => dropWhile(t, f)
    case _ => l
  }
}

// 公式のanswer
def dropWhile[A](l: List[A], f: A => Boolean): List[A] =
  l match {
    case Cons(h,t) if f(h) => dropWhile(t, f)
    case _ => l
  }

exercuse 3.6

// answer
def init[A](1: List[A]): List[A] = {
  l match {
    case Nil => sys.error("empty list")
    case Cons(_,Nil) => Nil
    case Cons(h,t) => Cons(h, init(t))
  }
}

// 公式のanswer
  def init[A](l: List[A]): List[A] =
    l match {
      case Nil => sys.error("init of empty list")
      case Cons(_,Nil) => Nil
      case Cons(h,t) => Cons(h,init(t))
    }

exercuse 3.7

// answer
- foldRightを使って実装されたproductは、0.0を検出した場合に、直ちに再帰を中止して0.0を返せるか。 
 返せない。末尾から畳み込むため。f(x, foldRight(xs, z)(f))となっており、
 foldRight(xs, z)を最後まで掘っていき、式が完成した後に順次値を返していく。左->右で式を完成させ、右<-左で値を返す。
 このため、直ちに再帰を中止して値を返すことは不可能。

- 大きなリストでfoldRightを呼び出した場合の短絡の仕組みについて検討せよ。
　問題文がちょっと読み取れない。呼び出した際のデメリットだろうか。
　スタックセーフではないためスタックオーバーフローする可能性がある。

// 公式のanswer

　　　　　　　

exercuse 3.8

// answer
- foldRight(List(1,2,3), Nil:List[Int])(Cons(_,_))のように、NilおよびCons自体をfoldRightに渡した場合はどうなるか。
　Cons(1,Cons(2,Cons(3,Nil)))を返す

- これがfoldRightとListのデータコンストラクタとの関係について何を表していると思うか。
Nilのコンストラクタがアキュームレータの役割を果たしていることについて言及すればよいのだろうか・・・？（正直良く分からん）

// 公式のanswer

exercuse 3.9

// answer
def length[A](l: List[A]): Int = foldRight(l, 0)((_,cnt) => cnt + 1)

// 公式のanswer