Clojureでパスカルの三角形

SICP遅々と読む。練習問題にパスカルの三角形の要素を計算せよ（再帰を使って）、というのがある。 フィボナッチ数列の次くらいに手軽な題材でいろいろ試せて遊べるなと。

Clojureらしい解き方は、やっぱ遅延シーケンスを作るやり方だろうなと。 出力形式は問われていないから、任意の行数までの計算結果を返すとしよう。

=> (take 5 (pascal-triangle))
([1] [1 1] [1 2 1] [1 3 3 1] [1 4 6 4 1])

=> (nth (pascal-triangle) 5)
[1 5 10 10 5 1]

コード：

(defn next-row
    [row]
    (letfn [(add-1-both-ends [coll] (concat [1] coll [1]))]
      (->> (partition 2 1 row)
           (map (fn [[a b]] (+ a b)))
           add-1-both-ends
           vec)))

(defn pascal-triangle
  ([] (pascal-triangle [1]))
  ([col] (lazy-seq (cons col (pascal-triangle (next-row col))))))

next-rowはパスカル三角形の特定の行の数列が与えられたとして、その次の行の数列を返す。

=> (next-row [1 1])
[1 2 1]
=> (next-row [1 2 1])
[1 3 3 1]

この関数の実装方法としては、以前「プログラミングClojure」で衝撃的だったフィボナッチ数列の解き方に習って、 いったん与えられた数列の形を扱いやすい形に変えている。

[1 3 3 1]　→ [[1 3] [3 3] [3 1]]

これで再帰を使わなくてもmapを使って要素の計算ができる。 partitionという関数を使えば、上記は簡単に出来る。

=> (partition 2 1 [1 3 3 1])
((1 3) (3 3) (3 1))

仮にcore関数のpartitionを使わずに、似たことをやるとしたら以下の関数を作れば良い。

(defn my-partition
   [[a b :as col]]
   (when (and a b)
     (cons [a b] (my-partition (rest col)))))

デストラクチャリングを使って要素を取り出して再帰するClojureのエレガントさを味わえるので、これはこれで楽しい。

pascal-triangle関数も、遅延シーケンスを使わずに再帰を使って、しかもStack Overflowを起こさない末尾最適可能なように作るとしたら、下記になるかなと。（中で使っているnext-rowは変わらない）

(defn pascal-triangle
  ([n] (pascal-triangle n [1] []))
  ([n a b]
    (if (zero? n)
      b
      (recur (dec n) (next-row a) (conj b a)))))

遅延シーケンスほど使い回しは効かなくなるが、

=> (pascal-triangle 5)
([1] [1 1] [1 2 1] [1 3 3 1] [1 4 6 4 1])

という感じになる。

この小さい題材の実装でもClojureの以下の機能が便利すぎて、

• シーケンスを扱う高階関数(map, partition)
• 引数個数ごとに関数の処理を分けて定義できる（multi-arity）
• デストラクチャリングによる引数の分解
• スレッディングマクロ(->>)

これらが無い世界で暮らすのが辛い（笑）。