2009年04月15日

なぜ関数型言語を使うのか→一言で言うと単純且つ強力だから((c) E. Sumii)

なぜ関数型言語を使うのか(再掲・追記)

(この文章は以前(2005-5-15)に書いた記事を再編集して再掲するものです。)

Red-black treeは、平衡木の一種である。その実装は2-3-4木に等しいが、データ構造はより簡便である。

さて、その挿入を実装することを考えよう。Haskellでは、このように書ける。(情報元:sampou.org)

挿入のためには、平衡操作(木の分割と回転)を実装する必要がある。

balance :: RB a -> a -> RB a -> RB a
balance (T R a x b) y (T R c z d) = T R (T B a x b) y (T B c z d)
balance (T R (T R a x b) y c) z d = T R (T B a x b) y (T B c z d)
balance (T R a x (T R b y c)) z d = T R (T B a x b) y (T B c z d)
balance a x (T R b y (T R c z d)) = T R (T B a x b) y (T B c z d)
balance a x (T R (T R b y c) z d) = T R (T B a x b) y (T B c z d)
balance a x b = T B a x b

これに対し、ほとんど同じ実装で私が書いたC++のコードは次のようになる:

  static void rechain(node*& nref, node* less, node* middle, node* greater, node* ll, node* lr, node* rl, node* rr){
    nref = middle;
    middle  -> color = RED;
    middle  -> left  = less;
    middle  -> right = greater;
    less    -> color = BLACK;
    less    -> left  = ll;
    less    -> right = lr;
    greater -> color = BLACK;
    greater -> left  = rl;
    greater -> right = rr;
  }
 
  static void balance(node*& nref){
    // if, tree structure is R (_, _), just ignore and come back later
    if(nref -> color == RED) return;
 
    node *child, *gchild, *ochild;
    // all "4-node"s should be rebalanced to R(B, B)
    if((child = (nref -> left)) && child -> color == RED){
      // B (R, R)
      if((ochild = (nref -> right)) && ochild -> color == RED){
        nref -> color = RED;
        child -> color = BLACK;
        ochild -> color = BLACK;
        return;
      }
 
      // B (R (R, _), _)
      if((gchild = (child -> left)) && gchild -> color == RED){
        rechain(nref, gchild, child, nref,
                gchild -> left, gchild -> right,
                child -> right, nref -> right);
        return;
      }
      // B (R (_, R), _)
      if((gchild = (child -> right)) && gchild -> color == RED){
        rechain(nref, child, gchild, nref,
                child -> left, gchild -> left,
                gchild -> right, nref -> right);
        return;
      }
    }
    if((child = (nref -> right)) && child -> color == RED){
      // B (_, R (R, _))
      if((gchild = (child -> left)) && gchild -> color == RED){
        rechain(nref, nref, gchild, child,
                nref -> left, gchild -> left,
                gchild -> right, child -> right);
        return;
      }
      // B (_, R (_, R))
      if((gchild = (child -> right)) && gchild -> color == RED){
        rechain(nref, nref, child, gchild,
                nref -> left, child -> left,
                gchild -> left, gchild -> right);
        return;
      }
    }
  }

#rotate操作に直すともう少し簡潔に書ける。

読者の多くは、もう何が言いたいかわかったと思う。パターンマッチは偉大である。

僕には、なぜ、アルゴリズムを教えようとする教師がJavaやCを好んで使いたがるのかが理解できない。C系列の手続き型言語は、すべからく(僕が好んで使うC++を含めて)トリビアルな部分で異様なほど時間をとられ、アルゴリズムそのものの勉強に使える時間はきわめて限定されてしまうのに。

(再掲:月記/2005-4-18)
 あなたが難しい問題を解こうとしているなら、 問われているのはパワフルな言語を使うか使わないか、ではない。 
 (a)パワフルな言語を使うか 
 (b)パワフルな言語と等価なインタプリタを書くか 
 (c)自らがパワフルな言語の人間コンパイラとなるか
 、という選択なのだ。

(追記)Scalaでの実装。みずしまさんのツッコミを受けて修正。

  abstract class Node
  case class Leaf() extends Node
  case class R(left: Node, key: int, right: Node) extends Node
  case class B(left: Node, key: int, right: Node) extends Node

  def balance(left: Node, key: int, right: Node) = {
    (left, key, right) match {
      case (R(a, x, b), y, R(c, z, d)) => R(B(a, x, b), y, B(c, z, d))
      case (R(R(a, x, b), y, c), z, d) => R(B(a, x, b), y, B(c, z, d))
      case (R(a, x, R(b, y, c)), z, d) => R(B(a, x, b), y, B(c, z, d))
      case (a, x, R(b, y, R(c, z, d))) => R(B(a, x, b), y, B(c, z, d))
      case (a, x, R(R(b, y, c), z, d)) => R(B(a, x, b), y, B(c, z, d))
      case _ => B(left, key, right)
    }
  }

ちなみに、私は以前教授Aに「データ構造の教育には関数型言語を使うのもアリじゃないですかね」と言ったところ、その話を聞いた別の教授Bから鼻で笑われたことがあって、それ以来ずっと根に持っている :P 。

posted by chun at 15:20| 日記