Ruby で「パスカルの三角形」を出力（ちょっと関数型プログラミングっぽく+メモ化）

パスカルの三角形

こういうのですね。

              1               
             1 1              
            1 2 1             
           1 3 3 1            
          1 4 6 4 1           
        1 5 10 10 5 1         
       1 6 15 20 15 6 1       
     1 7 21 35 35 21 7 1      

$(a + b)^n$を展開すると、係数が上のように並びます。両端が 1 で、となり同士の数字を足すと、その下の数字になっています。

コード

pascal.rb

each_cons = ->(ary) {
  (ary.size < 2) ? [] : [ary[0] + ary[1]] + each_cons.(ary.drop(1))
}
pascal = ->(n) {n.zero? ? [1] : [1] + each_cons.(pascal.(n - 1)) + [1]}

n = 8
n.times {|i| puts pascal.(i).join(" ").center(30)}

これで上の出力になります。「関数型」ってのはまあ気分です。誰でも何でも再帰で書きたいときがある（笑）　結構きれいに書けたと思うのだけれど、もっと上手いやり方があったら教えて下さい。

関数pascal.(n)というのは n + 1 行目の出力というつもりで書きました。Array を返します。順番に[1],[1, 1], [1, 2, 1], [1, 3, 3, 1]... みたいな感じですね。

関数each_cons.(ary)は Ruby 組み込みから名前を借りただけで、自前の関数です。このプログラムはこの関数がキモです。再帰関数（自分自身を呼び出す関数）です。関数型プログラミングではループの代わりに再帰を使います。上で「となり同士の数字を足すと、その下の数字になっています」と書きましたが、ここではまさにそれをやっています。おわかりでしょうか。引数aryは Array で、関数は Array を返します。

Rubyをよく知らない人へ

もしかしたら->() {}という書き方をご存知ない方がおられるかもしれないので書いておくと、これは Ruby の lambda の書き方のひとつです。lambda do ~ endと同じです。また、? :というのはいわゆる「三項演算子」で、if then ~ else ~ endと同じです。

ちなみに、drop(1)というのは Lisp のcdrを Ruby で書いたものです。Array の先頭を取り除き、その残りを返します。例えば、[1, 2, 3].drop(1)は[2, 3]が返ります。わかる人はわかると思いますが、じつは Ruby でちょっと Lisp っぽく書いてみたかったのです（笑）　Lisp はよくは知りませんが。

以上はブログ記事を元にしています。

追記：メモ化

このままだと「効率が悪い」としかられそうなので、先に追記しておきます。こんな風にします。

pascal_memoized.rb

memo = {}

each_cons = ->(ary) {
  (ary.size < 2) ? [] : [ary[0] + ary[1]] + each_cons.(ary.drop(1))
}
pascal = ->(n) {
  return memo[n] if memo.has_key?(n)
  memo[n] = n.zero? ? [1] : [1] + each_cons.(pascal.(n - 1)) + [1]
}

n = 8
n.times {|i| puts pascal.(i).join(" ").center(30)}

一度計算したものはハッシュmemoに入れておくという「メモ化」なる技法です。高速化などによく使われます。多少コードの量は増えますが、計算量をぐっと減らすことができます。

それから、n.times {...}の部分ももちろん簡単に再帰で書けます。徹底したい方はそちらでどうぞ。