Purely Functional Data Structures: 第２章

Exercises.md

Excercises

スケイラですみません(◞‸◟) もちがってる可能性があります。

Exercise 2.1

def suffixes[A](xs: List[A]): List[List[A]] = xs match {
  case Nil => List(Nil)
  case _ :: tail => xs :: suffixes(tail)
}

Exercise 2.2

def member22(x: Int, tree: BinarySearchTree): Boolean = member22(x, tree, None)

@annotation.tailrec
private def member22(x: Int, tree: BinarySearchTree, candidate: Option[Int]): Boolean = {
  tree match {
    case Node(left, y, _) if x < y => member22(x, left, candidate)
    case Node(_, y, right) if x >= y => member22(x, right, Some(y))
    case Empty =>
      candidate match {
        case Some(`x`) => true
        case _ => false
      }
  }
}

Exercise 2.3

def insert23(x: Int, tree: BinarySearchTree): BinarySearchTree = try {
  insert23OrError(x, tree)
} catch {
  case e: RuntimeException => tree
}

private def insert23OrError(x: Int, tree: BinarySearchTree): BinarySearchTree = tree match {
  case Node(left, y, right) if x < y => Node(insert(x, left), y, right)
  case Node(left, y, right) if x > y => Node(left, y, insert(x, right))
  case Node(_, `x`, _) => throw new RuntimeException("already exists.")
  case Empty => Node(Empty, x, Empty)
}

Exercise 2.4

def insert24(x: Int, tree: BinarySearchTree): BinarySearchTree = try {
  insert24OrError(x, tree, None)
} catch {
  case e: RuntimeException => tree
}

private def insert24OrError(x: Int, tree: BinarySearchTree, candidate: Option[Int]): BinarySearchTree = {
  tree match {
    case Node(left, y, right) if x < y => Node(insert24OrError(x, left, candidate), y, right)
    case Node(left, y, right) => Node(left, y, insert24OrError(x, right, Some(y)))
    case Empty => candidate match {
      case Some(`x`) => throw new RuntimeException("already exists.")
      case _ => Node(Empty, x, Empty)
    }
  }
}

Exercise 2.5 (a)

sealed abstract class BinaryTree
case object Empty extends BinaryTree
case class Node(left: BinaryTree, elem: Int, right: BinaryTree) extends BinaryTree

object BinaryTree {
  def complete(x: Int, depth: Int): BinaryTree = depth match {
    case 0 => Empty
    case n =>
      val subTree = complete(x, depth - 1)
      Node(subTree, x, subTree)
  }
}

Exercise 2.5 (b)

def create(x: Int, size: Int): BinaryTree = size match {
  case 0 => Empty
  case 1 => Node(Empty, x, Empty)
  case n if n % 2 == 0 =>
    val (left, right) = create2(x, (n - 1) / 2)
    Node(left, x, right)
  case n =>
    val subTree = create(x, (n - 1) / 2)
    Node(subTree, x, subTree)
}

private def create2(x: Int, size: Int): (BinaryTree, BinaryTree) = {
  (create(x, size), create(x, size + 1))
}

Exercise 2.6

• TreeMapにすればいい
  • NodeはKey-Valueペアを持つ
  • 木はKeyのOrderingを持つ

pfds-ch2.md

2 Persistence

• 関数型データ構造の特徴は、それらが必ず 永続的 である、ということである
  • 関数型データ構造の更新は非破壊的で、更新前のバージョンと更新後のバージョンが共存できる
  • この永続性は、更新の影響を受けるノードのみ コピー し、それに対して変更を加える事で実現する
    • ノードが直接変更されることはないので、更新の影響を受けない箇所は更新前と更新後のバージョンで安全に 共有(share) することができる
• この章ではListと二分探索木を用いて、コピーと共有について説明する

2.1 Lists

• まずは連結リストから始める
  • このデータ構造は命令型プログラミングにおいて一般的なもので、関数型プログラミングにおいてもよく使用される
  • Listがサポートする関数(cons, head, tail)は本質的にはスタックの抽象と同じである(Figure 2.1)
    • ↑全部O(1)
    • Figure 2.1のStack signatureの中では、Stackの用語(push, top, pop)でなくListの用語(cons, head, tail)が使用されている
    • これはStackをシーケンスインスタンスの一種(他にはQueueやDequeやcatenable listsもそう)であるとみなせるからである
    • 我々はこれらの abstraction に対する関数に、同じような方針で命名を行う
      • そうすることで異なる実装同士を手間なく置き換えることができる

