Clojureでもクリスマスツリーを飾りました

Clojure

この記事はClojure Advent Calendar 2011の13日目の記事です。一日＋α 遅れましたが。

シーケンス（リスト）でクリスマスツリーが作れるらしいので作ってみました。

●元ネタ

●準備

みんな大好き leiningen
project.clj は今回こんな感じです。

(defproject christmas-tree "0.1.0"
  :description "clojure advent calendar"
  :dependencies [[org.clojure/clojure "1.2.1"]
                 [org.clojure/clojure-contrib "1.2.0"]
                 [hiccup "0.3.7"]]
  :jar-name "christmas-tree.jar"
  :uberjar-name "christmas-tree-standalone.jar"
  :main christmas-tree.core)

●木のデータ

データの作り方は単純です。使うのは 0 と 1 だけ。
最初のデータはこれだけです。これを一次（サイズ１）とします。

0 1

二次はこうです。

   10
00 01 11

三次は

    100 101
    010 110
000 001 011 111

n+1 次のデータは n 次のデータから生成します。
n 次のデータの「行」のすべてのブロック*1の末尾に 0 を加えた新たな行と、1 を加えた新な行の２行を作ります。

00 01 11
     ↓
000 010 110
001 011 111

そして、0 を加えた行の先頭の１ブロックを 1 を加えた行の先頭に移動します。

    010 110
000 001 011 111

このような操作を「木」の全ての行に対して行なうことで、次のサイズの木が作られます。
なお操作によって行のブロックが１つもなくなってしまった場合、その行は除去します。

以上の処理を Clojure でシーケンス操作によって作ります。

1011 のような数字の連続したブロックを [1 0 1 1] という数値のベクタで表現しています。したがって tree の１行は「ベクタを要素とするシーケンス」、tree 全体では「ベクタを要素とするシーケンスのシーケンス」となります。
christmas-tree.tree/grow-lineで１行分のデータを受け取り、上に書いた操作によって２行にして返します。
christmas-tree.tree/nth-tree は引数 n の次数の tree のデータを返します。この nth-tree の関数の最後の行にある ,,, ですが、Clojure では , は空白文字（スペース）と同じ扱いです。これを利用して「ここに値が挿入されますよ」というマークにしています。Web上で公開されていた Clojure コードで見掛けたのですが -> マクロ利用時などに使うと可読性があがるのでよく使ってます。

ちなみに ブロックをベクタにしたのは、新たな要素を末尾に追加しなければならないからです。「末尾へ追加」は 「conj + ベクタ」が効率的（なはず）です。

(conj [1 0 0] 1) ;=> [1 0 0 1]

では実際に nth-tree を試してみましょう。

