FP in scala 勉強メモ [PartⅠ 第3章 関数型プログラミングのデータ構造] ref: http://qiita.com/ma2k8/items/678b8c3bb698b7ecb244

file0.txt

// Q
以下のマッチ式はどのような結果になるか

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

file1.txt

// Q
Listの最初の要素を削除する関数tailを実装せよ。
実行時間は一定

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

file10.txt

// Q
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)

file11.txt

// Q
要素が逆に並んだリストを返す関数を記述せよ。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))

file12.txt

// Q
難問: 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)

file13.txt

// Q
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(_,_))

// 公式のanswer
def appendViaFoldRight[A](l: List[A], r: List[A]): List[A] =
  foldRight(l, r)(Cons(_,_))

file14.txt

// Q 
難問: 複数のリストからなるリストを1つのリストとして連結する関数を記述せよ。
この関数の実行時間はすべてのリストの長さの合計に対して線形になるはずである。
すでに定義した関数を使ってみること。

// answer
def flatten[A](l: List[List[A]]): List[A] = foldRight(l, List[A]())((l,h) => append(_,_))

// 公式のanswer
def concat[A](l: List[List[A]]): List[A] =
  foldRight(l, Nil:List[A])(append)

file15.txt

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

// answer
def allIncrement(l: List[Int]): List[Int] = foldRightLeft(l, List[Int]())( (a,b) => Cons(a + 1,b))

//公式のanswer
def add1(l: List[Int]): List[Int] =
  foldRight(l, Nil:List[Int])((h,t) => Cons(h+1,t))

file16.txt

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

// answer
def double2string(l: List[Double]): List[String] =
  foldRightLeft(l, Nil:List[String])((h,t) => Cons(h.toString,t))

// 公式のanswer
def doubleToString(l: List[Double]): List[String] = foldRight(l, Nil: List[String])((a, b) => Cons(a.toString, b))

file17.txt

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

// answer
def map[A,B](as: List[A])(f: A => B): List[B] = 
  foldRightLeft(as, Nil: List[B])((a,b) => Cons(f(a), b))

// 公式のanswer
def map[A,B](l: List[A])(f: A => B): List[B] =
  foldRight(l, Nil:List[B])((h,t) => Cons(f(h),t))

file18.txt

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

// answer 
def filter[A](as: List[A])(f: A => Boolean): List[A] =
  foldRightLeft(as, Nil: List[A])( (a, b) => if (f(a)) Cons(a, b) else b)

// 公式のanswer
def filter[A](l: List[A])(f: A => Boolean): List[A] =
  foldRight(l, Nil:List[A])((h,t) => if (f(h)) Cons(h,t) else t)

file19.txt

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

// answer

// 公式のanswer
def flatMap[A,B](l: List[A])(f: A => List[B]): List[B] =
  concat(map(l)(f))

file2.txt

// Q
EXERCISE 3.2と同じ考えに基づいて、Listの最初の要素を別の値と置き換えるsetHead関数を実装せよ

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

file20.txt

// Q
flatMapを使ってfilterを実装せよ

// answer
def filter[A](as: List[A])(f: A => Boolean): List[A] = flatMap(as)(a => if (f(a)) List(a) else Nil)

// 公式のanswer
def filterViaFlatMap[A](l: List[A])(f: A => Boolean): List[A] =
  flatMap(l)(a => if (f(a)) List(a) else Nil)

file21.txt

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

// answer
def zipWithSum(a: List[Int], b: List[Int]): List[Int] = (a, b) match {
  case (Nil, _) => Nil
  case (_, Nil) => Nil
  case (Cons(h1,t1), Cons(h2,t2)) => Cons(h1+h2,zipWithSum(t1,t2))
}

// 公式のanswer
def addPairwise(a: List[Int], b: List[Int]): List[Int] = (a,b) match {
  case (Nil, _) => Nil
  case (_, Nil) => Nil
  case (Cons(h1,t1), Cons(h2,t2)) => Cons(h1+h2, addPairwise(t1,t2))
}

file22.txt

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

// answer
def zipWith[A,B,C](a: List[A], b: List[B])(f: (A,B) => C): List[C] = (a, b) match {
  case (Nil, _) => Nil
  case (_, Nil) => Nil
  case (Cons(h1,t1), Cons(h2,t2)) => Cons(f(h1,h2),zipWith(t1,t2)(f))
}

// 公式のanswer
def zipWith[A,B,C](a: List[A], b: List[B])(f: (A,B) => C): List[C] = (a,b) match {
  case (Nil, _) => Nil
  case (_, Nil) => Nil
  case (Cons(h1,t1), Cons(h2,t2)) => Cons(f(h1,h2), zipWith(t1,t2)(f))
}

file23.txt

// Q
難問: 例として、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

// 公式のanswer
  @annotation.tailrec
  def startsWith[A](l: List[A], prefix: List[A]): Boolean = (l,prefix) match {
    case (_,Nil) => true
    case (Cons(h,t),Cons(h2,t2)) if h == h2 => startsWith(t, t2)
    case _ => false
  }
  @annotation.tailrec
  def hasSubsequence[A](sup: List[A], sub: List[A]): Boolean = sup match {
    case Nil => sub == Nil
    case _ if startsWith(sup, sub) => true
    case Cons(h,t) => hasSubsequence(t, sub)
  }