命令型++

• もう一つのよくあるリストに関する関数は、 ++
  • 2つのリストを連結する操作(zs = xs ++ ys)
  • この操作は命令型の実装であれば、O(1)の時間で実行できる(Figure 2.4)
    1. Listごとに最初と最後のノードへのポインタを保持する
    2. 一つ目のListの最後のノードが、２つ目のListの最初のノードを参照するようにする
  • ただし、この操作は引数となるList両方を破壊し、二度と使えないようにする
    • (疑問) xsは最後のノードの状態が更新されるから壊れるけど、ysは別に壊れはしない？

public class MyList<A> {
	private class Node {
		A elem;
		Node next;

		Node(A elem, Node next) {
			this.elem = elem;
			this.next = next;
		}
	}

	private Node head;
	private Node last;

	public MyList<A> append(MyList<A> other) {
		if (last == null) {
			return other;
		} else {
			last.next = other.head;
			last = other.last;
			return this;
		}
	}

	// その他methods
}

関数型++

• 一方、関数型プログラミングでは、このような破壊的な変更を行うことができない(Figure 2.5)
  1. 最初のListの最後のcellを コピー し、そのtail pointerを変更する
  2. 最後から２番目のcellコピーし、↑でコピーしたcellを参照するようにする
  3. この操作を、最初のListをコピーし終えるまで繰り返す

def ++[A](xs: List[A], ys: List[A]): List[A] = xs match {
  case Nil => ys
  case head :: tail => head :: ++(tail, ys)
}

• 永続的だが、O(n)かかる
  • 10章及び11章にて、永続性を失うことなく、「++」をO(1)で実現する方法を示す
• 多くのコピーが発生してしまっていることは否定出来ないが、ysのコピーを行う必要がないことに注目されたい
  • コピーする代わりに、ysのノードをysとzsが共有している
• update(与えられたindexを持つノードを更新する関数)も、「コピーと共有」というコンセプトを体現することができる(Figure 2.6)
  • リスト全体をコピーすることなく、変更したいノードと、そのノードを直接的、あるいは間接的に参照しているノードのみコピーしている
    • 言い換えると、一つのノードを修正するために、rootからそのノードまでのすべてのノードを更新している
    • この経路上にないノードはすべて、更新前のバージョンと更新後のバージョンで共有されている
• このスタイルのプログラミングは、自動GCのおかげで単純化されている
  • 必要でなくなったコピーのために使用されている空間は再利用されたいが、ノードが広く共有されていると、手動GCはつらい
  • どんなプログラムでもGCがないと私はつらい

Exercise 2.1

• Listを受け取り、そのListすべてのsuffixのListからなるListを返す関数「suffixes」をつくろう
  • suffixのListは長さの降順(例: [1, 2, 3, 4] -> [[1, 2, 3, 4], [2, 3, 4], [3, 4], [4], []])となる
  • 時間・空間計算量はO(n)

2.2 Binary Search Trees

• それぞれのノードが2つ以上のポインタを持てば、より難しい共有のパターンを実現できる
  • 二分探索木はこの種の共有を示すためのよい例である
• Binary search trees are binary trees with elements stored at the interior nodes in symmetric order
  • datatype Tree E | T of Tree x Elem x Tree
  • ノードの値は左側の部分木に属するすべての値より必ず大きく、また右側の部分木に属するすべての値より小さい
• 二分探索木は要素の型に関してポリモーフィックでない
  • 要素同士に全順序関係がなければならない
  • かといって、型ごとに二分探索木を定義する必要があるというわけではない。 functor とかいう仕組みでいける(Figure 2.9)
• この章では二分探索木を用いてSetを実装してみる
  • Tにさらなるフィールドを追加すれば、Finite Mapのような abstraction や、「i番目に小さな要素を返す」といった関数を実装することもたやすく可能

Set