(require '[christmas-tree.tree :as tree])
(tree/nth-tree 3)

結果

(([1 0 0] [1 0 1]) ([0 1 0] [1 1 0]) ([0 0 0] [0 0 1] [0 1 1] [1 1 1]))

●整形して出力

インデントを挿入して出力します。

christmas-tree.console/print-tree に christmas-tree.tree/nth-tree で作ったデータを与えると、

(require '[christmas-tree.console :as console])
(console/print-tree (tree/nth-tree 4))

こんな風にコンソールに出力されます。（サイズ４の場合です）。

          1010
     1000 1001 1011
          1100
     0100 0101 1101
     0010 0110 1110
0000 0001 0011 0111 1111

木の左側のインデントサイズは、行の左端のブロックをみるだけで決定できるのですが、分りますか？
christmas-tree.tree/make-indentでインデント用のシーケンスを作っています。

●色を付けたい

例えばこんな行の場合

0010 0110 1110	
-*---**---*---

アスタリスクの付いているアイテム*2に色を付けます。つまり隣接する２つのブロックを比較した時、「左のブロックのアイテム 0 が、右ブロックの同じ位置で 1 になっている場合」に、「左ブロックの 0」と「右ブロックの 1」の両方に色を付けます。
簡単そうで意外にややこしいです。

さて、単なる数値であるアイテムに属性情報（色）をつけるため、nth-tree で生成されたデータの全てのアイテムを hash-map に置き換える関数を作ることにしました。
「赤い 0」は {:val 0 :color 'red} のように表現します。

隣あったブロックを比較するために (partition 2 1) を使っています

(partition 2 1 '(A B C D E F)) ;=> ((A B) (B C) (C D) (D E) (E F))

隣合う要素をペアにしてくれるので、隣接要素の比較に利用できます。ただしこの方法だと、

(->> (partition 2 1 '(A B C D E F))
     (map first))    

 ;=> (A B C D E)  ; F が欠落

というように、先頭や末尾の要素が処理結果に含まれないことがあります。今回もこのケースに該当してしまうのですが、要素の欠落はさせたくない。そういう場合には

(->> (concat '(X) '(A B C D E F) '(X))
     (partition 2 1)
     (map first)
     rest)

;;=>(A B C D E F)

予め計算結果に影響を与えないような値を、処理対象のシーケンスの前後に加えておいて、最後に不要な部分をカットすることで、欠落のないデータを得ることができます。
今回のコードでは christmas-tree.attr/set-line-colors 関数の

(->> (concat [ones] line [zeros])
      to-attrs-from-line
      (partition 2 1)
      (mapcat set-blocks-colors)
      rest ...

という部分がそれにあたります。 concat で line の前後にベクタ（ブロック）を加えてから (partition 2 1) で処理し、最後に rest で余分な先頭をカットしています。
試しに使ってみると...

(require '[christmas-tree.attr :as attr])
(attr/set-tree-colors (tree/nth-tree 3))

結果

((({:val 1} {:val 0})) (({:val 0} {:color red, :val 0}) ({:color red, :val 0} {:color yellow, :val 1}) ({:color yellow, :val 1} {:val 1})))

0 には red, 1 には yellow を付加しています。色付をしないアイテムは {:val 0} のように :color 属性をつけていません。これは {:val 0 :color nil} と同じとみなすことができます。

●html 出力

色情報を付加したので、その情報をもとにレンダリングします。HTMLに吐き出すのがてっとり早い。

hiccup というモジュールを使うと、HTMLのタグをベクタで構築できます。
CSS を ベタ書きでハードコーディングしてるのはよろしくないですが、ともあれこれで色付きのツリーを出力できます。
次のようにすると、標準出力に HTML が出力されます。
christmas_tree.html/print-tree は 全ての要素が hash-map 化された属性つき tree データを引数にとります。

(require '[christmas-tree.html :as html])
(-> (tree/nth-tree 6) attr/set-tree-colors html/print-tree)

ファイルに保存してブラウザで開くと

色がつくと雰囲気がでますね。赤黄の密度も丁度いい感じ。

●コマンドラインツールとして

最後に core.clj を整備しましょう。

clojure.contrib.command-line/with-command-line はコマンドライン引数の定義をサポートしてくれるマクロです。--help で出力する usage も管理してくれます。
以下は、leiningen での実行例*3。

$ lein run --help

java -jar christmas-tree-standalone.jar [Options]

Options
  --size, -n <arg>     size of tree              [default 4]
  --text, -t           output to text (default)             
  --html, -p           output to html page                  
  --outfile, -o <arg>  output filename

<arg> が付いているのが引数をとるオプションです。
例えば

$ lein run -n 8 -p -o hoge.html

とすれば、サイズ8の、tree を hoge.html へ HTMLファイルとして保存します。


clojure.contrib.duck-streams/with-out-writer は動的 binding によって標準出力をファイルへリダイレクトしてくれるマクロです。とりあえず println で標準出力にデータを吐き出す関数を作っておいて、あとでファイル出力に変更する、ということが簡単にできます。

(defn print-hoge
  "標準出力へ出力"
  []
  (println "HOGE"))

(defn write-hoge
  "ファイルへ出力"
  [filename]
  (with-out-writer filename (print-hoge)))

大きなプログラムではもう少しちゃんとアウトプット管理をすべきですが、小さなツールでは便利に使えるとおもいます。コマンドライン引数でのファイル指定と組み合わせるとさらに便利です*4。

おわりに

小さなプログラムの作成をしながら、Clojure ならではのポイントや小さな tips を書いてみようという試みでしたが、如何がでしたでしょうか。Clojurian にとってはあたりまえのことばかりだったと思いますが、初心者や Clojure に興味をもっている方の参考になれば幸です。

以上の全コードは github においてあります。
https://github.com/mnzk/christmas-tree

*1:100 や 101 のような連続した塊を、ここでは「ブロック」と呼びます。

*2:ここではブロック内の要素 0,1 ひとつひとつを「アイテム」と呼びます。

*3:leiningen でプロジェクトを管理している場合、 lein run で -main 関数を実行してくれます。コマンドライン引数もそのままプログラムへ渡してくれます。

*4:引数でファイルが指定されたらそちらへ、指定されなかったら標準出力へといった振分けが簡単にできます。