新人SEの学習記録

14年度入社SEの学習記録用に始めたブログです。気づけば社会人3年目に突入。

学習記録:Scala関数型デザイン

第3章:関数型プログラミングのデータ構造(続き)

標準ライブラリのリスト

Scalaには標準ライブラリにListが存在し、後の章ではこの標準ライブラリのListを使用する。
ここまでで作成してきたListと標準ライブラリのListとの主な違いは、Consが::として参照され右結合になることである。
つまり、List(1,2) = Cons(1, Cons(2, Nil))は1 :: 2 :: Nilと記述する。

また、標準ライブラリのリストには便利なメソッドが多く存在する。

  • take(n: Int): List[A] … thisの最初のn個から成るリストを返す
scala> var x = List(1,2,3,4,5,1,2,3)
x: List[Int] = List(1, 2, 3, 4, 5, 1, 2, 3)
scala> x.take(5)
res2: List[Int] = List(1, 2, 3, 4, 5)
  • takeWhile(f: A => boolean): List[A] … 全ての要素がfの条件を満たす有効な部分リストを作成し、そのうち最も長いものを返す
scala> var x = List(1,2,3,4,5,1,2,3)
x: List[Int] = List(1, 2, 3, 4, 5, 1, 2, 3)
scala> x.takeWhile(_ <= 4)
res3: List[Int] = List(1, 2, 3, 4)
  • forall(f: A => Boolean): Boolean … thisのすべての要素がfの条件を満たす場合にのみtrueを返す
  • exists(f: A => Boolean): Boolean … thisのいずれかの要素がfの条件を満たす場合trueを返す
scala> var x = List(1,2,3,4,5,1,2,3)
x: List[Int] = List(1, 2, 3, 4, 5, 1, 2, 3)
scala> x.forall(_ <= 5)
res4: Boolean = true

scala> x.forall(_ > 1)
res5: Boolean = false

scala> x.exists(_ > 1)
res6: Boolean = true

scala> x.exists(_ > 5)
res7: Boolean = false
より単純なコンポーネントからリスト関数を組み立てるときの非効率性

Listの問題の一つに、汎用的な関数により演算やアルゴリズムを表現できることが多い反面、
結果として得られる実装が必ずしも効率的でないことが挙げられる。

例えば、同じ入力に対するパスを複数作成しなければならないことや、途中で抜けることができるように再帰ループを記述しなければならないことがある。

Exercise 3.24
  • Listに別のListがサブシーケンスとして含まれているかどうかを調べるhasSubsequenceを実装せよ。

例えば、List(1,2,3,4)にはサブシーケンスとしてList(1,2), List(3,4), List(4)などが含まれている。

とりあえず思いついた一番それっぽいものを書いてみる。

  def subSequence[A](sup: List[A], sub: List[A]): Boolean =
    (sup,sub) match {
      // 先頭同士が等しく、sub側の後ろがNilなら検索終了してtrueを返す
      case (Cons(h1,t1),Cons(h2,t2)) if (h1 == h2 && t2 == Nil) => true
      // 先頭同士が等しく、subの検索する文字がまだあるなら続いて検索する
      case (Cons(h1,t1),Cons(h2,t2)) if (h1 == h2) => subSequence(t1, t2)
      // 先頭同士が等しくなければ、supの後ろとsubを比較
      case (Cons(h1,t1),Cons(h2,t2)) => subSequence(t1, sub)
      // どちらかが先にNilになったらfalse (下の方はいらないかも?)
      case (Nil, _) => false
      case (_, Nil) => false
    }

だが、これはうまく動かず。
というのも、先頭同士が等しくない場合、もう一度「関数に最初に渡したsub」を使う必要があるが、
上記の関数では再帰時にsubは既に最初とは異なる(短い)Listになっているため。

例えば、List(1,2,3,4,5)に対してList(1,2)が存在することは求められるが、

scala> List.subSequence(List(1,2,3,4,5), List(1,2))
res14: Boolean = true

同様に、List(1,5)に対してもtrueを返してしまう。

scala> List.subSequence(List(1,2,3,4,5), List(1,5))
res15: Boolean = true

ということで、苦肉の策として、最初に渡したsubをずっと保存しておく引数bkupを作り、
それにより再検索する際にsubをbkupで復元する。
これでちゃんと動く。でもめちゃくちゃ格好わるい。。。

  def subSequence[A](sup: List[A], sub: List[A], bkup: List[A]): Boolean =
    (sup,sub) match {
      case (Cons(h1,t1),Cons(h2,t2)) if (h1 == h2 && t2 == Nil) => true
      case (Cons(h1,t1),Cons(h2,t2)) if (h1 == h2) => subSequence(t1, t2, bkup)
      case (Cons(h1,t1),Cons(h2,t2)) =>	subSequence(t1, bkup, bkup)
      case (Nil, _) => false
      case (_, Nil) => false
    }

解答では、先頭同士が等しかった場合、その後の検索処理を別の関数にやらせていた。
検索処理を他の関数にやらせるようにして自分で書いたのが以下。

  def startWith[A](l: List[A], search: List[A]): Boolean =
    (l, search) match {
      case (Cons(h1,t1),Cons(h2,t2)) if (h1 == h2 && t2 == Nil) => true
      case (Cons(h1,t1),Cons(h2,t2)) if (h1 == h2) => startWith(t1, t2)
      case _ => false
    }

  def subSequence2[A](sup: List[A], sub: List[A]): Boolean =
    (sup,sub) match {
      case (Cons(h1,t1),Cons(h2,t2)) if (h1 == h2) => startWith(sup, sub)
      case (Cons(h,t), _)  => subSequence2(t, sub)
      case _ => false
    }

そして解答は以下。
こっちの方がsupがNilだったときの処理があったり、if文のガードが洗練されている。

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