• Setの最小のインターフェース(Figure 2.7)
  • 値: empty(空集合)
  • 関数: insert(挿入)、member(指定した要素が含まれるか否か判定)
  • より現実的な実装だと、要素の削除や要素の列挙、といった関数が追加されるだろう
• member関数はクエリ要素を木の根の要素と比較していくことで検索を行う(O(log n))
  • クエリ要素が根の要素より小さければ、左の部分木を再帰的に検索する
  • 大きければ、右の部分木を同じように再帰的に検索する
  • クエリ要素が根の要素と一致していればtrueを返す
  • 空ノードにたどり着く(= 指定した要素が集合内に存在しない)と、falseを返す
• insert関数はmember関数と同じようにツリーを検索するが、たどっていく途中にあるすべてのノードをコピーしていく(O(log n))(Figure 2.8)
  • 空ノードにたどり着くと、そのノードを、挿入したい要素を含んだノードに差し替える
  • コピーされるノードは、検索パス上にない方の部分木を元のツリーと共有する
    • 多くの場合、検索パスはツリー上にあるうちの一部のノードしか含まないので、多くのノードは共有されるサブツリーたちに含まれている

sealed abstract class BinarySearchTree
case object Empty extends BinarySearchTree
case class Node(left: BinarySearchTree, elem: Int, right: BinarySearchTree) extends BinarySearchTree

object BinarySearchTree {
  def member(x: Int, tree: BinarySearchTree): Boolean = tree match {
    case Node(left, y, _) if x < y => member(x, left)
    case Node(_, y, right) if x > y => member(x, right)
    case Node(_, `x`, _) => true
    case Empty => false
  }

  def insert(x: Int, tree: BinarySearchTree): BinarySearchTree = tree match {
    case Node(left, y, right) if x < y => Node(insert(x, left), y, right)
    case Node(left, y, right) if x > y => Node(left, y, insert(x, right))
    case Node(_, `x`, _) => tree
    case Empty => Node(Empty, x, Empty)
  }
}

Exercise 2.2

• 最悪のケースで、member関数は木の深さ d に対して約 2d 回の比較を行う必要がある
• d + 1 回以下の比較ですむようにmember関数を書き直せ
  1. クエリ要素と同じ かもしれない 要素をキープする
     • 「<」による比較がfalseを返し、「>=」による比較がtrueを返す最後の要素
  2. 末端に辿り着いた時点で、その候補と等価性を比較する

Exercise 2.3

• すでに存在する要素をinsertすると、元のツリーと等価なツリーとなるにも関わらずコピーが発生してしまう
• 例外を使用して、コピーを避けるよう書き直せ
  • イテレーションごとにハンドリングするのではなく、insert 1回に対して1度のみハンドリングするようにせよ

Exercise 2.4

• 上記2つを組み合わせて、不必要なコピーが発生せず、かつ d + 1 回以下の比較ですむinsert関数を実装せよ

Exercise 2.5

• オブジェクト間での共有は便利だが、ひとつのオブジェクトの中で共有を用いることもまた便利である
  • あるノードに与えられた2つの部分木が同じものであるならば、それらは同じ木として表現することができる

Exercise 2.5 (a)

• 上記のアイデアを用いて、要素と深さを受け取り、↓の条件を満たす二分木を返す関数 complete(Elem x int -> Tree)を実装せよ
  • complete(element, depth)
  • すべてのノードが「element」を保持する、深さ「depth」の完全二分木
  • O(depth)の時間で動く

Exercise 2.5 (b)

• 任意のサイズの平衡二分木を作成できるよう、この関数を拡張せよ
  • この木は必ずしも完全二分木でなくてもよいが、できるだけバランスしていなければならない
    • サイズの差が1より大きな2つの部分木を持つノードがあってはならない
  • この関数はO(log n)の時間で動く
  • (ヒント: サイズmを与えられると、サイズmの木とサイズm + 1の木を返すヘルパー関数を使いましょう)

Exercise 2.6

• UnbalancedSet functorを、Finite Map(Figure 2.10)を扱えるようにせよ

2.3 Chapter Notes

• 省略

まとめ

• コピーはすくなく、共有はできるだけ多くできるよう工夫しましょう