file24.txt

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

// answer
def size[A](tr: Tree[A]): Int = tr match {
  case Leaf(_) => 1
  case Branch(a,b) => 1 + size(a) + size(b)
}

// 公式のanswer
def size[A](t: Tree[A]): Int = t match {
  case Leaf(_) => 1
  case Branch(l,r) => 1 + size(l) + size(r)
}

file25.txt

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

// answer
def maximum(tr: Tree[Int]): Int = tr match {
  case Leaf(x) => x
  case Branch(a,b) => maximum(a) max maximum(b) 
}

// 公式のanswer
def maximum(t: Tree[Int]): Int = t match {
  case Leaf(n) => n
  case Branch(l,r) => maximum(l) max maximum(r)
}

file26.txt

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

// answer
def depth[A](t: Tree[A]): Int = t match {
  case Leaf(_) => 0
  case Branch(a,b) => 1 + (depth(a) max depth(b))  
}

// 公式のanswer
def depth[A](t: Tree[A]): Int = t match {
  case Leaf(_) => 0
  case Branch(l,r) => 1 + (depth(l) max depth(r))
}

file27.txt

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

def map[A,B](t: Tree[A])(f: A => B): Tree[B] = t match {
  case Leaf(x) => Leaf(f(x))
  case Branch(a,b) => Branch(map(a)(f),map(b)(f))
}

file28.txt

// Q
size,maximum,depth,mapを一般化し、それらの類似点を抽象化する新しいfold関数を記述せよ。
そして、このより汎用的なfold関数を使ってそれらを再実装せよ。
このfold関数とListの左畳み込み及び右畳み込みの間にある類似性を抽出することは可能か。

// answer 
def fold[A,B](tr: Tree[A])(f1: A => B)(f2: (B,B) => B): B = tr match {
  case Leaf(x) => f1(x)
  case Branch(a,b) => f2(fold(a)(f1)(f2) ,fold(b)(f1)(f2)) 
}

def size[A](tr: Tree[A]): Int = fold(tr)(a => 1)(1 + _ + _)
def maximum(tr: Tree[Int]): Int = fold(tr)(a => a)(_ max _)
def depth[A](tr: Tree[A]): Int = fold(tr)(a => 0)(1 + _ max _)
def map[A,B](tr: Tree[A])(f: A => B): Tree[B] = fold(tr)(f)


// 公式のanswer
def fold[A,B](t: Tree[A])(f: A => B)(g: (B,B) => B): B = t match {
  case Leaf(a) => f(a)
  case Branch(l,r) => g(fold(l)(f)(g), fold(r)(f)(g))
}

def sizeViaFold[A](t: Tree[A]): Int = 
  fold(t)(a => 1)(1 + _ + _)

def maximumViaFold(t: Tree[Int]): Int = 
  fold(t)(a => a)(_ max _)

def depthViaFold[A](t: Tree[A]): Int = 
  fold(t)(a => 0)((d1,d2) => 1 + (d1 max d2))

def mapViaFold[A,B](t: Tree[A])(f: A => B): Tree[B] = 
  fold(t)(a => Leaf(f(a)): Tree[B])(Branch(_,_))

file3.txt

// Q
tailを一般化して、リストの先頭からn個の要素を削除するdropという関数に置き換えよ。
この関数の実行時間は削除する要素の数にのみ比例することに注意。List全体のコピーを作成する必要はない。

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

// 公式の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)
  }

file4.txt

// Q
述語とマッチする場合に限り、Listからその要素までの要素を削除するdropWhileを実装せよ。

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

file5.txt

// Q
すべてがこのようにうまくいくわけではない。Listの末尾を除く全ての要素で構成されたListを返すinit関数を実装せよ。
List(1,2,3,4)が与えられた場合、initはList(1,2,3)を返す。この関数をtailのように一定時間で実装できないのはなぜか。

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

Listが単方向Listであるため、それに至るまでの全ての要素を走査しなければならない。
よって、リストの要素数に応じた処理時間になる。

// 公式の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))
  }

file6.txt

// Q
foldRightを使って実装されたproductは、0.0を検出した場合に、直ちに再帰を中止して0.0を返せるか。その理由を説明せよ。
大きなリストでfoldRightを呼び出した場合の短絡の仕組みについて検討せよ。この問題は奥が深いため、第5章で改めて取り上げる。

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

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

file7.txt

// Q
foldRight(List(1,2,3),Nil:List[Int])(Cons(_,_))のように、NilおよびCons自体をfoldRightに渡した場合はどうなるか。
これがfoldRightとListのデータコンストラクタとの関係について何を表していると思うか。

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

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

file8.txt

// Q
foldRightを使ってリストの長さを計算せよ。

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

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

file9.txt

// Q
このfoldRightの実装は末尾再帰ではなく、リストが大きい場合はStackOverFlowErrorになってしまう。これをスタックセーフではないと言う。
そうした状況であると仮定し、前章で説明した手法を使って、リスト再帰の総称関数foldLeftを記述せよ。シグネチャは以下のとおり
def foldLeft[A,B](l: List[A], z: B)(f: (B, A) => B): B

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