ツリー

Listは代数的データ型と呼ばれるものの一つだが、紛らわしいことに代数的データは抽象データ型を表すために使用されることがある。
代数的データ型は、1つ以上のデータコンストラクタによって定義されるデータ型であり、
コンストラクタはそれぞれ0個以上の引数を受け取る。
データ型がそのデータコンストラクタの和であり、各データコンストラクタがその引数の積であることから、代数的と呼ばれる。

代数的データ型は、他のデータ構造の定義に使用できる。
例として、単純な二分木データ構造を定義してみる。

sealed trait Tree[+A]
// 木の最下層である葉を表す。値を持つ
case class Leaf[A](value: A) extends Tree[A]
// 木の幹を表す。左と右のツリーへの参照を持つ
case class Branch[A](left: Tree[A], right: Tree[A]) extends Tree[A]
Exercise 3.25
  • 二分木のノード(LeafとBranch)の数を数えるsize関数を記述せよ。

Leafなら+1を、Branchならleftとrightで再帰かつ+1をしていけばOK。

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

実際に呼ぶとこんな感じ。

scala> var x = Branch(Branch(Leaf(1), Leaf(2)), Leaf(3))
x: Branch[Int] = Branch(Branch(Leaf(1),Leaf(2)),Leaf(3))

scala> Tree.size(x)
res42: Int = 5
Exercise 3.26
  • Tree[Int]の最大の要素を返すmaximum関数を記述せよ。

x.max(y)で2つの整数xとyを比較できる。
Branchの場合「左の最大値.max(右の最大値)」を呼ぶことで最大の要素を取得できる。

  def maximum(t: Tree[Int]): Int =
    t match {
      case Leaf(v) => v
      case Branch(l, r) => maximum(l).max(maximum(r))
    }
}

呼ぶとこんな感じ。

scala> var x = Branch(Branch(Leaf(1), Leaf(2)), Leaf(3))
x: Branch[Int] = Branch(Branch(Leaf(1),Leaf(2)),Leaf(3))

scala> Tree.maximum(x)
res43: Int = 3

scala> var x = Branch(Branch(Leaf(5), Leaf(9)), Leaf(1))
x: Branch[Int] = Branch(Branch(Leaf(5),Leaf(9)),Leaf(1))

scala> Tree.maximum(x)
res44: Int = 9
Exercise 3.27
  • 二分木のルートから任意のLeafまでの最長パスを返すdepth関数を記述せよ。
  def depth[A](t: Tree[A]): Int	=
    t match {
      case Leaf(_) => 1
      case Branch(l, r) => (1 + depth(l)).max(1 + depth(r))
    }

解答ではルートを深さ0としていたのでcase Leaf(_)のときは0を返していた。
また、(1 + depth(l)).max(1 + depth(r))は1 + (depth(l).max(depth(r))にまとめられていた。

Exercise 3.28
  • 二分木の各要素を特定の関数を使って変更するmap関数を記述せよ。

「二分木の各要素」というのがBranchも指すのかわからなかったため混乱したが、
関数fを適用するのはLeafに対してだけということで良いらしい。

  def map[A,B](t: Tree[A])(f: A => B): Tree[B] =
    t match {
      case Leaf(v) => Leaf(f(v))
      case Branch(l, r) => Branch(map(l)(f), map(r)(f))
    }

実際に使うとこんな感じ。

scala> var x = Branch(Branch(Leaf(5), Branch(Leaf(9), Leaf(3))), Leaf(1))
x: Branch[Int] = Branch(Branch(Leaf(5),Branch(Leaf(9),Leaf(3))),Leaf(1))

scala> Tree.map(x)((a) => a + 1)
res2: Tree[Int] = Branch(Branch(Leaf(6),Branch(Leaf(10),Leaf(4))),Leaf(2))
Exercise 3.29
  • size,maximum,depth,mapを一般化し、それらの類似点を抽象化する新しいfold関数を記述せよ。

ListのときのfoldRightを参考に…やってみたがダメだった。
foldには二つの関数が必要で、Leafに対して行う関数fとBranchに対して行う関数gの二つが必要。

  def fold[A,B](t: Tree[A])(f: A => B)(g: (B,B) => B): B =
    t match {
      case Leaf(v) => f(v)
      case Branch(l, r) => g(fold(l)(f)(g), fold(r)(f)(g))
    }

こうすることで、今まで実装してきた全ての関数をfoldを使って実装できる。

  def size2[A](t: Tree[A]): Int =
    fold(t)(_ => 1)((l, r) => l + r + 1)

  def maximum2(t: Tree[Int]): Int =
    fold(t)(v => v)((l,	r) => l.max(r))

  def depth2[A](t: Tree[A]): Int =
    fold(t)(_ => 0)((l,	r) => 1	+ l.max(r))

map関数のみ少し特殊で、関数fに注釈が必要。

  def map2[A,B](t: Tree[A])(f: A => B): Tree[B] =
    fold(t)(v => Leaf(f(v)): Tree[B])((l, r) => Branch(l, r))

このTree[B]の注釈がないと、以下のエラーになる。

<console>:53: error: type mismatch;
 found   : Branch[B]
 required: Leaf[B]
           fold(t)(v => Leaf(f(v)))((l, r) => Branch(l, r))

注釈がないと関数fの戻り値がLeaf[B]と認識されるので、結果的に関数gの戻り値もLeaf[B]だと期待されてしまう。
だが、実際には関数gはBranch[B]を返さなければならない。
ここで、fの戻り値がTree[B]であると注釈をつけると、Leaf[B]とBranch[B]のどちらにも対応ができる。

まとめ

本章では、代数的データ型とパターンマッチングを紹介し、単方向リストを含む純粋関数型のデータ構造を実装する方法を示した。