(cache) Ruby でパターンマッチ

2010-05-22

■[Ruby] Ruby でパターンマッチ

で紹介されている implicit future が Ruby に欲しい！

# promise を作る
x = Promise.new
a = [1, x, 2, x, 3, x]

# 今はまだ値になっていない
p a #=> [1, _promise_, 2, _promise_, 3, _promise_]

# この promise は 42 に決めた！ (代入ではないよ)
x === 42

# x の箇所は勝手に 42 になっている
p a #=> [1, 42, 2, 42, 3, 42]

というのも、これがあれば Ruby でパターンマッチができる気がするんですよね。こんな感じに。

# 何にでもマッチする箇所には _ と書く (実体は Promise.new)
def _
  Promise.new
end

# + と定数だけからなる抽象構文木 (二分木)
Sum   = Struct[:left, :right]
Const = Struct[:value]

# ... を評価する関数 (ここが重要！)
def eval(n)
  case n
  when Sum[l = _, r = _] then eval(l) + eval(r)
  when Const[v = _] then v
  end
end

# ... で (1+2)+(3+4) を評価する
p eval(Sum[Sum[Const[1], Const[2]], Sum[Const[3], Const[4]]])  #=> 10

case 文が内部的に Sum[l = _, r = _] === n を実行してくれるのがミソ。例えば n が Sum[1, 2] とかだったら、l === 1 と r === 2 が実行されるので *1 、l と r がそれぞれ 1 と 2 になる。

素敵ですよねー。

def eval(n)
  case n
  when Sum then eval(n.left) + eval(n.right)
  when Const then n.value
  end
end

の方が分かりやすいって？この程度の例ではそうかもしれないんだけれど、よくパターンマッチの強力さを示す例としてあげられる赤黒木の balance を見ると、

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

Red Black Trees

Haskell の↑が、↓の Ruby になる。

def balance(l, v, r)
  case [l, v, r]
  when [T[:R,T[:R,a=_,x=_,b=_],y=_,c=_],z=_,d=_]; T[:R,T[:B,a,x,b],y,T[:B,c,z,d]]
  when [T[:R,a=_,x=_,T[:R,b=_,y=_,c=_]],z=_,d=_]; T[:R,T[:B,a,x,b],y,T[:B,c,z,d]]
  when [T[:R,a=_,x=_,b=_],y=_,T[:R,c=_,z=_,d=_]]; T[:R,T[:B,a,x,b],y,T[:B,c,z,d]]
  when [a=_,x=_,T[:R,T[:R,b=_,y=_,c=_],z=_,d=_]]; T[:R,T[:B,a,x,b],y,T[:B,c,z,d]]
  when [a=_,x=_,T[:R,b=_,y=_,T[:R,c=_,z=_,d=_]]]; T[:R,T[:B,a,x,b],y,T[:B,c,z,d]]
  when [a=_,x=_,b=_]; T[:B,a,x,b]
  end
end

Haskell のシンプルさには敵わないけれど、だいぶ健闘していますよね。

x=_ が見にくいので、x=_ を <x> などと書けるような syntactic sugar を導入すればだいぶ見違えるんじゃないかと思う。

今の Ruby だけで書くと、

def balance(l, v, r)
  case
  when T===l && l.c===:R && T===l.l && l.l.c===:R; T[:R,T[:B,l.l.l,l.l.v,l.l.r],l.v,T[:B,l.r,v,r]]
  when T===l && l.c===:R && T===l.r && l.r.c===:R; T[:R,T[:B,l.l,l.v,l.r.l],l.r.v,T[:B,l.r.r,v,r]]
  when T===l && l.c===:R && T===r   && r  .c===:R; T[:R,T[:B,l.l,l.v,l.r],v,T[:B,r.l,r.v,r.r]]
  when T===r && r.c===:R && T===r.l && r.l.c===:R; T[:R,T[:B,l,v,r.l.l],r.l.v,T[:B,r.l.r,r.v,r.r]]
  when T===r && r.c===:R && T===r.r && r.r.c===:R; T[:R,T[:B,l,v,r.l],r.v,T[:B,r.r.l,r.r.v,r.r.r]]
  else T[:B,l,v,r]
  end
end