前回は「変数」と「評価」について説明して、基本的なリスト操作を行う関数を紹介しました。今回は「条件分岐」と「再帰定義」について説明します。
条件分岐は難しい話ではありません。たとえば、「暑いからアイスコーヒーを飲もう」とか、「雨が降りそうだから傘を持っていこう」というように、私たちはそのときの状況によって自分の行動を決めています。プログラミングの世界でも、状況によって次に実行する処理を選択しなければならないことがよくあります。これを「条件分岐」といいます。
先ほどの例では、「暑いから・・・」と「雨が降りそうだから・・・」が「条件」を示しています。ただし、このままでは条件部分があいまいなので、もっと具体的に条件部を書き換えてみます。
「もしも気温が 30 ℃以上であれば、アイスコーヒーを飲む」
~~~~~~~~~~~~~~~~
「もしも降水確率が 50 ％以上であれば、傘を持っていく」
~~~~~~~~~~~~~~~~~~~~
これだと条件部がよくわかると思います。そして、実際に「気温が 30 ℃以上になる」ことを「条件を満たす」または「条件が成立する」といいます。条件が成立したときに「アイスコーヒーを飲む」という行動が実行されます。降水確率が 40 ％であれば、条件が成立しないので、「傘を持っていく」という行動は実行されません。
これを図に示すと、次のようになります。
↓ ↓
┌─────┐false ┌─────┐false
│ 条 件 │─┐ │ 条 件 │─────┐
└─────┘ │ └─────┘ │
↓true │ ↓true ↓
┌─────┐ │ ┌─────┐ ┌─────┐
│ 処理Ａ │ │ │ 処理Ａ │ │ 処理Ｂ │
└─────┘ │ └─────┘ └─────┘
│ │ │ │
├←───┘ ├←───────┘
↓ ↓
(1) (2)
図 : 条件分岐
(1) では、「もしも条件を満たすならば、処理 A を実行する」となります。この場合、条件が成立しないと処理は何も実行されませんが、(2) のように条件が成立しない場合でも処理を実行することができます。(2) の場合では、「もしも条件を満たすならば、処理 A を実行し、そうでなければ処理 B を実行する」となります。すなわち、条件によって処理 A か処理 B のどちらかが実行されることになります。
プログラミングの世界では、条件が成立することを「真 (true)」といい、条件が不成立のことを「偽 (false)」といいます。実際のプログラミングでは、true と false を表すデータが必要になります。Clojure の場合、真偽を表すデータ型 (boolean) として true と false が用意されていますが、Clojure では false と nil を偽と判断し、それ以外の値を真と判断します。true は真を表すデータの代表として使います。
それでは、Clojure で条件分岐を表してみましょう。Clojure には、条件分岐を実行する関数がいくつかありますが、いちばん簡単な関数が if です。if は英語で「もしも」という意味ですから、まさに条件分岐そのものを表しています。if の基本的な使い方は次のようになります。
(if <条件部> <処理Ａ> <処理Ｂ>)
if は 3 つの引数を受け取りますが、特殊形式なので評価されずにそのまま if に渡されます。最初に、if は <条件部> を評価します。この評価結果が false, nil 以外の値であれば、条件を満たしていると判断し、処理 A を評価します。この場合、処理 B は評価されません。
評価結果が false, nil であれば、処理 B を評価します。この場合、処理 A は評価されません。また、条件部が成立したときに実行する処理を「then 節」、不成立のときに実行する処理を「else 節」といいます。
関数型言語では、条件部で使用する関数を「述語 (predicate)」といいます。述語は真か偽を返す関数です。先ほど説明したように、false, nil 以外の値は真と判断されるのですが、条件を満たす場合、述語は true を返します。true は真を表す代表選手なのです。
それでは、実際にプログラミングしてみましょう。「もしも気温が 30 ℃以上であれば、アイスコーヒーを飲む」をプログラムしてみましょう。
リスト : 飲物を選ぶプログラム
(defn select-drink [degree]
(if (<= 30 degree)
(print "Drink ice coffee\n")
(print "Don't drink ice coffee\n")))
関数名や変数名には、その機能を表す名前をつけるようにしましょう。この場合、名前は selectdrink と続けて書くよりも、間に '-' (ハイフン) を含めたほうが、一目でわかるようになります。関数名にハイフンを使うことができないプログラミング言語では、'_' (アンダーライン) を使って select_drink と書くことで同様の効果を得ることができます。
このほかに SelectDrink や selectDrink のように大文字を使う場合もあります。一般に、Lisp 言語では単語と単語の間をハイフンで繋ぐことが多いようです。
select-drink は、気温 degree によって飲物を選びます。<= は数値を比較する述語です。右側の引数が左側の引数以上であれば true を返し、そうでなければ false を返します。ここで数値を比較する述語をまとめて紹介しましょう。
Lisp 言語では、数の等値は = で判定するのが一般的ですが、Clojure では == を使うことに注意してください。これらの述語は、右側に書いた数式の関係を満たせば true を返し、そうでなければ false を返します。引数は 2 つ以上与えてもかまいません。数値は整数値以外にも実数や有理数 (分数) を使うことができます。
それでは実際に select-drink を実行してみましょう。
user=> (select-drink 35) Drink ice coffee <== print による画面表示 nil <== select-drink の返り値 user=>
まず、述語 (<= 30 degree) が評価されます。degree は 35 なので条件を満たし、then 節である (print "Drink ice coffee\n") が評価されます。print の副作用により画面に Drink ice coffee が表示され、print の返り値が if の返り値となり、それが select-drink の返り値となって nil が表示されます。
複数の述語を組み合わせる場合は特殊形式 and と or を使います。
(and Ｓ式１ Ｓ式２ Ｓ式３ Ｓ式４ ..... ) (or Ｓ式１ Ｓ式２ Ｓ式３ Ｓ式４ ..... )
and は複数の述語を「～かつ～」で結ぶ働きをします。and は与えられた S 式を左から順番に評価します。そして、S 式の評価結果が false であれば、残りの S 式を評価せずに false を返します。最後まで S 式が false に評価されなかった場合は、いちばん最後の S 式の評価結果を返します。
or は複数の述語を「～または～」で結ぶ働きをします。or は and と違い、S 式の評価結果が false 以外の場合に、残りの S 式を評価せずにその評価結果を返します。すべての S 式が false に評価された場合は false を返します。それでは、簡単な例を示しましょう。
user=> (defn check-number [x] (and (< 10 x) (<= x 20))) #'user/check-number user=> (defn check-number-else [x] (or (>= 10 x) (> x 20))) #'user/check-number-else user=> (check-number 15) true user=> (check-number-else 15) false user=> (check-number 30) false user=> (check-number-else 30) true
最初の例は、引数 x が 10 より大きくて、かつ 20 以下の場合 true を返します。次の例はその逆で、x が 10 以下、または 20 より大きい場合 true を返します。
check-number と check-number-else は逆の関係です。いちいち 2 つの関数を作らなくても結果を逆にすればいいはずです。この場合は not を使います。not は引数が偽 (false or nil) ならば true を返し、それ以外ならば false を返す関数です。つまり、真と偽をひっくり返す働きをします。これを「否定」といいます。ひらたくいえば、「～ではない」という意味になります。次の例を見てください。
user=> (check-number 15) true user=> (not (check-number 15)) false
このように not を使うことで、述語の判定を逆にすることができます。
関数 if は条件部が不成立になったときに実行する処理を省略することができます。
リスト : 飲物を選ぶプログラム
(defn select-drink1 [degree]
(if (<= 30 degree)
(print "Drink ice coffee\n")))
条件部が不成立で実行する処理がない場合、Clojure は nil を返します。
if の else 節が存在しない場合には、if の代わりに when を使うことができます。逆に、if の then 節で評価する処理が無い場合には when-not を使うことができます。
(when test Ｓ式１ Ｓ式２ Ｓ式３ ..... )
when は最初に test を評価しその結果が真であれば、S 式を順番に評価して最後の S 式の評価結果を返します。test の結果が偽ならば、その後ろの S 式は評価しません。このときの返り値は nil になります。
when-not は when とは逆の働きをします。述語が偽に評価されたときに、引数の S 式を順番に評価します。when-not は述語 not を使うと、次のように whenを使って表すことができます。
(when-not test Ｓ式１ ...) ≡ (when (not test) Ｓ式１ ...)
if の場合、then 節や else 節はひとつの S 式しか受け付けませんが、when や when-not では、複数の S 式を引数として受け取ることができます。
ここで、Clojure で用意されている数と算術演算についてまとめておきましょう。Clojure は大きく分けると整数、有理数 (分数)、実数という 3 種類の数があります。なお、Common Lisp と Scheme は複素数をサポートしていますが、Clojure は標準ではサポートしていません。ご注意くださいませ。
Clojure の整数には二種類あって、ひとつは Java の Long で、もうひとつがの Java の BigInt (多倍長整数) です。整数の後ろに N を付けると BigInt になります。また、プログラムや REPL で整数を入力するとき、Long の範囲を超えると BigInt に変換されます。
Common Lisp の場合、整数は fixnum (固定長整数) と bignum (多倍長整数) に分けられますが、数値演算で fixnum の範囲を超えると bignum に拡張されます。これは Scheme でも同じです。Clojure の場合、Long 同士の演算で結果が Long の範囲を超えると long overflow というエラーになります。BigInt に拡張する関数も用意されていて、関数名の後ろに ' を付けます。
簡単な例を示しましょう。
user=> (* 4611686018427387904 2) Execution error (ArithmeticException) at java.lang.Math/multiplyExact (Math.java:1032). long overflow user=> (*' 4611686018427387904 2) 9223372036854775808N user=> (* 4611686018427387904 2N) 9223372036854775808N user=> (* 4611686018427387904N 2) 9223372036854775808N
Long と BigInt の演算は Long を BigInt に変換して行われるので、long overflow は起こりません。
整数は通常 10 進表記ですが、次に示す基数でも書くことができます。
簡単な例を示しましょう。
2r10101010 => 170 01234567 => 342391 -0127 => -87 0xabcdef => 11259375
Clojure は有理数 (分数) を扱うことができます。有理数は 2 つの整数を / で区切って表します。簡単な例を示します。
1/2, 2/3, 4/3, 11/13, -51/100, 30517578125/32768
また、4/6 や 3/12 のような入力もできますが、この場合は約分されることになります。とくに、4/2 のような割り切れる有理数は、ただちに整数に変換されます。次の例を見てください。
4/6 => 2/3 3/12 => 1/4 10/5 => 2 ; 整数に変換される
Clojure で扱うことのできる実数は、浮動小数点数 (Java の Double) と Java の BigDecimal の二種類があります。末尾に M を付けると BigDecimal になります。
浮動小数点の表記法は次のようになります。
[+|-] 数字 小数点 数字 指数マーカ [+|-] 数字 例： 0.1234, 1.2345e10, -9.876542999999999e-100
指数マーカは e と E が使えます。
次は簡単な算術演算を説明します。
+ は足し算を、* は掛け算を、- は引き算を行います。これらの関数は引数をいくつでも取ることができます。数以外のデータを引数に与えるとエラーになります。引数の型が異なる場合は強制的に型変換が行われます。簡単な例を示しましょう。
(+) => 0 (+ 1) => 1 (+ 1 2 3) => 6 (+ 1 2 3 1/2) => 13/2 (+ 1 2 3 4.5) => 10.5 (*) => 1 (* 1) => 1 (* 1 2 3) => 6 (* 1 2 3 1/4) => 3/2 (* 1 2 3 4.5) => 27.0 (- 1) => -1 (- 10 5 4) => 1 (- 10 5/2) => 15/2 (- 10 4.5) => 5.5 (-) => Error ; 引数が足りない
/ は割り算を行います。整数同士の割り算で割り切れない場合は分数になります。0 で割り算したとき、引数が整数の場合はエラーになります。引数が実数の場合、Clojure は ##Inf または##-Inf という無限大を表すデータを返します。
(/ 2) => 1/2 ; 引数の逆数を求める (/ 8 4 2) => 1 ; 約分されて整数になる (/) => Error ; 引数が足りない (/ 1 0) => Error ; 0 で除算した場合 (/ 1.0 0) => ##Inf (/ -1 0.0) => ##-Inf
2 つの整数 n1 と n2 の商は関数 quot で、剰余は関数 rem, mod で求めることができます。
(quot 4 2) => 2 (rem 4 2) => 0 (mod 4 2) => 0 (quot 5 2) => 2 (rem 5 2) => 1 (mod 5 2) => 1 (quot -5 2) => -2 (rem -5 2) => -1 (mod -5 2) => 1 (quot 5 -2) => -2 (rem 5 -2) => 1 (mod 5 -2) => -1
quot は n1 / n2 が割り切れない場合、0 の方向へ丸めた値を返します。rem は n1 / n2 の剰余で、その符号は n1 と同じになります。mod も n1 / n2 の剰余ですが、その符号は n2 と同じになります。
このほかにも、Clojure には数値演算に関する関数がたくさん用意されています。興味のある方は Closure のリファレンスマニュアルをお読みください。
条件分岐が理解できると、同じ処理を何回も繰り返すプログラムを書くことができるようになります。まずは簡単な例として、階乗を計算するプログラムを考えてみます。
階乗の定義からわかるように、n の階乗を求めるには (n - 1) の階乗の答えがわかれば求めることができます。実は、これをそのままプログラミングすることができるのです。
リスト : 階乗を計算する
(defn fact [n]
(if (zero? n)
1
(* n (fact (dec 1)))))
述語 zero? は引数が 0 ならば真を返します。pos? は引数が正ならば真を返し、neg? は引数が負ならば真を返します。偶数と奇数を判定する述語 even?, odd? もあります。関数 dec は引数を -1 します。引数を +1 する関数 inc もあります。これらの関数は以下に示す Common Lisp の関数と同じです。
Clojure Common Lisp --------------------- zero? zerop pos? plusp neg? minusp even? evenp odd? oddp inc 1+ dec 1-
Clojure や Scheme の場合、述語には ? マークを付ける習慣があります。
本当にこれで階乗を計算できるのか、実際に試してみると次のような計算結果となります。
n = 0 => 1 n = 1 => 1 n = 2 => 2 n = 3 => 6 n = 4 => 24 n = 5 => 120 n = 6 => 720 n = 7 => 5040 n = 8 => 40320 n = 9 => 362880
確かに階乗の答えを求めることができるようです。なお、fact は Long 同士で計算しているので、long overflow が発生します。if の then 節の 1 を 1N に修正すると BigInt で計算されるので、大きな階乗でも求めることができます。
それでは、関数の処理内容について詳しく見ていきましょう。関数 fact の内容は、「もしも n が 0 ならば 1 を返し、そうでなければ、(* n (fact (dec n))) を実行する」というものです。条件が成立する場合が、0! = 1 を表していることは直ぐに理解できると思います。問題は条件が不成立になる場合です。
(* n (fact (dec n))) では、n * (n - 1)! を計算しています。この S 式で注目すべき点は、(n - 1)! を求めるときに、関数 fact 自身を再び呼び出しているところです。これを「再帰定義 (recursive definition)」とか「再帰呼び出し (recursive call)」といいます
関数の定義に自分自身を使うことができるなんて、何か特別な仕掛があるのではないかと思われるかもしれません。筆者が最初に再帰定義を見たときは、ヘビが自分の尻尾を食べていくような奇妙な感覚に陥って、なかなか理解できませんでした。
ところが、再帰定義は特別なことではありません。ましてや、Lisp 言語の専売特許でもないのです。Ｃ言語や Pascal など近代的なプログラミング言語であれば、再帰定義を使うことができるのです。残念なことですが、Lisp などの関数型言語以外では、再帰定義は難しいテクニックのひとつと思い込んでしまい、初心者の方は避けて通ることが多いように思います。
実は、再帰呼び出しは、今まで説明した関数の呼び出しとまったく同じなので、難しく考える必要はないのです。とくに関数型言語の場合、再帰定義を積極的に活用してプログラミングを行うので、初心者の方が覚えるべき基礎テクニックのひとつにすぎません。慣れるまでちょっと苦労するかもしれませんが、ポイントさえつかめば簡単に使いこなすことができるようになります。
それでは、このプログラムの動作を説明します。
┌───── (fact 4) => 24 ─────┐
│ n = 4 │
│ (* 4 (fact 3)) │
│ │
│┌──── (fact 3) => 6 ────┐│
││ n = 3 ││
││ (* 3 (fact 2)) ││
││ ││
││┌─── (fact 2) => 2 ───┐││
│││ n = 2 │││
│││ (* 2 (fact 1)) │││
│││ │││
│││┌── (fact 1) => 1 ──┐│││
││││ n = 1 ││││
││││ (* 1 (fact 1)) ││││
││││ ││││
││││┌─ (fact 0) => 1 ─┐││││
│││││ n = 0 │││││
│││││ 1 │││││
││││└──────────┘││││
│││└────────────┘│││
││└──────────────┘││
│└────────────────┘│
└──────────────────┘
図 : 再帰呼び出し
fact に 4 を与えて呼び出してみましょう。引数 n には 4 が代入されます。この引数 n の値は (fact 4) が実行されている間有効です。上図では、そのことを枠で示しています。この場合、n は 0 ではないので、else 節が実行されます。最初の枠の中を見てください。ここで n の値から １ 引いた値で自分自身を呼び出しています。
次に、2 番目の枠の中を見てください。引数 n には 3 が代入されます。ここで、関数を実行するときの動作を思い出してください。Clojure は引数 n に対応するメモリ領域を割り当て、その領域に実引数を書き込み、関数本体を実行するのでしたね。再帰呼び出しであっても、普通の関数呼び出しには違いありません。
したがって、(fact 3) を実行する場合も、引数 n に対応するメモリ領域を割り当て、そこに実引数である 3 を代入します。つまり、(fact 4) と (fact 3) の呼び出しでは、引数 n に割り当てられるメモリ領域は異なっているのです。ここが再帰呼び出しを理解するポイントのひとつです。
プログラムを見ると引数 n はひとつしかないように見えますが、関数を呼び出すたびに、局所変数は新しいメモリ領域に割り当てられていくのです。したがって、(fact 4) を呼び出したときの n の値が更新されるのではなく、(fact 4) を実行しているときの n は 4 で、(fact 3) を実行しているときの n は 3 なのです。再帰呼び出しが行われるたびに、新しい変数 n がメモリ領域に割り当てられていくと考えてください。
同様に (fact 2), (fact 1), (fact 0) と順番に呼び出していきます。(fact 0) の場合、n は 0 ですから then 節が実行されます。ここで再帰呼び出しが止まります。ここが第 2 のポイントです。
停止条件を作らなかったり、作ってもその条件を満たさないならプログラムは正常に動作しません。停止条件がなかったり条件を満たさない場合、関数呼び出しが限りなく行われるので、Clojure のシステム資源 (メモリ) を食い潰し、いつかはプログラムの実行ができなくなります。
(fact 0) は 1 を返します。実行が終了したので、引数 n の値は元に戻ります。これも局所変数の特徴でしたね。では、どの値に戻るのでしょうか。関数を呼び出した場合、それを呼び出した関数に必ず戻ってきます。この場合は (fact 0) が終了したので、(fact 1) の実行に戻るのです。(fact 1) の実行は終了していないので、引数 n の値は 1 に戻ります。図でいえば、実行が終了したら枠が壊れていくと考えてください。いちばん内側の枠が壊れて、その前に値を代入された局所変数が顔を出すのです。
(fact 0) が 1 を返してきたので、(fact 1) を計算することができます。(* 1 1) を評価して (fact 1) は 1 を返します。同様に、順番に値を計算していき、最後に (fact 4) の値を求めることができるのです。
基本的なポイントを押さえたら、あとは「習うより慣れろ」です。そこで、再帰定義を使って、リスト操作を行う関数を作ってみましょう。実は、リスト操作と再帰定義は相性が良いのです。これが Lisp 言語で再帰定義が頻繁に使われる理由でもあります。
それでは手始めに、リストの n 番目の要素を求めるプログラムを作ってみましょう。Lisp 言語の場合、リストの要素は 0 から数えます。したがって、リストの先頭の要素は 0 番目の要素となります。Scheme には list-ref、Common Lisp と Clojure には nth という関数がありますが、私たちでも簡単にプログラムすることができます。関数名は retrieve とし、引数に数値 n とリスト ls を与えます。
n : 2 ls : (1 2 3 4) │
│ やさしい問題へ置き換えていく
n : 1 ls : (2 3 4) │
│
n : 0 ls : (3 4) ↓
=> first を適用し 3 を取り出す
図 : retrieve の考え方
リスト ls の 0 番目の要素を求めることは簡単に実現できます。リストの先頭の要素を取り出す関数 first を適用すればいいだけです。それでは、n 番目の要素を求めるにはどうしたらいいのでしょうか。実はこれも簡単です。階乗の計算を思い出してください。n! を求めるには (n - 1)! がわかれば十分でした。リスト ls の n 番目の要素は、ls の先頭の要素を取り除いたリストの n - 1 番目の要素がわかればいいのです。
再帰定義の場合、複雑な問題を簡単な問題へ置き換えるように考えていきます。階乗の場合は、n! が 0! まで簡単になりましたね。この場合も、n 番目の要素を 0 番目の要素になるように再帰させるのです。これをプログラムすると次のようになります。
リスト : リストの n 番目の要素を取り出す
(defn retrieve [ls n]
(when-not (empty? ls))
(if (zero? n)
(first ls)
(retrieve (rest ls) (dec n)))))
関数 empty? は、引数が空のコレクション (collection) であれば真を返す述語です。複数のデータを格納するデータ構造をコレクションとかコンテナといいます。リストのほかにも、Clojure にはベクタ、マップ (連想配列)、セット (集合) といったコレクションが標準でサポートされています。これらのデータ型は empty? で要素の有無を判定することができます。簡単な例を示しましょう。
user=> (empty? '()) true user=> (empty? '(1 2 3)) false user=> (empty? []) true user=> (empty? [1 2 3]) false
Clojure スタイルガイド によると、『シーケンスが空かどうかをチェックするには seq を使う（このテクニックはしばしば nil punning と呼ばれる）』 とのことです。seq はコレクションをシーケンス (列) に変換する関数で、コレクションが空の場合は nil を返します。簡単な例を示しましょう。
user=> (seq '()) nil user=> (seq '(1 2 3)) (1 2 3) user=> (seq []) nil user=> (seq [1 2 3]) (1 2 3)
空リストの判定に empty? を用いても retrieve は問題なく動作しますが、今後はスタイルガイドに従って seq で空リストを判定することにしましょう。ちなみに、Lisp / Scheme には空リストを判定する専用の述語が用意されていて、Common Lisp では null を、Scheme では null? を使います。
処理内容は簡単です。もしも ls が空リストならば nil を返します。n が 0 ならば、リスト ls に first を適用して先頭の要素を返します。この 2 つが再帰呼び出しの停止条件になります。そうでなければ、retrieve を再帰呼び出しします。このとき、リスト ls に rest を適用して先頭の要素を取り除き、n の値を -1 します。
それでは実際に動かしてみましょう。
user=> (retrieve '(a b c d) 0) a user=> (retrieve '(a b c d) 1) b user=> (retrieve '(a b c d) 2) c user=> (retrieve '(a b c d) 3) d user=> (retrieve '(a b c d e) 5) nil user=> (retrieve '(a b c d e) -1) nil
正常に動作していますね。
次は、前回紹介したリストとリストを結合する関数 concat を作ってみましょう。関数名は append とし、引数としてリスト xs と ys を渡して、それを結合したリストを返します。名前は Common Lisp, Scheme から拝借しました。
再帰に慣れていないと、どうしたらよいのか見当もつかないかもしれません。retrieve のときと同様に、簡単な場合から考えていきましょう。まず、リスト xs が空リスト () ならば、リスト ys を返すだけでいいですね。次に、リスト xs に要素がひとつしかない場合を考えてみます。これはリスト xs に car を適用して要素を取り出し、それを cons でリスト ys の先頭に追加すればいいでしょう。
┌────────────────────────────┐
│(append '(1 2) '(3 4)) │
├────────────────────────────┤
│ ( 1 2 ) │
│ ┬ ── rest ─┐ │
│ first ↓ │
│ │ ┌──────────────────────┐│
│ │ │(append '(2) '(3 4)) ││
│ │ ├──────────────────────┤│
│ │ │ ( 2 ) ││
│ │ │ ┬ ─ rest ─┐ ││
│ │ │ first ↓ ││
│ │ │ │ ┌────────────────┐││
│ │ │ │ │(append () '(3 4)) => (3 4) │││
│ │ │ │ └────────────────┘││
│ │ │ │ │ ││
│ │ │ └→ cons ←─┘ ││
│ │ │ (2 3 4) ││
│ │ └─────┼────────────────┘│
│ └──→ cons ←─┘ │
└──────┼─────────────────────┘
↓
(1 2 3 4)
図 : append の動作
ここでちょっと考えてみてください。xs が空リストの場合は ys をそのまま返しますよね。それでは、「リスト ys の先頭に追加する」という処理は、「空リストとリスト ys を結合したリストの先頭に追加する」と置き換えることができるはずです。リスト xs に cdr を適用すれば空リストになりますから、この処理は再帰定義で実現できるはずです。
つまり、リスト xs とリスト ys を結合するには、リスト xs の cdr とリスト ys を結合したリストに、リスト xs の car を cons すればいいのです。これを図に示すと上図のようになります。プログラムは次のようになります。
リスト : リストの結合
(defn append [xs ys]
(if-not (seq xs)
ys
(cons (first xs) (append (rest xs) ys))))
(if-not pred ...) は (if (not pred) ...) と同じです。Clojure では (if (not pred) ...) よりも if-not を使うことが多いようです。ちなみに、Common Lisp, Scheme に if-not はありません。
if-not で xs が空リストかチェックし、そうであればリスト ys をそのまま返します。そうでなければ、リスト xs に rest を適用した値を append に渡して再帰呼び出しします。その結果とリスト xs の first を cons で接続すればいいのです。それでは、実際に実行してみましょう。
user=> (append '(a b) '(c d)) (a b c d) user=> (append '((a b) (c d)) '((e f) (g h))) ((a b) (c d) (e f) (g h))
正常に動作していますね。
今回はここまでです。最後に、今まで説明したことについて、簡単に復習しておきましょう。
次回は「局所変数の定義」と「繰り返し」について説明します。お楽しみに。
次の関数を定義してください。
user=> (defn divisor? [m n] (zero? (mod m n))) #'user/divisor? user=> (divisor? 15 3) true user=> (divisor? 15 5) true user=> (divisor? 15 7) false user=> (defn three-or-five-multiple [n] (or (divisor? n 3) (divisor? n 5))) #'user/three-or-five-multiple user=> (three-or-five-multiple 9) true user=> (three-or-five-multiple 10) true user=> (three-or-five-multiple 11) false user=> (defn between [n low high] (<= low n high)) #'user/between user=> (between 5 1 10) true user=> (between 0 1 10) false user=> (between 20 1 10) false user=> (defn single? [xs] (and (not (empty? xs)) (empty? (rest xs)))) #'user/single? user=> (single? '(a)) true user=> (single? '(a b)) false user=> (single? '()) false