Lisp 系の言語では、リストを「入れ子 (ネスト)」にすることができます。入れ子になっているリスト構造を「木 (tree)」といいます。伝統的な Lisp には木の要素を置換する関数 subst が用意されています。また、近代的な Lisp 処理系では、他のデータ構造 (配列、ハッシュ、構造体など) も入れ子にすることが可能です。
Lisp と同様に Clojure もリスト、ベクタ、マップなどを入れ子にすることができます。そして、複雑なデータ構造を操作するためのライブラリ (clojure.walk や clojure.zippers など) も用意されています。今回は入れ子になったリストを操作する便利な関数をいくつか紹介します。
Lisp のリストは複数の「コンスセル (cons cell)」を連結したものです。ひとつのコンスセルには、データを格納する CAR (カー) という場所と、次のセルを連結する CDR (クダー) という場所からなっています。次の図を見てください。
CAR CDR CAR CDR
┌─┬─┐ ┌─┬─┐
│・│・┼─→│・│・┼→終端 (NIL)
└┼┴─┘ └┼┴─┘
↓ ↓
１ ２
図 : リストの構造
上図では、コンスセルを箱で表しています。左側の CAR がデータを格納する場所で、CDR が次のコンスセルと連結しています。上図の例では、先頭のコンスセルの CAR には 1 が格納され、CDR は次のコンスセルと連結しています。2 番目のコンスセルには CAR に 2 というデータが格納されています。このあとに接続されるコンスセルはもうないので、CDR にはリストの終わりを示す特別なデータ (Common Lisp はNIL, Scheme と Clojure は ()) が格納されます。このようなリストを Lisp では (1 2) と表記します。
さらに、Lisp のリストは CAR にリストを格納して、リストを入れ子にすることができます。次の図を見てください。
┌─┬─┐ ┌─┬─┐ ┌─┬─┐
│・│・┼→│・│・┼→│・│／│ ／ : NIL
└┼┴─┘ └┼┴─┘ └┼┴─┘
↓ │ │
１ │ │
│ ↓
│ ┌─┬─┐ ┌─┬─┐ ┌─┬─┐
│ │・│・┼→│・│・┼→│・│／│
│ └┼┴─┘ └┼┴─┘ └┼┴─┘
│ ↓ ↓ ↓
│ ３ １２ １３
↓
┌─┬─┐ ┌─┬─┐ ┌─┬─┐
│・│・┼→│・│・┼→│・│／│
└┼┴─┘ └┼┴─┘ └┼┴─┘
↓ ↓ ↓
２ １０ １１
図 : リストの階層構造
上図のリストを Lisp で記述すると (1 (2 10 11) (3 12 13)) になります。なお、静的型付けの関数型言語 (Haskell や ML 系言語など) では、トップレベルのリストの要素の型が整数とリストで異なるため、このようなデータ構造をリストで表すことはできません。この場合、リストではなく二分木を使うと簡単に定義することができます。
Clojure の場合、コンスセルの CDR はリスト (コンスセルと空リスト) しか格納することができませんが、Lisp / Scheme ではリストだけではなく、他のデータ型でも格納することができます。Lisp / Scheme の場合、リストの終端が空リスト以外のデータの場合、そのリストを次のように表します。
┌─┬─┐ ┌─┬─┐
│・│・┼─→ NIL │・│・┼─→２
└┼┴─┘ └┼┴─┘
↓ ↓
１ １
(1) ≡ (1 . NIL) (1 . 2)
┌─┬─┐ ┌─┬─┐ ┌─┬─┐
│・│・┼─→│・│・┼─→│・│・┼─→ NIL
└┼┴─┘ └┼┴─┘ └┼┴─┘
↓ ↓ ↓
１ ２ ３
(1 2 3) ≡ (1 . (2 . (3 . NIL)))
図 : リストの終端 (その１)
┌─┬─┐ ┌─┬─┐ ┌─┬─┐
│・│・┼─→│・│・┼─→│・│・┼─→d
└┼┴─┘ └┼┴─┘ └┼┴─┘
↓ ↓ ↓
ａ ｂ ｃ
(a b c . d) ≡ (a . (b . (c . d)))
図 : リストの終端 (その２)
左右のカッコの中間にドット ( . ) を置き、左側に CAR のデータを、右側に CDR のデータを書きます。つまり、リスト (1) は (1 . NIL) と表すことができます。このようなデータを Lisp では「ドット対 (dotted pair)」と呼びます。たとえば、CAR が 1 で CDR が 2 であれば (1 . 2) となります。普通のリストも次のようにドット対を使って表現できます。
(1) ≡ (1 . NIL) (1 2 3) ≡ (1 . (2 . (3 . NIL))) ((1 2) (3 4)) ≡ ((1 . (2 . NIL)) . ((3 . (4 . NIL)) . NIL)) ((1 2) 3 4) ≡ ((1 . (2 . NIL)) . (3 . (4 . NIL)))
それでは、リスト (a b c) の終端を d に変えてみましょう。ドット対を使った表記法では、(a . (b . (c . d))) となりますが、これは (a b c . d) と表すことができます。このように、NIL 以外のアトムで終端されたリストを Lisp では「ドットリスト (dotted list)」と呼びます。
ドットの後ろは CDR にセットするデータを指定するのですから、複数のデータを書いたり省略してはいけません。次の場合、Lisp ではエラーになります。
( . a) ; CAR がない (a . ) ; CDR がない (a . b c) ; CDR にデータが複数ある (a . . b) ; ドットが複数ある (a . b . c )
Clojure はドット対をサポートしていないので、入れ子になったリスト構造を操作する場合、Lisp と Clojure で動作が異なることがあります。ご注意くださいませ。
入れ子になったリストを巡回する場合、コンスセルを二分木の節と考えれば簡単です。拙作のページ 二分探索木 で説明したように、木の巡回は次の 3 つの方法が重要です。
リストを木構造として考える場合、コンスセルの CAR を左の子、CDR を右の子とします。データは格納されていないので、節のデータのかわりにコンスセルを出力することにします。たとえば、リスト ((12) (3 4)) を巡回してみましょう。次の図を見てください。
Ａ Ｂ
┌─┬─┐ ┌─┬─┐
│・│・┼→│・│／│
└┼┴─┘ └┼┴─┘
│ │
│ ↓Ｃ Ｄ
│ ┌─┬─┐ ┌─┬─┐
│ │・│・┼→│・│／│
│ └┼┴─┘ └┼┴─┘
│ ↓ ↓
│ ３ ４
↓Ｅ Ｆ
┌─┬─┐ ┌─┬─┐
│・│・┼→│・│／│
└┼┴─┘ └┼┴─┘
↓ ↓
１ ２
図 : リスト ((1 2) (3 4)) の構造
コンスセル A が二分木の根 (ルート) に相当します。CAR をたどっていくと A - E - 1 まで進みます。1 は葉なので、E に戻って CDR をたどり A - E - F に進みます。F の CAR をたどると ２ に進み、CDR をたどると空リストになります。F と E は CDR までたどったので A に戻ります。
次に、A の CDR をたどり A - B に進みます。CAR をたどっていくと A - C - 3 に進みます。3 は葉なので C にもどって CDR をたどると A - C - D に進みます。D の CAR をたどると 3 に進み、CDR をたどると空リストになります。D と C は CDR までたどったので B に戻ります。最後に、B の CDR をたどって空リストになり、これでリスト (コンスセルと要素) を全て巡回することができました。
これをプログラムすると、次のようになります。
リスト : リスト (木) の巡回
;;; コンスセル？
(defn consp [xs]
(and (list? xs) (seq xs)))
;;; 通りがけ順
(defn traverse-inorder [proc xs]
(if (not (consp xs))
(proc xs)
(do
(traverse-inorder proc (first xs))
(proc xs)
(traverse-inorder proc (rest xs)))))
;;; 行きがけ順
(defn traverse-preorder [proc xs]
(if (not (consp xs))
(proc xs)
(do
(proc xs)
(traverse-preorder proc (first xs))
(traverse-preorder proc (rest xs)))))
;;; 帰りがけ順
(defn traverse-postorder [proc xs]
(if (not (consp xs))
(proc xs)
(do
(traverse-postorder proc (first xs))
(traverse-postorder proc (rest xs))
(proc xs))))
述語 consp は引数 xs がコンスセルならば true を返します。関数名は Common Lisp から拝借しました。どの関数も引数 xs がコンスセルでなければ、(proc xs) を評価します。これで葉 (要素) を出力することができます。コンスセルであれば CAR と CDR に分解して、関数を再帰呼び出しします。再帰呼び出しする前に (proc xs) を評価すると行きがけ順に、再帰呼び出しの後に評価すると帰りがけ順に、CAR を再帰呼び出しした後に評価すると通りがけ順になります。
それでは実行してみましょう。
user=> (traverse-preorder println '((1 2) (3 4))) ((1 2) (3 4)) (1 2) 1 (2) 2 () ((3 4)) (3 4) 3 (4) 4 () () nil user=> (traverse-postorder println '((1 2) (3 4))) 1 2 () (2) (1 2) 3 4 () (4) (3 4) () ((3 4)) ((1 2) (3 4)) nil user=> (traverse-inorder println '((1 2) (3 4))) 1 (1 2) 2 (2) () ((1 2) (3 4)) 3 (3 4) 4 (4) () ((3 4)) () nil
正常に動作していますね。興味のある方はいろいろ試してみてください。
リストを列 (sequence) と考えた場合、トップレベルの要素を置換するのは簡単です。Common Lisp には関数 substitute, substitute-if などがありますし、Clojure でも replace や内包表記などを使えば簡単です。ですが、これらの関数を使って ((1 2) (3 4)) の要素 1, 2, 3, 4 を他の値に置き換えることはできません。
入れ子になったリストの要素を置換する関数として、伝統的な Lisp には subst があります。また、Common Lisp には subst の他にも subst-if などがあります。
subst new old tree old と等しい要素を new に置き換える subst-if new pred tree 述語 pred が真となる要素を new に置き換える
Clojure には入れ子になったデータ構造を操作するためのライブラリ clojure.walk が用意されています。これはリストだけではなくベクタやマップなどにも適用することができますが、Common Lisp の subst とはちょっと動作が異なるところがあります。clojure.walk はあとで説明することにして、ここでは subst と subst-if を Clojure でプログラムしてみましょう。
subst と subst-if はリストの巡回と同様に、深さ優先でリスト (木構造) をたどります。次のリストを見てください。
リスト : リストの置換 (1)
(defn subst [new old xs]
(cond
(= old xs) new
(not (consp xs)) xs
:else (cons (subst new old (first xs))
(subst new old (rest xs)))))
(defn subst-if [new pred xs]
(cond
(pred xs) new
(not (consp xs)) xs
:else (cons (subst-if new pred (first xs))
(subst-if new pred (rest xs)))))
subst はリスト xs の old に等しい (=) 部分を、new に置き換えた新しいリストを返します。subst-if は述語 pred が真を返す部分を new に置き換えた新しいリストを返します。どちらの関数もリストの構造を再帰的にたどり、すべての要素を検査します。元のリストは破壊されません。
簡単な実行例を示します。
user=> (subst 0 4 '((1 2) (3 4))) ((1 2) (3 0)) user=> (subst 0 '(3 4) '((1 2) (3 4))) ((1 2) 0) user=> (subst 1 'a '(a b c (a b c (a b c)))) (1 b c (1 b c (1 b c))) user=> (subst-if 0 #(and (integer? %) (even? %)) '(((1 2) (3 4)) (5 6))) (((1 0) (3 0)) (5 0))
最後の例は even? だけでは動作しません。つまり、1 や 2 だけではなく、(1 2) や ((1 2) (3 4)) も検査されるのです。ご注意ください。
ところで、Clojure はドット対をサポートしていないので、ドット対が生成されるような置換はできません。簡単な例を示しましょう。
user=> (subst 'z '() '(1 2 3 4)) Execution error (IllegalArgumentException) at user/subst (sample_walk.clj:49). Don't know how to create ISeq from: clojure.lang.Symbol user=> (subst '(z) '() '(1 2 3 4)) (1 2 3 4 z) user=>(subst 'z '(3 4) '(1 2 3 4)) Execution error (IllegalArgumentException) at user/subst (sample_walk.clj:49). Don't know how to create ISeq from: clojure.lang.Symbol user=> (subst '(z) '(3 4) '(1 2 3 4)) (1 2 z)
1 番目の例は (1 2 3 4 . z) になり、3 番目の例では (1 2 . z) となるので、Clojure ではエラーになります。z ではなく (z) のようなリストならば置換することができます。ドット対をサポートしている Lisp 処理系であれば正常に動作します。SBCL での実行例を示します。
* (subst 'z nil '(1 2 3 4)) (1 2 3 4 . Z) * (subst 'z '(3 4) '(1 2 3 4) :test #'equal) (1 2 . Z)
Common Lisp の場合、subst は等値の判定に述語 eql を使います。リスト同士を eql で比較すると結果は偽になるので、:test で述語 equal を指定してください。
もうひとつ便利な関数を紹介しましょう。Common Lisp の関数 sublis は、連想リストのキーに等しい form の部分を、キーに対応するデータに置き換えます。sublis は subst を複数回実行した場合と同じ効果が得られます。form は破壊されません。
sublis a-list form
SBCL での実行例を示します。
* (sublis '((a . 1) (b . 2)) '(a b c (a b c . a) d . b)) (1 2 c (1 2 c . 1) d . 2)
sublis にはキーワード :key, :test, :test-not を指定することができます。Clojure で sublis をプログラムするのであれば、連想リストよりもマップを使ったほうが簡単です。プログラムは次のようになります。
リスト : リストの置換 (2)
(defn sublis [alist xs]
(let [new (get alist xs)]
(cond
new new
(not (consp xs)) xs
:else (cons (sublis alist (first xs))
(sublis alist (rest xs))))))
引数 alist はマップです。最初に xs が alist にあるかチェックします。xs が見つからない場合、変数 new は nil になります。new が真であれば、new をそのまま返します。あとは subst と同じです。
それでは実際に試してみましょう。
user=> (sublis {"foo" 10 "oops" 20} '(("foo" "bar") ("baz" "oops")))
((10 "bar") ("baz" 20))
user=> (sublis {:a 1, :b 2, :c 3} '(:a (:b :b) :c))
(1 (2 2) 3)
user=> (sublis {:a 1, :b 2, :c 3} '(:a (:b :b) :c :d))
(1 (2 2) 3 :d)
正常に動作しているようです。興味のある方はいろいろ試してみてください。
Clojure のライブラリ clojure.walk には、入れ子になったデータ構造 (リスト、ベクタ、マップ、シーケンスなど) を巡回して要素を置換するための関数が定義されています。今回作成した subst や subst-if はリスト専用ですが、clojure.walk はリスト以外のデータ構造にも適用することができます。
巡回の動作は次の関数で確認することができます。
postwalk-demo form prewalk-demo form
どちらの関数もデータ構造 form を深さ優先で巡回します。postwalk-demo は帰りがけ順で、prewalk-demo は行きがけ順で要素を表示します。それでは実際に試してみましょう。
user=> (require '[clojure.walk :as w]) nil user=> (w/postwalk-demo '((1 2) (3 4))) Walked: 1 Walked: 2 Walked: (1 2) Walked: 3 Walked: 4 Walked: (3 4) Walked: ((1 2) (3 4)) ((1 2) (3 4)) user=> (w/prewalk-demo '((1 2) (3 4))) Walked: ((1 2) (3 4)) Walked: (1 2) Walked: 1 Walked: 2 Walked: (3 4) Walked: 3 Walked: 4 ((1 2) (3 4))
結果を見ればおわかりのように、clojure.walk の巡回は今回作成した関数 traverse-xxx とは動作が異なります。具体的には、リストをシーケンスとして扱い、先頭から順番に要素を取り出して、それがコレクションならば再帰的に巡回する、というアルゴリズムになります。これを高階関数でプログラムすると、次のようになります。
リスト : コレクションの巡回
(defn traverse-post [proc xs]
(when (coll? xs)
(doseq [x xs]
(traverse-post proc x)))
(proc xs))
(defn traverse-pre [proc xs]
(proc xs)
(when (coll? xs)
(doseq [x xs]
(traverse-pre proc x))))
アルゴリズムをそのままプログラムしただけなので、とくに難しいところはないと思います。それでは実際に試してみましょう。
user=> (traverse-post println '((1 2) (3 4))) 1 2 (1 2) 3 4 (3 4) ((1 2) (3 4)) nil user=> (traverse-pre println '((1 2) (3 4))) ((1 2) (3 4)) (1 2) 1 2 (3 4) 3 4 nil
同様に、ベクタとマップも巡回することができます。簡単な実行例を示します。
user=> (w/postwalk-demo [[1 2] [3 4]])
Walked: 1
Walked: 2
Walked: [1 2]
Walked: 3
Walked: 4
Walked: [3 4]
Walked: [[1 2] [3 4]]
[[1 2] [3 4]]
user=> (w/prewalk-demo [[1 2] [3 4]])
Walked: [[1 2] [3 4]]
Walked: [1 2]
Walked: 1
Walked: 2
Walked: [3 4]
Walked: 3
Walked: 4
[[1 2] [3 4]]
user=> (traverse-post println [[1 2] [3 4]])
1
2
[1 2]
3
4
[3 4]
[[1 2] [3 4]]
nil
user=> (traverse-pre println [[1 2] [3 4]])
[[1 2] [3 4]]
[1 2]
1
2
[3 4]
3
4
nil
user=> (w/postwalk-demo {{:a 1, :b 2}, {:c 3, :d 4}})
Walked: :a
Walked: 1
Walked: [:a 1]
Walked: :b
Walked: 2
Walked: [:b 2]
Walked: {:a 1, :b 2}
Walked: :c
Walked: 3
Walked: [:c 3]
Walked: :d
Walked: 4
Walked: [:d 4]
Walked: {:c 3, :d 4}
Walked: [{:a 1, :b 2} {:c 3, :d 4}]
Walked: {{:a 1, :b 2} {:c 3, :d 4}}
{{:a 1, :b 2} {:c 3, :d 4}}
user=> (w/prewalk-demo {{:a 1, :b 2}, {:c 3, :d 4}})
Walked: {{:a 1, :b 2} {:c 3, :d 4}}
Walked: [{:a 1, :b 2} {:c 3, :d 4}]
Walked: {:a 1, :b 2}
Walked: [:a 1]
Walked: :a
Walked: 1
Walked: [:b 2]
Walked: :b
Walked: 2
Walked: {:c 3, :d 4}
Walked: [:c 3]
Walked: :c
Walked: 3
Walked: [:d 4]
Walked: :d
Walked: 4
{{:a 1, :b 2} {:c 3, :d 4}}
user=> (traverse-post println {{:a 1, :b 2}, {:c 3, :d 4}})
:a
1
[:a 1]
:b
2
[:b 2]
{:a 1, :b 2}
:c
3
[:c 3]
:d
4
[:d 4]
{:c 3, :d 4}
[{:a 1, :b 2} {:c 3, :d 4}]
{{:a 1, :b 2} {:c 3, :d 4}}
nil
user=> (traverse-pre println {{:a 1, :b 2}, {:c 3, :d 4}})
{{:a 1, :b 2} {:c 3, :d 4}}
[{:a 1, :b 2} {:c 3, :d 4}]
{:a 1, :b 2}
[:a 1]
:a
1
[:b 2]
:b
2
{:c 3, :d 4}
[:c 3]
:c
3
[:d 4]
:d
4
nil
clojure.walk で subst や subst-if に相当する関数が postwalk と prewalk です。
prewalk proc form => new-form postwalk proc form => new-form
prewalk は通りがけ順に、postwalk は帰りがけ順に form を巡回します。form の要素を x とすると、これらの関数は要素 x を (proc x) の返り値に置き換えた新しい form を返します。簡単な実行例を示します。
user=> (w/prewalk (fn [x] (println x) x) '((1 2) (3 4))) ((1 2) (3 4)) (1 2) 1 2 (3 4) 3 4 ((1 2) (3 4)) user=> (w/postwalk (fn [x] (println x) x) '((1 2) (3 4))) 1 2 (1 2) 3 4 (3 4) ((1 2) (3 4)) ((1 2) (3 4))
prewalk-demo, postwalk-demo は prewalk, postwalk を使って実現することができます。subst, subst-if のように要素を置換する場合は、次のように if 文を使うと簡単です。
user=> (w/prewalk #(if (= % 4) 0 %) '((1 2) (3 4))) ((1 2) (3 0)) user=> (w/postwalk #(if (= % 4) 0 %) '((1 2) (3 4))) ((1 2) (3 0)) user=> (w/prewalk #(if (= % 4) 0 %) [[1 2] [3 4]]) [[1 2] [3 0]] user=> (w/postwalk #(if (= % 4) 0 %) [[1 2] [3 4]]) [[1 2] [3 0]] user=> (w/prewalk #(if (= % [3 4]) 0 %) [[1 2] [3 4]]) [[1 2] 0] user=> (w/postwalk #(if (= % [3 4]) 0 %) [[1 2] [3 4]]) [[1 2] 0]
proc に副作用が無い場合、prewalk と postwalk の結果は同じになると思われるかもしれませんが、次のように prewalk がエラーになる場合があるので注意してください。
user=> (w/postwalk list '(1 (2 (3) 4) 5)) (((1) (((2) (((3))) (4))) (5))) user=> (w/postwalk vector '(1 (2 (3) 4) 5)) [([1] [([2] [([3])] [4])] [5])] user=> (w/postwalk #(if (int? %) (list %) %) '(1 (2 (3) 4) 5)) ((1) ((2) ((3)) (4)) (5)) user=> (w/prewalk list '(1 (2 (3) 4) 5)) Execution error (StackOverflowError) at (REPL:1). null user=>(w/prewalk vector '(1 (2 (3) 4) 5)) Execution error (StackOverflowError) at (REPL:1). null user=> (w/prewalk #(if (int? %) (list %) %) '(1 (2 (3) 4) 5)) Execution error (StackOverflowError) at user/eval82$fn (REPL:1). null
list や vector のように、要素をコレクションに格納して返すと prewalk ではスタックオーバーフローになります。
Common Lisp の sublis に相当する関数が prewalk-replace と postwalk-replace です。
prewalk-replace smap form => new-form
postwalk-replace smap form => new-form
smap := {old1 new1, old2 new2 ... }
prewalk-replace は通りがけ順に、postwalk-replace は帰りがけ順に form を巡回します。引数 smap はマップで、キー old に等しい form の要素を、値 new に置換した新しい new-form を返します。簡単な実行例を示します。
user=> (w/postwalk-replace {"bar" "oops"} '("foo" "bar" "baz"))
("foo" "oops" "baz")
user=> (w/postwalk-replace {"bar" "oops"} ["foo" "bar" "baz"])
["foo" "oops" "baz"]
user=> (w/prewalk-replace {"bar" "oops"} '("foo" "bar" "baz"))
("foo" "oops" "baz")
user=> (w/prewalk-replace {"bar" "oops"} ["foo" "bar" "baz"])
["foo" "oops" "baz"]
user=> (w/postwalk-replace {:a 1 :b 2} '(:a :b (:c :b)))
(1 2 (:c 2))
user=> (w/postwalk-replace {:a 1 :b 2} '[:a :b [:c :b]])
[1 2 [:c 2]]
user=> (w/postwalk-replace {:a 1 :b 2} {{:a 10, :b 20}, {:c 30, :b 40}})
{{1 10, 2 20} {:c 30, 2 40}}
clojure.walk の簡単な使い方を説明しました。clojure.walk の詳細は Clojure のドキュメントをお読みくださいませ。
;;;
;;; sample_walk.clj : リストの巡回と置換
;;;
;;; Copyright (C) 2025 Makoto Hiroi
;;;
(require '[clojure.walk :as w])
;;; コンスセル？
(defn consp [xs]
(and (list? xs) (seq xs)))
;;; リスト (木) の巡回
(defn traverse-inorder [proc xs]
(if (not (consp xs))
(proc xs)
(do
(traverse-inorder proc (first xs))
(proc xs)
(traverse-inorder proc (rest xs)))))
(defn traverse-preorder [proc xs]
(if (not (consp xs))
(proc xs)
(do
(proc xs)
(traverse-preorder proc (first xs))
(traverse-preorder proc (rest xs)))))
(defn traverse-postorder [proc xs]
(if (not (consp xs))
(proc xs)
(do
(traverse-postorder proc (first xs))
(traverse-postorder proc (rest xs))
(proc xs))))
;;; リストの置換
(defn subst [new old xs]
(cond
(= old xs) new
(not (consp xs)) xs
:else (cons (subst new old (first xs))
(subst new old (rest xs)))))
(defn subst-if [new pred xs]
(cond
(pred xs) new
(not (consp xs)) xs
:else (cons (subst-if new pred (first xs))
(subst-if new pred (rest xs)))))
(defn sublis [alist xs]
(let [new (get alist xs)]
(cond
new new
(not (consp xs)) xs
:else (cons (sublis alist (first xs))
(sublis alist (rest xs))))))
;;; コレクションの巡回 (clojure.walk と同じ)
(defn traverse-pre [proc xs]
(proc xs)
(when (coll? xs)
(doseq [x xs]
(traverse-pre proc x))))
(defn traverse-post [proc xs]
(when (coll? xs)
(doseq [x xs]
(traverse-post proc x)))
(proc xs))