前回は「条件分岐」と「再帰定義」について説明しました。今回は「局所変数の定義」と「繰り返し」について説明します。
関数の中で引数以外の局所変数を定義できると便利な場合があります。Clojure には、局所変数を定義するための関数 let が用意されています。それでは、let の構文を見てみましょう。
(let [変数１ 初期値１
変数２ 初期値２
・・・・・・
変数Ｍ 初期値Ｍ]
Ｓ式１
・・・・・・
Ｓ式Ｍ)
図 : let の構文
let は特殊形式で、関数の仮引数のように与えられた名前を局所変数として扱い、その変数に初期値を評価した値を代入します。そして、後ろに続く S 式を順番に評価します。Clojure の場合、Lisp / Scheme と違って、変数と初期値はベクタの中に記述します。Lisp / Scheme は変数と初期値のペアをカッコで囲みますが、Clojure では囲む必要はありません。定義された局所変数は let の実行が終了するまで有効です。let は最後に評価した S 式の値を、let の評価結果として返します。
それでは、簡単な例をみてみましょう。
user=> (def x 10) #'user/x user=> x 10 user=> (let [x 100] (println x)) 100 nil user=> x 10
最初に def で x に 10 を代入します。この場合、変数 x は大域変数として扱われます。次の let では、まず x を局所変数として定義して 100 を代入し、(println x) を実行しています。最初の 100 は println が画面に出力したもので、次の nil が let の返り値です。let の終了後 x の値は 10 なので、確かに局所変数として扱われたことがわかります。
Clojure の let は Lisp / Scheme の let と動作が異なります。Lisp / Scheme の let は全ての初期値を評価したあと、その結果を変数にセットします。Clojure の let は初期値の評価と変数への代入を逐次的に行います。つまり、Common Lisp の let* と同じ動作になります。簡単な例を示しましょう。
user=> (def a 10) #'user/a user=> (def b 20) #'user/b user=> (let [b a c b] (println b) (println c)) 10 10 nil
Clojure の let は最初に変数 a を評価します。これは大域変数の値 10 になるので、局所変数 b は 10 に初期化されます。次に、変数 b を評価します。let により局所変数 b が作られているので、b の評価結果は 10 となり、局所変数 c は 10 に初期化されます。
それでは簡単な例題として、累乗を求める関数 pow を作ってみましょう。累乗は x の n 乗という x を n 回掛ける計算です。累乗は x の右上に小さく n を書くことで表されますが、ここでは x ** n と書くことにします。
累乗の計算 pow(x, y) = x ** y x ** 3 = x * x * x x ** 4 = x * x * x * x x ** 5 = x * x * x * x * x
今回のプログラムでは、引数 y を整数と限定します。そうすると、x ** y は次のように定義することができます。
階乗の場合と同様に、x ** y は x ** (y - 1) がわかれば求めることができます。プログラムは次のようになります。
リスト : 累乗 (1)
(defn pow [x y]
(if (zero? y)
1
(* x (pow x (dec y)))))
関数 pow は再帰定義を使って x ** y を計算しています。手続き型言語では単純な繰り返しで実現できる処理ですが、関数型言語では単純な繰り返しでも再帰定義を使ってプログラムするのが普通です。
ところで、このプログラムは n - 1 回の掛け算をしなくてはいけませんが、式を変形するともっと少ない掛け算の回数で求めることがでます。次の式を見てください。
x ** 4 = (x ** 2) ** 2 -> 2 回 x ** 8 = (x ** 4) ** 2 -> 3 回 x ** 16 = (x ** 8) ** 2 -> 4 回 一般化すると x ** y = (x ** (y / 2)) ** 2 (n は偶数) x ** y = ((x ** (y / 2)) ** 2) * x (n は奇数)
階乗の計算では n を n - 1 の計算に置き換えていきますが、累乗の場合は y を y / 2 に置き換えていくことができます。y が半分になっていくので減少の度合いが大きくなり、計算回数は少なくて済みます。これを単純にプログラムすると、次のようになります。
リスト : 累乗 (2)
(defn pow1 [x y]
(if (zero? y)
1
(if (zero? (mod y 2))
(* (pow1 x (quot y 2)) (pow1 x (quot y 2)))
(* x (pow1 x (quot y 2)) (pow1 x (quot y 2))))))
このプログラムは y が偶数の場合でも奇数の場合でも (pow1 x (quot y 2)) を 2 回呼び出しています。同じ計算を 2 回しているのは無駄ですね。そこで、let を使って局所変数を定義します。次のリストを見てください。
リスト : 累乗 (3)
(defn pow2 [x y]
(if (zero? y)
1
(let [z (pow2 x (quot y 2))]
(if (zero? (mod y 2))
(* z z)
(* x z z)))))
let で局所変数 z を定義します。z の値は x ** (y/2) です。これは pow2 を再帰呼び出しすれば簡単に求めることができます。あとは、y が偶数であれば (* z z) の値を返し、奇数であれば (* x z z) の値を返します。このように、局所変数 z に (pow2 x (quoient y 2)) の値を求めておくことで、累乗を効率的に計算することができます。
ここで、累乗 (2) のプログラムをもう一度見てください。if の中に if が入れ子になっていますね。これを図に示すと次のようになります。
↓
┌─────┐No
│ 条 件 │─────┐
└─────┘ │
↓Yes ↓
│ ┌─────┐No
│ │ 条 件 │─────┐
│ └─────┘ │
│ ↓Yes ↓
┌─────┐ ┌─────┐ ┌─────┐
│ Ｓ式Ａ │ │ Ｓ式Ｂ │ │ Ｓ式Ｃ │
└─────┘ └─────┘ └─────┘
│ │ │
↓ ↓ ↓
├────────┴────────┘
↓
図 : 複雑な条件分岐
このように、if を入れ子にすることで、複雑な条件分岐を表すことができますが、Clojure にはもっと便利な関数 cond が用意されています。cond は特殊形式で、ちょっと奇妙な構文をもっています。
(cond 条件部Ａ Ｓ式A
条件部Ｂ Ｓ式B
・・・・・
条件部Ｍ Ｓ式M
:else Ｓ式Z)
図 : cond の構造
cond には条件をチェックする述語と、条件が成立した場合に評価する S 式を並べて記述します。条件が不成立であれば、次の条件部をチェックします。Lisp / Scheme の cond とは構文が異なるので注意してください。
たとえば、条件部 A が不成立であれば、次の条件部 B をチェックします。条件部が成立したならば、その後ろにある S 式を評価し、その結果が cond の返り値となります。したがって、一度条件部が成立したら、それ以降の条件部と S 式は評価されません。
もしも、どの条件部も不成立であれば、cond の返り値は nil になります。ところで、上図ではいちばん最後の節で条件部が :else になっていますね。この節は無条件で実行されます。つまり、条件部 A から条件部 M までのすべての条件が不成立でも、最後の節が必ず選択されるのです。このように、cond を使う場合は最後の節の条件部を :else にしておくことを好むプログラマが多いようです。
名前の先頭に : を付けると、それは「キーワード (keyword)」というデータ型になります。キーワードはシンボルと似ていますが、その値は自分自身に初期化されるところが異なります。簡単な例を示しましょう。
user=> :a :a user=> :else :else
このように、:else の値は :else になります。偽 (false, nil) ではなく真なので、この条件部が必ず成立するわけです。
cond の処理を図に表すと次のようになります。
↓
┌────┐true┌───┐
│条件部Ａ│─→│Ｓ式Ａ│─→┐
└────┘ └───┘ │
↓false │
┌────┐true┌───┐ │
│条件部Ｂ│─→│Ｓ式Ｂ│─→┤
└────┘ └───┘ │
↓false │
・ │
↓ │
┌────┐true┌───┐ │
│条件部Ｍ│─→│Ｓ式Ｍ│─→┤
└────┘ └───┘ │
↓false │
┌────┐true┌───┐ │
│ :else │─→│Ｓ式Ｚ│─→┤
└────┘ └───┘ │
│
↓
図 : cond の流れ図
累乗 (2) のプログラムを cond で書き直すと次のようになります。
リスト : 累乗 (2)
(defn pow3 [x y]
(cond
(zero? y) 1
(zero? (mod y 2)) (* (pow3 x (quot y 2)) (pow3 x (quot y 2)))
:else (* x (pow3 x (quot y 2)) (pow3 x (quot y 2)))))
if を入れ子にするよりも cond を使った方がわかりやすいプログラムになると思います。
もう一つ簡単な例題として FizzBuzz 問題を解いてみましょう。FizzBuzz 問題は 1 から 100 までの値を表示するとき、3 の倍数のときは Fizz を、5 の倍数ときは Buzz を表示するというものです。FizzBuzz 問題の詳細については Fizz Buzz - Wikipedia をお読みください。
プログラムは次のようになります。
リスト : FizzBuzz 問題
(defn change [n]
(cond
(zero? (mod n 15)) 'FizzBuzz
(zero? (mod n 3)) 'Fizz
(zero? (mod n 5)) 'Buzz
:else n))
(defn fizzbuzz [n]
(when (<= n 100)
(print (change n))
(print " ")
(fizzbuzz (inc n))))
user=> (fizzbuzz 1) 1 2 Fizz 4 Buzz Fizz 7 8 Fizz Buzz 11 Fizz 13 14 FizzBuzz 16 17 Fizz 19 Buzz Fizz 22 23 Fizz Buzz 26 Fizz 28 29 FizzBuzz 31 32 Fizz 34 Buzz Fizz 37 38 Fizz Buzz 41 Fizz 43 44 FizzBuzz 46 47 Fizz 49 Buzz Fizz 52 53 Fizz Buzz 56 Fizz 58 59 FizzBuzz 61 62 Fizz 64 Buzz Fizz 67 68 Fizz Buzz 71 Fizz 73 74 FizzBuzz 76 77 Fizz 79 Buzz Fizz 82 83 Fizz Buzz 86 Fizz 88 89 FizzBuzz 91 92 Fizz 94 Buzz Fizz 97 98 Fizz Buzz nil
関数 change は引数 n をシンボル Fizz, Buzz, FizzBuzz に変換します。最初の条件部で n が 3 の倍数でかつ 5 の倍数かチェックします。これをそのままプログラムすると次のようになります。
(and (zero? (mod x 3)) (zero? (mod x 5)))
この処理は 15 の倍数をチェックすることと同じなので、関数 change では (zero? (mod x 15)) と書いています。この場合は FizzBuzz を返します。シンボルを返すのでクォート ( ' ) を付けることをお忘れなく。そうでなければ、次の条件部で n が 3 の倍数かチェックし、その次の条件部で n が 5 の倍数かチェックします。どの条件も該当しない場合は else 節で n をそのまま返します。
関数 fizzbuzz は再帰定義で 1 から 100 までの数を生成します。引数 n が 100 以下ならば、change を呼び出して引数 n を変換して、その結果を print で出力します。そのあと、 fizzbuzz を再帰呼び出しします。このとき、引数 n の値を inc で +1 します。これで (fizzbuzz 1) と呼び出せば、1 から 100 の数値を生成して、Fizz, Buzz, FizzBuzz に変換することができます。
ところで、Clojure には単純な繰り返しが用意されているので、再帰定義を使わなくても FizzBuzz 問題を解くことができます。
「繰り返し」とは、同じ処理を何度も行うことです。関数型言語の場合、繰り返しは再帰定義を使って実現するのが普通です。Lisp / Scheme の場合、単純な繰り返しであれば特殊形式 do を使って行うこともできます。ただし、Clojure の do は繰り返しではないので (Common Lisp の progn, Scheme の begin と同等の機能)、dotimes を使って説明することにします。
dotimes はマクロ [*1} で、構文は次のようになります。
(dotimes [v limit] Ｓ式 ...)
dotimes は limit で指定した回数だけ、与えられた S 式を繰り返し評価します。dotimes は最初に limit を評価します。このとき、その評価結果は 0 以上の整数値でなければいけません。評価結果を n とすると、0 から n - 1 までの整数が順番に変数 v に代入され、そのあとの S 式を評価します。
v は局所変数として扱われ、dotimes が評価されている間だけ有効です。最後に nil を返します。次の例を見てください。
user=> (dotimes [x 5] (println x)) 0 1 2 3 4 nil
この処理は変数 x の値を println で表示するだけですが、繰り返すたびに x の値が 1 つずつ増えていくことがわかります。最後の nil は dotimes の返り値です。これを図に表すと次のようになります。
↓
┌─────┐
│ x ← 0 │
└─────┘
├←────┐
↓ │
No ┌─────┐ │
┌───│ x < 5 │ │
│ └─────┘ │
│ ↓Yes │
│ ┌─────┐ │
│ │(print x) │ │
│ └─────┘ │
│ ↓ │
│ ┌─────┐ │
│ │x ← x + 1│ │
│ └─────┘ │
│ └─────┘
└──────┐
↓
図 : dotimes の処理
それでは簡単な例を見てみましょう。FizzBuzz 問題を dotimes でプログラムします。
リスト : dotimes の使用例
(defn fizzbuzz0 []
(dotimes [n 100]
(print (change (inc n)))
(print " ")))
user=> (fizzbuzz0) 1 2 Fizz 4 Buzz Fizz 7 8 Fizz Buzz 11 Fizz 13 14 FizzBuzz 16 17 Fizz 19 Buzz Fizz 22 23 Fizz Buzz 26 Fizz 28 29 FizzBuzz 31 32 Fizz 34 Buzz Fizz 37 38 Fizz Buzz 41 Fizz 43 44 FizzBuzz 46 47 Fizz 49 Buzz Fizz 52 53 Fizz Buzz 56 Fizz 58 59 FizzBuzz 61 62 Fizz 64 Buzz Fizz 67 68 Fizz Buzz 71 Fizz 73 74 FizzBuzz 76 77 Fizz 79 Buzz Fizz 82 83 Fizz Buzz 86 Fizz 88 89 FizzBuzz 91 92 Fizz 94 Buzz Fizz 97 98 Fizz Buzz nil
dotimes は 0 から始まるので、change に渡すときは inc で n を +1 することをお忘れなく。
次は doseq を説明しましょう。doseq もマクロで、構文も dotimes とたいへんよく似ています。
(doseq [v1 init-form1] Ｓ式 ... )
doseq は名前が示すように、シーケンスに関係があります。最初に init-form1 を評価します。このとき、評価結果はシーケンスリストでなければいけません。doseq は、このリストの要素を順番に変数 v1 に代入して S 式を評価します。リストの要素がなくなったら doseq は nil を返します。次の例を見てください。
(doseq [x '(1 2 3 4 5)] (println x)) 1 2 3 4 5 nil
この処理は局所変数 x の値を println で表示するだけですが、繰り返しのたびにリストの要素が x に代入されていることがわかります。最後の nil は doseq の返り値です。これを図に表すと次のようになります。
↓
├←────┐
No ┌─────┐ │
┌───│要素がある│ │
│ └─────┘ │
│ ↓Yes │
│ ┌───────┐ │
│ │ x ← 次の要素│ │
│ └───────┘ │
│ ↓ │
│ ┌─────┐ │
│ │(print x) │ │
│ └─────┘ │
│ └─────┘
└──────┐
↓
図 : doseq の処理
doseq は変数とシーケンスの組を複数指定することができます。その場合は多重ループになります。簡単な例を示しましょう。
user=> (doseq [x '(1 2 3) y '(a b c)] (println (list x y))) (1 a) (1 b) (1 c) (2 a) (2 b) (2 c) (3 a) (3 b) (3 c) nil
再帰定義のなかで、最後に再帰呼び出しを行う場合を「末尾再帰」といいます。英語では tail recursion ですが、日本語では末尾再帰のほかに「末端再帰」とか「終端再帰」と訳すことがあります。末尾再帰は簡単な処理で「繰り返し」に変換することができます。これを「末尾再帰最適化」[*2] といいます。
Lisp / Scheme などの関数型言語や論理型言語の Prolog では、プログラムをコンパイルするときに、この最適化を行う処理系があります。Scheme の場合、仕様書 (RnRS) に末尾再帰最適化を行うことが明記されています。ただし、Clojure は末尾再帰最適化を行いません。そのかわり、特別な構文 recur を使うと末尾再帰最適化と同じ効果を得ることができます。
たとえば、階乗を求める関数 fact を思い出してください。
リスト : 階乗の計算
(defn fact [n]
(if (zero? n)
1
(* n (fact (dec n)))))
fact は最後に x と fact の返り値を乗算しているので、このプログラムは末尾再帰ではありません。これを末尾再帰に変換すると、次のようになります。
リスト : 階乗の計算 (末尾再帰)
(defn facti [n a]
(if (zero? n 0)
a
(facti (dec n) (* n a))))
(defn fact [n] (facti n 1))
fact は関数 facti を呼び出すだけで、実際の計算は facti で行っています。 facti は最後の再帰呼び出しで facti の返り値をそのまま返しているので、このプログラムは末尾再帰になっています。これで階乗を計算できるなんて、ちょっと不思議な感じがしますね。まあ、そこが再帰呼び出しの面白いところです。このプログラムでは変数 a の使い方がポイントです。
たとえば (facti 4) を実行すると、このプログラムでは 4 * 3 * 2 * 1 を計算しています。このとき、計算の途中経過を変数 a に記憶しているのです。末尾再帰最適化を適用する前の facti の呼び出しを図に示すと、次のようになります。
(facti 4 1)
(facti 3 4)
(facti 2 12)
(facti 1 24)
(facti 0 24)
=> a の値 24 を返す
=> 24
=> 24
=> 24
=> 24
図 : facti の呼び出し
変数 a には計算途中の値が格納されていることがわかります。このような変数を「累算変数」とか「累算器」といいます。純粋な関数型言語の場合、dotimes のような単純な繰り返しは用意されていないのが普通です。また、論理型言語の Prolog にも単純な繰り返しはありません。
これらの言語では、繰り返しのかわりに末尾再帰を使ってプログラミングを行います。そして、末尾再帰最適化によりプログラムを高速に実行することができます。
Clojure は末尾再帰最適化を行わないので、関数呼び出しが深くなると、末尾再帰でプログラムしても stack overflow が発生します。Clojure の場合、関数を末尾呼び出しするのではなく、関数名のかわりに recur を使います。次の例を見てください。
リスト : 階乗の計算 (recur による繰り返し)
(defn facti [n a]
(if (zero? n 0)
a
(recur (dec n) (* n a))))
(defn fact [n] (facti n 1))
recur の引数は、defn で定義した関数の引数と同じでなければいけません。defn と recur を一緒に使うことで、末尾再帰を繰り返しに変換して実行することができます。この場合、stack overflow は発生しません。
なお、マルチアリティ関数を使うと、以下のように関数を一つにまとめることができます。
リスト : 階乗の計算 (マルチアリティ関数)
(defn fact
([n] (fact n 1))
([n a]
(if (zero? n)
a
(recur (dec n) (* a n)))))
もう一つ、簡単な例を示しましょう。1 から n までの総和を求める関数を末尾再帰で定義します。
user=> (defn sumi [n a] (if (zero? n) a (sumi (dec n) (+ a n)))) #'user/sumi user=> (sumi 1000 0) 500500 user=> (sumi 10000 0) Execution error (StackOverflowError) at user/sumi (REPL:1). null user=> (defn sumr [n a] (if (zero? n) a (recur (dec n) (+ a n)))) #'user/sumr user=> (sumr 1000 0) 500500 user=> (sumr 10000 0) 50005000 user=> (sumr 100000 0) 5000050000
関数 sumi は 1 から n までの総和を末尾再帰で求めています。Clojure は末尾再帰を最適化しないので、n の値が大きくなると stack overflow します。それに対して、関数 sumr は末尾呼び出しのところで recur を使っています。これにより、sumr は繰り返しに変換されて、n の値が大きくなっても stack overflow しないで総和を求めることができます。
次はリストを反転する reverse を作りましょう。Clojure には同様の処理を行う関数 reverse が用意されているので、関数名を my-reverse とします。reverse はリストを first と rest で分解して、残りのリストを反転させてから先頭の要素を最後尾に追加することで実現できます。プログラムは次のようになります。
リスト : リストの反転
(defn my-reverse [ls]
(if-not (seq ls)
'()
(append (my-reverse (rest ls)) (list (first ls)))))
append で反転したリストの最後尾に先頭の要素を追加します。再帰の停止条件は ls が空リストになるときです。この場合は空リストを返します。簡単なプログラムですが append を使っているので、リストが長くなると時間がかかるのが欠点です。そこで、次に示すように補助的な関数を用意します。
リスト : リストの反転 (改良版)
(defn reversei [ls a]
(if (null? ls)
a
(reversi (cdr ls) (cons (car ls) a))))
(defn my-reverse [ls] (reversei ls '()))
関数 reversei は、リスト ls の先頭要素を引数 a の先頭に追加していきます。したがって、(reversei ls '()) と呼び出せば、リスト ls を反転することができます。reversei は末尾再帰になっていることに注意してください。関数呼び出しを図に示すと、次のようになります。
(reversei '(1 2 3 4) '())
(reversei '(2 3 4) '(1))
(reversei '(3 4) '(2 1))
(reversei '(4) '(3 2 1))
(reversei '() '(4 3 2 1))
=> a の値 (4 3 2 1) を返す
=> (4 3 2 1)
=> (4 3 2 1)
=> (4 3 2 1)
=> (4 3 2 1)
図 : reversei の呼び出し
このように、引数 a には反転途中のリストが格納されていることがわかります。ここで、末尾呼び出しの reversi を recur に変更すると、reversi を繰り返しに変換することができます。
なお、マルチアリティ関数を使うと、関数を一つにまとめることができます。
リスト : リストの反転 (改良版２)
(defn my-reverse
([ls] (my-reverse ls '()))
([ls a]
(if-not (seq ls)
a
(recur (rest ls) (cons (first ls) a)))))
もうひとつ簡単な例を示しましょう。フィボナッチ (fibonacci) 関数も再帰的に定義される関数です。
フィボナッチ関数も再帰定義を使えば簡単にプログラムできます。
リスト : フィボナッチ関数
(defn fibo [n]
(if (< n 2)
n
(+ (fibo (dec n)) (fibo (- n 2)))))
関数 fibo は fact とは違い、自分自身を 2 回呼び出しています。これを「二重再帰」といいます。fibo の関数呼び出しをトレースすると下図のようになります。
f(5) ┬ f(4) ┬ f(3) ┬ f(2) ┬ f(1)
│ │ │ │
│ │ │ └ f(0)
│ │ └ f(1)
│ └ f(2) ┬ f(1)
│ │
│ └ f(0)
│
└ f(3) ┬ f(2) ┬ f(1)
│ │
│ └ f(0)
└ f(1)
図 : 関数 fibo のトレース
同じ値を何回も求めているため、効率はとても悪いのです。そこで、累算変数を使って二重再帰を末尾再帰へ変換してみましょう。プログラムは次のようになります。
リスト : フィボナッチ関数 (末尾再帰)
(defn fiboi [n a b]
(if (zero? n)
a
(fiboi (dec n) b (+ a b))))
(defn fibo [n] (fiboi n 0 1))
累算変数 a と b の使い方がポイントです。現在のフィボナッチ数を変数 a に、ひとつ先の値を変数 b に格納しておきます。あとは a と b を足し算して、新しいフィボナッチ数を計算すればいいわけです。fiboi の呼び出しを図に示すと、次のようになります。
(fiboi 5 0 1)
(fiboi 4 1 1)
(fiboi 3 1 2)
(fiboi 2 2 3)
(fiboi 1 3 5)
(fiboi 0 5 8)
=> a の値 5 を返す
=> 5
=> 5
=> 5
=> 5
=> 5
図 : fiboi の呼び出し
二重再帰では、同じ値を何回も求めていたため効率がとても悪かったのですが、このプログラムでは無駄な計算を行っていないので、値を高速に求めることができます。さらに、末尾呼び出しの fiboi を recur に変更すると、末尾再帰が繰り返しに変換されるので、プログラムを高速に実行することができます。
なお、マルチアリティ関数を使うと、関数を一つにまとめることができます。
リスト : フィボナッチ関数 (改良版)
(defn fibo
([n] (fibo n 0 1))
([n a b]
(if (zero? n)
a
(recur (dec n) b (+ a b)))))
末尾再帰 (recur による繰り返し) は実行速度やメモリの消費量など効率の点で有利です。このため、何がなんでも末尾再帰でプログラムしようとする方がいるかもしれません。ところが、再帰定義を使うと簡単にプログラムできるが、末尾再帰に変換するとプログラムがとても複雑になってしまう、というアルゴリズムもあります。したがって、とくに問題がなければ、再帰定義をむりやり末尾再帰へ変換する必要はないでしょう。わかりやすいプログラムがいちばんだと思います。
さて、今までのプログラムは defn / recur で末尾再帰を繰り返しに変換していました。この他に、Clojure には loop / recur という構文があり、これを使うと末尾再帰 (繰り返し) を簡単に定義することができます。これは Scheme の named let と同じ機能です。
loop / recur の構文を示します。
(loop [変数１ 初期値１
変数２ 初期値２
・・・・・・
変数Ｍ 初期値Ｍ]
Ｓ式１
・・・
Ｓ式Ｍ
(recur 引数１ ... 引数Ｍ))
図 : loop / recur の構文
loop を関数の中で定義された局所関数と考えてください。loop の後ろに定義される変数が loop の引数になり、loop の中の S 式がその関数の処理内容になります。そして、loop の末尾で recur を呼び出すと、loop / recur は末尾再帰 (繰り返し) になります。
簡単な例を示しましょう。次のリスト見てください。
リスト : 名前付き let の使用例
;;; 階乗の計算
(defn fact [n]
(loop [n n a 1]
(if (zero? n)
a
(recur (dec n) (* a n)))))
;;; リストの反転
(defn my-reverse [ls]
(loop [ls ls a '()]
(if (empty? ls)
a
(recur (rest ls) (cons (first ls) a)))))
;;; フィボナッチ関数
(defn fibo2 [n]
(loop [n n a 0 b 1]
(if (zero? n)
a
(recur (dec n) b (+ a b)))))
loop / recur を使うと、マルチアリティ関数よりもプログラムは簡単になります。fact の定義 (loop [n n a 1] ...) のように、変数と初期値の指定に同じ名前 n を使っていますが、前の n は let の中で有効な変数名になり、後ろの n は引数の n で初期値になります。この場合、let の変数 n が引数 n を隠蔽することになるので、let の中から引数 n の値にアクセスすることはできなくなります。ご注意ください。
今回はここまでです。簡単に復習しておきましょう。
次の関数を定義してください。
user=> (defn length [xs] (loop [xs xs k 0] (if-not (seq xs) k (recur (rest xs) (inc k))))) #'user/length user=> (length '()) 0 user=> (length '(1 2 3 4 5)) 5 user=> (length '(1 2 3 4 5 4 3 2 1)) 9 user=> (defn longer [xs ys] (cond (and (seq xs) (seq ys)) (recur (rest xs) (rest ys)) (seq xs) true :else false)) #'user/longer? user=> (longer? '(a b c) '(a b)) true user=> (longer? '(a b c) '(a b c)) false user=> (longer? '(a b c) '(a b c d)) false user=> (defn my-take [n xs] (if (and (pos? n) (seq xs)) (cons (first xs) (my-take (dec n) (rest xs))) '())) #'user/my-take user=> (my-take 3 '(a b c d e)) (a b c) user=> (my-take 0 '(a b c d e)) () user=> (my-take 5 '(a b c d e)) (a b c d e) user=> (my-take 6 '(a b c d e)) (a b c d e) user=> (defn my-drop [n xs] (if (and (pos? n) (seq xs)) (recur (dec n) (rest xs)) xs)) #'user/my-drop user=> (my-drop 3 '(a b c d e)) (d e) user=> (my-drop 0 '(a b c d e)) (a b c d e) user=> (my-drop 5 '(a b c d e)) () user=> (my-drop 6 '(a b c d e)) () user=> (defn sum-list [xs] (loop [xs xs a 0] (if-not (seq xs) a (recur (rest xs) (+ a (first xs)))))) #'user/sum-list user=> (sum-list '(1 2 3 4 5)) 15 user=> (sum-list '()) 0 user=> (sum-list '(1 2 3 4 5 6 7 8 9 10)) 55 user=> (defn product [xs] (loop [xs xs a 1] (if-not (seq xs) a (recur (rest xs) (* a (first xs)))))) #'user/product user=> (product '()) 1 user=> (product '(1 2 3 4 5 6 7 8 9 10)) 3628800