新人SEの学習記録

14年度入社SEの学習記録用に始めたブログです。もう新人じゃないかも…

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

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

関数型データ構造の定義

関数型プログラミングでは、変数を更新したりミュータブルなデータ構造を変更することはない。
では、どのような種類のデータを使用し、定義し、操作するのか?

まずは単方向リストについてみてみる。

// Listデータ型。
// 型パラメータAを指定。+Aは共変なのでAのサブクラスも入る。
// sealedは実装が全てこのファイル内で行われることを宣言する。
// traitは抽象インタフェースを示す。
sealed trait List[+A]

// Listの形式を表す2つの実装。ケースクラスを使用。
// 空のリストを表す実装。
case object Nil extends List[Nothing]
// 空でないリストを表す実装。
case class Cons[+A](head: A, tail: List[A]) extends List[A]

// Listのコンパニオンオブジェクト。
// リストの作成や操作の関数を持つ。
object List {
  // パターンマッチングを使用し、リスト内の整数を足し合わせる
  def sum(ints: List[Int]): Int = ints match {
    case Nil => 0
    case Cons(x, xs) => x + sum(xs)
  }
  // Aの可変長引数をとり、Listを返す関数
  def apply[A](as: A*): List[A] =
    if (as.isEmpty) Nil
    else Cons(as.head, apply(as.tail: _*))
}

上記の実装により、Listの作成時にはNilを使って空のリストを作成するか、
Consを持ちて空ではないリストを作成できる。
Consはconstructの略で、空ではない最初の要素headと残りの要素のListであるtailで構成される。

val ex1: List[Double] = Nil
val ex2: List[Int] = Cons(1, Cons(2, Nil))
List.sum(ex2) // => 6

パターンマッチング

上記のプログラムにおけるobject ListはListのコンパニオンオブジェクトとも呼ばれる。
データ型の作成時には、コンパニオンオブジェクトにデータ型を作成または操作するための関数を定義するのが慣例。
リストの操作を行うモジュールFooを作っても良いが、名前をListにした方がわかりやすい。

さて、このコンパニオンオブジェクトに含まれるsum関数では、パターンマッチングが使われている。

  // パターンマッチングを使用し、リスト内の整数を足し合わせる
  def sum(ints: List[Int]): Int = ints match {
    case Nil => 0
    case Cons(x, xs) => x + sum(xs)
  }

sum関数では、空のリストの合計が0であること、
空でないリストの合計が最初の要素xに残りの要素xsの合計を足したものであることが示されている。
これは再帰定義であり、再帰データ型を操作する関数を記述するときによく利用される。

パターンマッチングは高度なswitch文のようなもので、
調べている式(上の例ではints)の構造の中に入り、構造から部分式を取り出すことができる。
ここで、intsはターゲットまたは被検査体と呼ばれる。
各ケースはCons(x, xs)といった左辺のパターンと、x + sum(xs)といった右辺の結果で構成される。
ターゲットがケースのパターンとマッチする場合、右辺の結果がマッチ式全体の結果となる。

パターンマッチングの例をもう少しみてみる。

  • List(1,2,3) match { case _ => 42 } は42になる。
  • List(1,2,3) match { case Cons(h,_) => h } は1になる。
  • List(1,2,3) match { case Cons(_,t) => t } はList(2,3)になる。
  • List(1,2,3) match { case Nil => 42 } はMatchErrorになる。
Excercise

以下のマッチ式の結果を求めろ。

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, 2, 4, ...)となる部分式はないので、マッチせず
  • Nilはないので、マッチせず
  • (x, y, 3, 4, ...)となる部分式(1, 2, 3, 4, ...)が存在するので、結果はx + y = 1 + 2 = 3
  • 以降は既にマッチしているので引っかからず

ということで、結果は3。