Journal InTime

_ パターンマッチの構文

pattern-matchというライブラリで赤黒木を実装してみてパターンマッチの便利さを改めて実感したが、やはり言語レベルのサポートがあった方がよいと感じたので構文を考えてみた。

• 既存の構文の互換性は維持する。
• 新しい予約語を追加しない。

という方針を立てて考えると、case式を拡張するのがよさそうだ。

Haskellのcase式を参考にしてみよう。Haskellでは赤黒木のbalanceを以下のように書くことができる。

balance :: RB a -> a -> RB a -> RB a
balance left key right =
  case (left, key, right) of
    ((T R a x b), y, (T R c z d)) -> T R (T B a x b) y (T B c z d)
    ((T R (T R a x b) y c), z, d) -> T R (T B a x b) y (T B c z d)
    ((T R a x (T R b y c)), z, d) -> T R (T B a x b) y (T B c z d)
    (a, x, (T R b y (T R c z d))) -> T R (T B a x b) y (T B c z d)
    (a, x, (T R (T R b y c) z d)) -> T R (T B a x b) y (T B c z d)
    (a, x, b) -> T B a x b

(a, x, b) -> T B a x bの部分はλ抽象に似ている（Haskellでは\x -> x + 1のようにRubyとは->の位置が違う点に注意）。

Rubyでもstabby lambda風の構文を導入してはどうだろうか。

def balance(left, key, right)
  case [left, key, right]
    -> [R[a, x, b], y, R[c, z, d]] { R[B[a, x, b], y, B[c, z, d]] }
    -> [R[R[a, x, b], y, c], z, d] { R[B[a, x, b], y, B[c, z, d]] }
    -> [R[a, x, R[b, y, c]], z, d] { R[B[a, x, b], y, B[c, z, d]] }
    -> [a, x, R[b, y, R[c, z, d]]] { R[B[a, x, b], y, B[c, z, d]] }
    -> [a, x, R[R[b, y, c], z, d]] { R[B[a, x, b], y, B[c, z, d]] }
    -> * { B[left, key, right] }
  end
end

これなら新しい予約語は必要ないし、->の位置にwhenが来た場合は現状どおりの動作とすれば互換性の問題もない。 endと{}が混ざるのが気持ち悪ければ代りにdo endを使えばよい（stabby lambdaと同じ）。

あと、pattern-matchではextractというメソッドでオブジェクトを分解しているけど、ちょっと名前が一般的すぎる気がするのでdeconstructとかにした方がいい気がする。

_ Enumerable#lazy

yhara先生が提案していたEnumerable#lazyがtrunkに入ったので、喜び勇んで以下の例を試したのだが、なぜかぜんぜん返って来ない。

def pythagorean_triples
  (1..Float::INFINITY).lazy.flat_map {|z|
    (1..z).flat_map {|x|
      (x..z).select {|y|
        x**2 + y**2 == z**2
      }.map {|y|
        [x, y, z]
      }
    }
  }
end
p pythagorean_triples.take(10)

確認したら、どうもEnumerable::Lazyはflat_mapをサポートしていないようだったので、適当に実装してtrunkにcommitしてやった。 こういうことができるのがRubyのいいところだ。というわけで無事動くようになった。

$ ruby-trunk t.rb
[[3, 4, 5], [6, 8, 10], [5, 12, 13], [9, 12, 15], [8, 15, 17], [12, 16, 20], [7, 24, 25], [15, 20, 25], [10, 24, 26], [20, 21, 29]]

しかし、今のEnumerable::Lazy#flat_mapではブロックの値が配列であることを期待するので、以下のようなコードだと残念なことになってしまう。

$ cat t2.rb
def pythagorean_triples
  (1..Float::INFINITY).lazy.flat_map {|z|
    (1..z).lazy.flat_map {|x|
      (x..z).lazy.select {|y|
        x**2 + y**2 == z**2
      }.map {|y|
        [x, y, z]
      }
    }
  }
end
p pythagorean_triples.take(10)
$ ruby-trunk t2.rb
[#<Enumerable::Lazy: #<Enumerator::Generator:0x214bd630>:each>, #<Enumerable::Lazy: #<Enumerator::Generator:0x214bd4c8>:each>, #<Enumerable::Lazy: #<Enumerator::Generator:0x214bd360>:each>, #<Enumerable::Lazy: #<Enumerator::Generator:0x214bd1f8>:each>, #<Enumerable::Lazy: #<Enumerator::Generator:0x214bd090>:each>, #<Enumerable::Lazy: #<Enumerator::Generator:0x214bcf28>:each>, #<Enumerable::Lazy: #<Enumerator::Generator:0x214bcdc0>:each>, #<Enumerable::Lazy: #<Enumerator::Generator:0x214bcc58>:each>, #<Enumerable::Lazy: #<Enumerator::Generator:0x214bcaf0>:each>, #<Enumerable::Lazy: #<Enumerator::Generator:0x214bc988>:each>]

eachでばらしてyieldするようにすればいいかなと思ったのだが、試しに実装したらSEGVしてしまったのでいつかリベンジしよう。