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)
- デストラクチャリングによる引数の分解
- スレッディングマクロ(->>)
これらが無い世界で暮らすのが辛い(笑)。
続Clojureのdestructuringメモ
前回「 Clojureのdestructuringメモ - Programmer's Note 」の続き。
マップのdestructuring
文字列をキーに使った場合を試す
(def mab {"a" 1 "b" 2}) (let [{:strs [a b]} mab] (println b "," a)) ; 結果 => 2,1
Goood!!
下記非短縮形もOK。
(def mab {"a" 1 "b" 2}) (let [{x "a" y "b"} mab] (println x y))
シンボルがキーの場合
(def mcd {'c 1 'd 2}) (let [{:syms [c d]} mcd] (println c "," d)) ; 結果 => 1,2
Goooooood!!
下記非短縮形もOK。
(def mcd {'c 1 'd 2}) (let [{x 'c y 'd} mcd] (println y "," x))
さて、マップの入れ子構造も試してみる
(def dat {:name "boo" :body {:weight 60 :height 160 } :money 100}) (let [{{h :height} :body} dat] (println h)) ; 結果 => 160
ベクターとマップの組み合わせ!
マップの中にベクターがある場合。
(def dat {:name "boo" :body [60 160] :money 100}) (let [{[_ height] :body} dat] (println height)) ; 結果 => 160
ベクターの中にマップがある場合。
(def dat ["boo" {:weight 60 :height 160} 100]) (let [[_ {h :weight} _] dat] (println h)) ; 結果 => 60
なんつービューティフルな言語なんだ!
関数に引数をマップで与える場合の省略形
たとえば関数にパラメータでマップを渡したい場合、
(boo "foo" {:weight 50 :height 120})
にするが、これを
(boo "foo" :weight 50 :height 120)
のように書ける!
前者の関数定義は
(defn boo [name opts] (let [{w :weight h :height} opts] (println name ": (" w "," h ")")))
で、後者は
(defn boo [name & opts] (let [{w :weight h :height} opts] (println name ": (" w "," h ")")))
違いは引数の定義に&
を使っているだけ!
defn
は実はマクロで、& opts
と定義したときは、残りの引数をまとめてシーケンスに入れてくれる。
さらにシーケンスはベクターにもマップにも展開できる。
シーケンスという一個上位の抽象概念をかますと、物事をシンプルに扱える。美しい。
destructuringは関数の引数定義[]
でも同じように使えるから、後者はこのようにも書ける。
(defn boo [name & {w :weight h :height}] (println name ": (" w "," h ")"))
いやあClojure最高です。
Clojureのdestructuringメモ
Clojureのdestructuringはベクターやmapの中から要素を取り出すのに、とても便利な機能。
さて、Clojure - Destructuring in Clojureに書いてあることなのだが、手を動かして確かめてみる。
使えるところ
関数
(defn foo [] (...))
無名関数
(fn [] (...))
let文
(let [] (...))
引数がベクターのとき
通常の使用方法
(def a [1 2]) (let [[x y] a] (println y "," x)) ; 結果 => 2,1
展開もとの要素数が足りない場合は、nilが代入される
(def b [1]) (let [[x y] b] (println y "," x)) ; 結果 => nil,1
_
を使って一部のみを取り出す
(def a [1 2]) (let [[_ y] a] (println y)) ; 結果 => 2
ベクターの入れ子もOK
(def abc [1 [2 3]]) (let [[x [y z]] abc] (println z "," y "," x)) ; 結果 => 3,2,1
ってどこまでOKなんだろう?
(def abcdefg [1 [2 3 [4 5 [6 7]]]]) (let [[_ [_ _ [_ _ [x y]]]] abcdefg] (println x "," y)) ; 結果 => 6,7
ひゅ〜、かっこいいね。
:as
を使って全体も扱う
(def abc [1 2 3]) (let [[x y :as z] abc] (println x "," y "<=" z)) ; 結果 => 1,2 <=[1,2,3]
&
を使って要素の一部を残りとして扱う
(def abc [1 2 3]) (let [[x & y] abc] (println x "," y)) ; 結果 => 1,(2 3)
引数がmapのとき
個別にkeyを指定して取り出す
(def mab {:a 1 :b 2}) (let [{x :a y :b} mab] (println y "," x)) ; 結果 => 2,1
展開時の{}
の書き方は、keyと要素が逆順、おしゃれ。
個別にkeyを指定して取り出す、特定のものだけ
(def mab {:a 1 :b 2}) (let [{z :b} mab] (println z)) ; 結果 => 2
ふーむ、便利。
存在しないkeyを指定した場合はnilが代入される
(def mab {:a 1 :b 2}) (let [{z :c} mab] (println z)) ; 結果 => nil
短縮形
(def mab {:a 1 :b 2}) (let [{:keys [a b]} mab] (println a "," b)) ; 結果 => 1,2
:keys
にkeywordの一覧を渡す。keywordから':‘を除いたものだね。これは要素がたくさんあるときは簡潔に表現できて便利。
mapのkeyにkeywordを使った場合はこのkeys
で指定できるが、keyに文字列やシンボルを使った場合は、:strs
、:syms
を使えば同じようにできる。すばらしすぎるな。
デフォルト値を入れることができる!
(def mab {:a 1 :b 2}) (let [{x :a, y :b, z :c :or {z 2}} mab] (println x "," y, "," z)) ; 結果 => 1,2,2
:c
はもともと定義したmapにはない要素だが、デフォルト値2を設定。
短縮形では、
(def mab {:a 1 :b 2}) (let [{:keys [a b c] :or {c 2}} mab] (println a "," b, "," c)) ; 結果 => 1,2,2
さらにmapの場合にも:as
が使える。
今日はここまで。
世界観と世界を変える一冊
ほぼ一年ぶりの更新か^^;
RubyとLispとClojureのコードの読みやすさ
「なぜRubyは許容可能なLISPなのか - 翡翠はコンピュータに卵を生むか」という記事が面白かった。
この記事の中でサンプルコードを使って、 プログラムの読みやすさを対比させていた部分があったので、 Clojureでやってみたくなった。
Ruby
[1,2,3].map {|n| n*n }.reject {|n| n%3==1 }
LISP
(remove-if (lambda (n) (= (mod n 3) 1)) (mapcar (lambda (n) (* n n)) '(1 2 3)))
(Clojure以外のLisp系言語はよく知らないが、たぶんこれはCommon Lisp)
同じことをClojureで記述してみる
Clojureのlambdaは無名関数なので、同じことをやると以下のようになる。
(remove (fn [n] (= (mod n 3) 1)) (map (fn [n] (* n n)) [1 2 3]))
上記LISPよりかは読みやすいが、ほぼ同等だな。
リーダーマクロ#()
を使ってみると。
(remove #(= (mod % 3) 1) (map #(* % %) [1 2 3]))
ぐっと簡潔になった。 さらに、スレッディングマクロを使うと、 Rubyのメソッドチェーンのように処理の流れの通りに書ける。
(->> [1 2 3] (map #(* % %)) (remove #(= (mod % 3) 1)))
一行の場合
(->> [1 2 3] (map #(* % %)) (remove #(= (mod % 3) 1)))
スレッディングマクロは、かなりプログラムの読みやすさに貢献している。 慣れてしまえばこれはRubyに匹敵する読みやすさになる。
とはいえ、しょっぱなはかなり戸惑ったけどね…。
データ指向 (Data Orientation)
Clojureを設計したRich Hickeyさんのプレゼン Clojure Made Simple - YouTube を観た。
特に印象的なのは、Clojureを作るきっかけになった経緯を語ったくだり。 簡単にいえば、20年間Java/C++/C#でエンタープライズ系のソフトウェアを組んできたキャリアのあと、 あるとき他の人がLispで面白いシステムをシンプルに実現しているのを見て、自分もやってみたら本当にシンプルにできたと。
かなり衝撃を受けたようで、いままで本当に時間を無駄にした!と落ち込んで(I was unhappy)、 やり方を変えないといけないと思ったと。 ここのくだりは気持ちがこもってるから悔しさが伝わってくるなW。「wasting my time」を連発している。
オブジェクト指向がいかに問題の本質とは関係ないところで、無駄にソフトウェアを複雑さにしているか、 このプレゼンの後半も具体例を使って説明している。 対比させているのは、Clojureの言語の特徴として説明している「データ指向(Data Orientation)」。
データ指向というのは例えばClojureのベクターやマップを使って、 問題領域にある処理対象のデータ構造を、ダイレクトに表現して扱っちまうことだ。と理解した。 この背景には、ほとんどのプログラムは本質的にデータ(情報)を処理するもの、という明快な思想がある。
データ構造を中心にプログラムを組むさまは、「Clojure for the Brave and True」の Functional Programming | Clojure for the Brave and True の章のサンプルゲーム開発の流れで要領がつかめる。 この本の著者はRich Hickeyのビデオは全部見ているようで、 The Unofficial Guide to Rich Hickey's Brain というブログ記事を書いている。(この記事のリプライが白熱した議論になっている。まじめに読んでないが・・・)
個人的にClojureを触り始めて、最初にクールに思った一つは ベクターとマップの存在で、これ自体が関数になる!ことだった。 Clojureを設計するにあたって、データ指向が念頭にあったとすると、ベクター/マップ/セットの出現は必然だったということか。 コードをデータとして表現できるLispを、言語のベースとして選択したことも必然だったと考えられる。
いやあでも、個人的にはLispをベースにしているとはいえ、 この人の言語設計のセンス(バランス感覚?)半端ないと思う。天才だと思います。 とちょっと最近はけっこう熱があがっている。 (いやなにせLispはLispでもCommon Lispはちょっと無理だな・・・)
Clojureの危険性
Clojureを始めたきっかけはPaul Grahamの「ハッカーと画家」を読んでだった。 この本はそれこそ情熱的なLisp啓蒙本と言っていい。 言語仕様はまったく紹介されてないにも関わらず、何だかLispのすごさだけは伝わってきた。 感化され「ANSI Common Lisp」「On Lisp」を買って読んだが、挫折。 (がんばって理解したいと思うほど言語が面白く感じなかった・・・)
しかし、その後「7つの言語7つの世界」のClojureの章を読んで、かなり面白い言語だと思った。 Common Lispに挫折してもClojureは楽しく入れたな。 どこが違いを生んだかというと、特に関数の書き方、ベクター、マップあたりが大きいと思う。
最近は仕事のちょっとした補助ツールをClojureで書いたり、あまった時間に色々戯れている。 せいぜい100〜200行程度のコードだが、それでもつくづく思う。 やばいくらいビューティフルな言語だなと!
で、また「ハッカーと画家」を読み直して、以前ピント来なかった部分が理解できて、新たに刺激を受けた。 この本は自分にとってバイブルになりつつある^^。
そして今日ふと積んでた「On Lisp」が目に入り、手に取って最初から読み直し始めた。 以下の一文に出くわす。
事実、Lispの持つ最大の危険はLispがユーザを堕落させてしまうかもしれないことだ。一度Lispをしばらく使うと、プログラミング言語とアプリケーションとの相性に敏感になりすぎ、元々使っていたプログラミング言語に戻っても、これでは必要な柔軟性が入らないという思いに常に囚われるようになりかねない
わかるわ〜。 自分もClojureでプログラムを組んでると、 「これ、他の言語が面倒くさく感じるようになるな。やばいな。」 と思っていたところだった。 プログラマーの三大美徳がだいぶ磨かれるな。これ。
On Lispの原著が読みたくなって調べたら、なんとフリーになっている!(http://www.paulgraham.com/onlisptext.html)
「SICP」、「Clojure for the Brave and True」もそうだが、Lisp界隈は本をフリーにする文化があるのかしら。