読者です 読者をやめる 読者になる 読者になる

新人SEの学習記録

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

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

学習記録 Scala 関数型 プログラミング

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

関数型データ構造でのデータ共有

イミュータブルなデータでは、例えばリストxsの先頭に要素1を追加したい場合には、新しいリスト(Cons(1, xs))を返すことで実現する。
ここでは悲観的なコピーは作成する必要はなく、リストはイミュータブルなのでxsを再利用するだけでよい。
これをデータ共有(data sharing)と呼ぶ。
逆にmylist = Cons(x, xs)から先頭の要素を削除したい場合、xsを返すだけで、実際に削除は発生しない。
元のリストであるmylistは以前として利用可能で、元のまま(Cons(x, xs))である。

Exercise 3.2
  • Listの最初の要素を削除する関数tailを実装せよ。

というわけで書いてみた。

  def tail[A](l: List[A]): List[A] = l match {
    case Nil => Nil
    case Cons(x, Nil) => Nil
    case Cons(x, xs) => xs
  }

ListがNilならNilを、Listの要素が1個だけならNilを、2個以上なら後ろの要素を返す。
解答は以下。

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

先の下二つのケースはCons(_, t)でまとめることができたようだ。
また、ここではListがNilだった場合は例外を投げている。
多くの場合、空のリストの末尾をとろうとすること自体がバグであり、それをわかるようにするためとのこと。

Exercise 3.3
  • Listの最初の要素を別の値と置き換えるsetHead関数を実装せよ。
  def setHead[A](l: List[A], h: A): List[A] = l match {
    case Nil => Cons(h, Nil)
    case Cons(_, t) => Cons(h, t)
  }

解答ではcase Nilでは例外を投げていた。

データ共有の効率性

データ共有を使うと、より効率的に処理を実行できることがよくある。

Exercise 3.4
  • tailを一般化して、リストの先頭からn個の要素を削除するdropに置き換えよ。

書いてみた。

  def drop[A](l: List[A], n: Int): List[A] = n match {
    case 0 => l
    case _ => drop(tail(l), n-1)
  }

nにマイナスの値を入れられたら無限ループになるとか、
tailを一般化しろという問題でtailを使うのはどうなのとか色々問題あり。
解答は以下。

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

if〜elseでもmatchは使える模様。
nが0以下ならlを返すことで無限ループも無く、
またcase Nilの時点でNilを返すことでnが大きい数でもListがNilになった時点ですぐ結果を返すことができる。

Exercise 3.5
  • 述語とマッチする場合に限り、Listからその要素までの要素を削除するdropwhileを実装せよ。
  def dropWhile[A](l: List[A], f: A => Boolean): List[A] = l match {
    case Nil => Nil
    case Cons(h, t) =>
      if(f(h)) dropWhile(t, f)
      else l
  }

ListがCons(h, t)で、かつf(h)がtrueならば、再度dropWhileをtailを引数に呼び出す。
解答ではもっと良い書き方をしていた。

  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
    }

case の後、=>の前にif を書くことで、caseに条件式を付けることができる(パターンガード)。
上のプログラムでは、リストlがCons(h, t)でかつf(h)がtrueならばdropWhile(t,f)を呼ぶ、ということを1行で表している。
リストlがCons(h, t)であっても、f(h)がfalseであれば次のパターンマッチング(case _)を行うため、より簡潔に記述できている。

データ共有の意外な例

次の関数は、あるリストの全ての要素を別のリストの最後に追加する。

def append[A](a1: List[A], a2: List[A]): List[A] = a1 match {
  case Nil => a2
  case Cons(h, t) => Cons(h, append(t, a2))
}

この定義では、最初のリストが尽きるまで値をコピーし、残りはa2を参照するだけとなる。
よって、実行時間とメモリ使用量はa1の長さのみによって決まる。
2つの配列に対して同様のことを行おうと思うと、両方の配列の要素をコピーする必要があり、単方向リストの方が効率的である。

Exercise 3.6
  • Listの末尾を除くすべての要素で構成されたListを返すinit関数を実装せよ。

書いてみた・・・けどまた何かイマイチな気がする。

  def init[A](l: List[A]): List[A] = l match {
    case Nil => Nil
    case Cons(x, Nil) => Nil
    case Cons(h, t) => Cons(h, init(t))
  }

と思ったが解答もこんなもんだった。
単方向リストの構造ゆえに、「末尾を置き換える」という処理は末尾より前のConsオブジェクトを全てコピーする必要がある(※)。

※val x = List(1,2,3,4,5)に対し、init(x)を呼ぶと、List(1,2,3,4)が返ってくる。
x = List(1,2,3,4,5)というデータは変更できず、append(a1,a2)と違い共有データが持てないため、
List(1,2,3,4)を作りだすには、Consオブジェクトを末尾の(5, Nil)以外全てコピーする必要がある。

つまり、様々な操作を効率よく行うデータ構造を記述するには、データ共有をうまく利用する方法を見つけ出す必要がある。
Scalaの標準ライブラリに含まれるVectorは、一定時間でのランダムアクセス/更新/head/tail/init/先頭または末尾への追加が可能。