M.Hiroi's Home Page

Functional Programming

お気楽 Scheme プログラミング入門

[ PrevPage | Scheme | NextPage ]

Scheme の基礎知識 [4]

前回は「条件分岐」と「再帰定義」について説明しました。今回は「局所変数の定義」と「繰り返し (末尾再帰)」について説明します。

●let による局所変数の定義

関数の中で引数以外の局所変数を定義できると便利な場合があります。Scheme では、局所変数を定義するための関数 let が用意されています。それでは、let の構文を見てみましょう。

(let ((変数1 初期値1)
      (変数2 初期値2)
        ・・・・・・
      (変数M 初期値M))

    S式1
  ・・・・・・
    S式M)

    図 : let の構文

let はシンタックス形式で、関数の仮引数のように与えられた名前を局所変数として扱い、その変数に初期値を評価した値を代入します。そして、後ろに続く S 式を順番に評価します。Scheme の場合、Common Lisp と違って初期値を省略することはできません。定義された局所変数は let の実行が終了するまで有効です。let は最後に評価した S 式の値を、let の評価結果として返します。

それでは、簡単な例をみてみましょう。

gosh[r7rs.user]> (define x 10)
x
gosh[r7rs.user]> (let ((x 100)) (display x))
100#<undef>
gosh[r7rs.user]> x
10

最初に define で x に 10 を代入します。この場合、変数 x は大域変数として扱われます。次の let では、まず x を局所変数として定義して 100 を代入し、(display x) を実行しています。最初の 100 は display が画面に出力したもので、次の #<undef> が let の返り値です。let の終了後 x の値は 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 は次のように定義することができます。

累乗の定義
\(\begin{array}{l} x ** \ 0 = 1 \\ x ** \ y = x \times (x ** \ (y - 1)) \end{array}\)

階乗の場合と同様に、x ** y は x ** (y - 1) がわかれば求めることができます。プログラムは次のようになります。

リスト : 累乗 (1)

(define (pow x y)
  (if (= y 0)
      1
      (* x (pow x (- y 1)))))

関数 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)

(define (pow1 x y)
  (if (= y 0)
      1
      (if (= (modulo y 2) 0)
          (* (pow1 x (quotient y 2)) (pow1 x (quotient y 2)))
          (* x (pow1 x (quotient y 2)) (pow1 x (quotient y 2))))))

このプログラムは y が偶数の場合でも奇数の場合でも (pow1 x (quotient y 2)) を 2 回呼び出しています。同じ計算を 2 回しているのは無駄ですね。そこで、let を使って局所変数を定義します。次のリストを見てください。

リスト : 累乗 (3)

(define (pow2 x y)
  (if (= y 0)
      1
      (let ((z (pow2 x (quotient y 2))))
        (if (= (modulo y 2) 0)
            (* 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 が入れ子になっていますね。これを図に示すと次のようになります。


                図 : 複雑な条件分岐

このように、if を入れ子にすることで、複雑な条件分岐を表すことができますが、Lisp / Scheme にはもっと便利な関数 cond が用意されています。cond はシンタックス形式で、ちょっと奇妙な構文をもっています。

(cond ( 条件部A S式A1 S式A2 ... )
      ( 条件部B S式B1 S式B2 ... )
        ・・・・・
      ( 条件部M S式M1 S式M2 ... )
      ( else     S式Z1 S式Z2 ... ))

          図 : cond の構造

cond は複数の節 (リスト) を引数として受け取ります。各節の先頭には条件をチェックする述語があり、条件が成立した場合、残りの S 式を評価します。条件が不成立であれば、次の節に移ります。

たとえば、条件部 A が不成立であれば、次の節の条件部 B をチェックします。条件が成立したならば、同じ節にある S 式を順番に評価していきます。そして、いちばん最後に評価された S 式の評価結果が cond の返り値となります。したがって、一度節が選択されたら、それ以降の節は評価されません。

もしも、どの条件部も不成立であれば、cond の返り値は未定義です。Gauche では #<undef> を返します。ところで、上図ではいちばん最後の節で条件部が else になっていますね。この節は無条件で実行されます。つまり、条件部 A から条件部 M までのすべての条件が不成立でも、最後の節が必ず選択されるのです。このように、cond を使う場合は最後の節の条件部を else にしておくことを好むプログラマが多いようです。

cond の処理を図に表すと次のようになります。

累乗 (2) のプログラムを cond で書き直すと次のようになります。

リスト : 累乗 (2)

(define (pow1 x y)
  (cond
   ((= y 0) 1)
   ((= (modulo y 2) 0)
    (* (pow1 x (quotient y 2)) (pow1 x (quotient y 2))))
   (else
    (* x (pow1 x (quotient y 2)) (pow1 x (quotient y 2))))))

if を入れ子にするよりも cond を使った方がわかりやすいプログラムになると思います。

●繰り返し

「繰り返し」とは、同じ処理を何度も行うことです。関数型言語の場合、繰り返しは再帰定義を使って実現するのが普通です。Scheme もそうなのですが、単純な繰り返しであればシンタックス形式 do を使って行うこともできます。ただし、Scheme の do は少々わかりにくいので、R5RS, R7RS-small にはありませんが Gauche で用意されている while を使って説明することにします。

while は条件が真の間、S 式を繰り返し実行します。次の図を見てください。

(while 条件部 処理A 処理B 処理C)

         図 : while の処理

while はシンタックス形式 [*1] です。図を見ればおわかりのように、while はいたって単純です。しかしながら、注意しなければならないポイントがあります。それは、条件部が偽にならないと繰り返しを停止しない、つまり、「無限ループ」に陥ってしまうことです。たとえば、指定した回数 Scheme を表示するプログラムを while を使って作ってみましょう。

リスト : while のテスト (バグあり)

(define (test x)
  (let ((n 0))
    (while (< n x)
      (display "Scheme\n"))))

このプログラムは正常に動作しません。画面に Scheme をずっと表示し続けるので、CTRL-C を入力して実行を止めるしかありません。

どこが悪いのかわかりますか。while の実行が終了しないのですから、条件部が成立したままになっているのでしょう。条件は n が x より小さいときに成立しますね。よく見てみると、n は 0 に初期化されていますが、そのあと n の値は増やされていませんね。これがプログラムが正常に動作しない原因です。n は 0 のままですから、while の条件部は偽になることがなかったわけです。

このように、プログラムを作っていると、正常に動作しないことがよくあります。私たち人間が行うことに完璧なものはありません。とくに、プログラムが大きくなると機能すべてが正常に動作する、ということは滅多にないことのです。つまり、プログラムのどこかに間違いが隠れているわけですね。

このプログラムの誤りを「バグ (bug)」といいます。そして、プログラムの誤りを直すことを「デバッグ (debug)」といいます。また、バグは虫という意味なので、「虫取り」ということもあります。このプログラムは、次のように修正すると正常に動作します。

リスト : while のテスト(修正版)

(define (test x)
  (let ((n 0))
    (while (< n x)
      (display "Scheme\n")
      (set! n (+ n 1)))))
gosh> (test 10)
Scheme
Scheme
Scheme
Scheme
Scheme
Scheme
Scheme
Scheme
Scheme
Scheme
#t

最後の行で、n の値をひとつずつ増やしていく処理を追加します。Scheme を表示するたびに n の値は増えていくので、x 回表示した時点で条件部を満たさなくなり while の実行が停止するのです。

このように、while を使うと set! で変数 n の値を書き換える処理が必要になるため、手続き型言語のようなプログラムになってしまいます。関数型言語の場合、単純な繰り返しは「末尾再帰」という再帰定義でプログラムするのが普通です。Scheme の場合も単純な繰り返しは末尾再帰を使うことが多いようです。

-- note --------
[*1] 正確にいうと、Gauche は「マクロ (macro)」で while を定義しています。マクロを使うと、シンタックス形式の関数を定義することができます。

●末尾再帰

再帰定義のなかで、最後に再帰呼び出しを行う場合を「末尾再帰」といいます。英語では tail recursion ですが、日本語では末尾再帰のほかに「末端再帰」とか「終端再帰」と訳すことがあります。末尾再帰は簡単な処理で「繰り返し」に変換することができます。これを「末尾再帰最適化」[*2] といいます。

Lisp / Scheme などの関数型言語や論理型言語の Prolog では、プログラムをコンパイルするときに、この最適化を行う処理系があります。Scheme の場合、仕様書 (RnRS) に末尾再帰最適化を行うことが明記されています。したがって、仕様に準拠している Scheme 処理系であれば末尾再帰最適化が必ず行われます。

末尾再帰最適化が行われると関数の再帰呼び出しは while のような繰り返しに変換されるので、関数呼び出しのオーバーヘッドがなくなります。末尾再帰最適化が行われないと、関数呼び出しが行われるたびにメモリ領域が消費されるため、再帰呼び出しが深くなる (回数が多くなる) と、メモリ領域を使い切ってプログラムの実行ができなくなる場合があります。また、一般に関数呼び出しは繰り返しに比べると少し時間がかかる処理なので、末尾再帰最適化が行われるとプログラムを高速に実行できる場合があります。

たとえば、階乗を求める関数 fact を思い出してください。

リスト : 階乗の計算

(define (fact n)
  (if (= n 0)
      1
      (* n (fact (- n 1)))))

fact は最後に x と fact の返り値を乗算しているので、このプログラムは末尾再帰ではありません。これを末尾再帰に変換すると、次のようになります。

リスト : 階乗の計算 (末尾再帰)

(define (facti n a)
  (if (= n 0)
      a
      (facti (- n 1) (* n a))))

(define (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 には計算途中の値が格納されていることがわかります。このような変数を「累算変数」とか「累算器」といいます。純粋な関数型言語の場合、while のような繰り返しは用意されていないのが普通です。また、論理型言語の Prolog にも単純な繰り返しはありません。

これらの言語では、繰り返しのかわりに末尾再帰を使ってプログラミングを行います。そして、末尾再帰最適化によりプログラムを高速に実行することができます。

ところで、関数 facti は fact からしか呼び出されていません。このような場合、facti は局所的な関数として定義するといいでしょう。Scheme の場合、関数の中でも define を使って関数を定義することができます。プログラムは次のようになります。

リスト : 階乗の計算 (末尾再帰)

(define (fact n)
  ;; 局所関数の定義
  (define (facti n a)
    (if (= n 0)
        a
        (facti (- n 1) (* n a))))
  ;; 呼び出し
  (facti n 1))

Lisp / Scheme では、セミコロン ( ; ) から行末までがコメントになります。関数の中で define を使う場合、その関数の先頭で定義するようにしてください。関数 facti は fact の中で定義されているので fact の中でのみ有効です。fact 以外の関数から呼び出すことはできません。このように、Scheme は局所的な関数を簡単に定義することができます。

-- note --------
[*2] 末尾再帰最適化は一般的な呼び方で、厳密には「末尾呼び出し最適化」とか「末尾最適化」といいます。詳しい説明は拙作のページ 関数型電卓プログラム fncalc の作成 (4) 末尾再帰とは? をお読みください。

●リストの反転

次はリストを反転する reverse を作りましょう。Scheme には同様の処理を行う関数 reverse が用意されているので、関数名を my-reverse とします。reverse はリストを car と cdr で分解して、残りのリストを反転させてから先頭の要素を最後尾に追加することで実現できます。プログラムは次のようになります。

リスト : リストの反転

(define (my-reverse ls)
  (if (null? ls)
      '()
      (append (my-reverse (cdr ls)) (list (car ls)))))

append で反転したリストの最後尾に先頭の要素を追加します。再帰の停止条件は ls が空リストになるときです。この場合は空リストを返します。簡単なプログラムですが append を使っているので、リストが長くなると時間がかかるのが欠点です。そこで、次に示すように補助的な関数を用意します。

リスト : リストの反転 (改良版)

(define (my-reverse ls)
  ;; 局所関数の定義
  (define (reversei ls a)
    (if (null? ls)
        a
        (reversei (cdr ls) (cons (car ls) a))))
  ;; 呼び出し
  (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 には反転途中のリストが格納されていることがわかります。

●フィボナッチ関数

もうひとつ簡単な例を示しましょう。フィボナッチ (fibonacci) 関数も再帰的に定義される関数です。

フィボナッチ関数の定義

\( fibo(n) = \begin{cases} 0, & if \ n = 0 \\ 1, & if \ n = 1 \\ fibo(n - 1) + fibo(n - 2), & if \ n \gt 1 \end{cases} \)

0, 1, 1, 2, 3, 5, 8, 13 .... という直前の 2 項を足していく数列

フィボナッチ関数も再帰定義を使えば簡単にプログラムできます。

リスト : フィボナッチ関数

(define (fibo n)
  (if (< n 2)
      n
      (+ (fibo (- n 1)) (fibo (- n 2)))))

関数 fibo は fact とは違い、自分自身を 2 回呼び出しています。これを「二重再帰」といいます。fibo の関数呼び出しをトレースすると下図のようになります。


            図 : 関数 fibo のトレース

同じ値を何回も求めているため、効率はとても悪いのです。そこで、累算変数を使って二重再帰を末尾再帰へ変換してみましょう。プログラムは次のようになります。

リスト : フィボナッチ関数 (末尾再帰)

(define (fibo1 n)
  ;; 局所関数の定義
  (define (fiboi n a b)
    (if (zero? n)
        a        (fiboi (- n 1) b (+ a b))))
  ;; 呼び出し
  (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 の呼び出し

二重再帰では、同じ値を何回も求めていたため効率がとても悪かったのですが、このプログラムでは無駄な計算を行っていないので、値を高速に求めることができます。もちろん、末尾再帰になっているので、末尾再帰最適化を行う Scheme では、プログラムを高速に実行できるでしょう。

末尾再帰は実行速度やメモリの消費量など効率の点で有利です。このため、何がなんでも末尾再帰でプログラムしようとする方がいるかもしれません。ところが、再帰定義を使うと簡単にプログラムできるが、末尾再帰に変換するとプログラムがとても複雑になってしまう、というアルゴリズムもあります。したがって、とくに問題がなければ、再帰定義をむりやり末尾再帰へ変換する必要はないでしょう。わかりやすいプログラムがいちばんだと思います。

●名前付き let

さて、今までのプログラムは局所的な関数を define で定義しましたが、Scheme には局所的な関数を定義するシンタックス形式 letrec と名前付き let (named let) が用意されています。とくに、末尾再帰は名前付き let を使うと簡単にプログラムすることができます。ここで名前付き let を簡単に説明しましょう。

名前付き let はその名が示すように let に名前を付けたものです。名前付き let の構文を示します。

(let 名前
   ((変数1 初期値1)
    (変数2 初期値2)
      ・・・・・・
    (変数M 初期値M))

  S式1
  ・・・
  S式M
  (名前 引数1 ... 引数M))

図 : 名前付き let の構文

名前付き let は、let の後ろに名前を指定します。この名前が関数名になると考えてください。その後ろに定義される変数がその関数の引数になり、let の中の S 式がその関数の処理内容になります。そして、let の中でその関数を呼び出すことができ、let の最後で再帰呼び出しを行えば末尾再帰になります。

簡単な例を示しましょう。次のリスト見てください。

リスト : 名前付き let の使用例

;;; 階乗の計算
(define (fact n)
  (let iter ((n n) (a 1))
    (if (= n 0)
        a
        (iter (- n 1) (* a n)))))

;;; リストの反転
(define (my-reverse ls)
  (let iter ((ls ls) (a '()))
    (if (null? ls)
        a
        (iter (cdr ls) (cons (car ls) a)))))

;;; フィボナッチ関数
(define (fibo2 n)
  (let iter ((n n) (a 0) (b 1))
    (if (= n 0)
        a
        (iter (- n 1) b (+ a b)))))

名前付き let を使うと、define で局所関数を定義するよりもプログラムは簡単になります。fact の定義 (let iter ((n n) (a 1)) のように、変数と初期値の指定に同じ名前 n を使っていますが、前の n は let の中で有効な変数名になり、後ろの n は引数の n で初期値になります。この場合、let の変数 n が引数 n を隠蔽することになるので、let の中から引数 n の値にアクセスすることはできなくなります。ご注意ください。

●繰り返しと再帰定義

ところで、「繰り返しがあるから再帰定義なんていらないのでは?」と思った方もいるかもしれませんね。実際、末尾再帰は次のリストのように繰り返しに変換することができます。

リスト : 末尾再帰を繰り返しに変換

;;; 階乗
(define (fact n)
  (let ((a 1))
    (while (< 0 n)
      (set! a (* a n))
      (set! n (- n 1)))
    a))

;;; リストの反転
(define (my-reverse ls)
  (let ((a '()))
    (while (pair? ls)
      (set! a (cons (car ls) a))
      (set! ls (cdr ls)))
    a))

;;; フィボナッチ関数
(define (fibo n)
  (let ((a 0) (b 1) (c 0))
    (while (< 0 n)
      (set! c (+ a b))
      (set! a b)
      (set! b c)
      (set! n (- n 1)))
    a))

ところが、繰り返しは再帰定義に変換することができますが、その逆は必ずしもできるとは限りません。つまり、簡単な繰り返しでは実現できない処理があるのです。

たとえば、リストに含まれるアトムの個数を求めるプログラムを考えてみましょう。この場合、リストの要素がリストであれば、そのリストに含まれるアトムの個数をカウントしないといけません。そして、そのリストの要素にリストがあれば・・・、という具合に、リストの階層構造をたどっていかなくてはいけません。このような処理は、単純な繰り返しでは実現できません。再帰定義を使った方が簡単にプログラムすることができます。

それでは、アトムの個数を求めるプログラムを作ってみましょう。関数名は count-atom とします。まず、引数が空リストであれば 0 を返せばいいですね。そして、引数がアトムであれば 1 を返します。では、引数がリストだったらどうするのでしょうか。ここで悩む必要はありません。これも再帰すればいいのです。先頭の要素を count-atom で処理したら、次は残りのリストを count-atom で処理します。全体の結果は、再帰呼び出しした count-atom の返り値を足し算すればいいのです。

これをそのままプログラミングすると、次のようになります。

リスト : リスト中のアトムを数える

(define (count-atom ls)
  (cond
   ((null? ls) 0)
   ((not (pair? ls)) 1)
   (else
    (+ (count-atom (car ls))
       (count-atom (cdr ls))))))

最初に、引数 ls が空リストかチェックします。そうであれば 0 を返します。次に、引数 ls がアトムかチェックします。not は「否定」といって、真偽値を反転する関数です。引数が #f だと #t を返し、#f 以外の引数は #f を返します。Lisp / Scheme では、リスト以外のデータがアトムなので、(pair? ls) の結果を not で反転すればいいわけです。ls がアトムであれば 1 を返します。

ls がリストの場合、最後の else 節が評価されます。引数 ls に car と cdr を適用してリストを分解し、それぞれに対し count-atom を再帰呼び出しします。そして、その評価結果を足し算します。

このように、リストの階層構造をたどる場合、リストを car と cdr に分解して再帰呼び出しする手法は、Lisp / Scheme ではよく用いられる常套手段なので覚えておいてください。

●まとめ

今回はここまでです。簡単に復習しておきましょう。

  1. let は局所変数を設定する。
  2. cond は複雑な条件分岐を表すのに便利である。
  3. while は条件部が真の間、処理を繰り返す。
  4. 単純な繰り返しは末尾再帰で実現できる。
  5. 局所的な関数は define や名前付き let で定義できる。
  6. セミコロンから行末までがコメントになる。
  7. 末尾再帰は名前付き let を使うと簡単にプログラムできる。
  8. not は真偽値を反転する関数である。

今回で Scheme の基礎知識は終了です。次回は数当てゲームを題材に、ちょっとだけ複雑なプログラミングに挑戦しましょう。お楽しみに。

●問題

次の関数を定義してください。

  1. リスト xs の長さを求める関数 my-length xs
  2. リスト xs はリスト ys よりも長いか調べる述語 longer? xs ys
  3. リスト xs の先頭から n 個の要素を取り出す関数 take xs n
  4. リスト xs の先頭から n 個の要素を取り除く関数 drop xs n
  5. リストの要素を足し算する関数 sum-list xs
  6. リストの要素を掛け算する関数 product xs
-- note --------
[*3] Scheme の仕様書 R5RS は必要最低限の機能しか定義されていないため、多くの Scheme 処理系で機能追加や拡張が行われています。この拡張機能の標準化を目的に SRFI (Scheme Requests For Implementation) という仕様が定められています。Gauche でも多くの SRFI がサポートされています。その中で、SRFI-1 にはリスト操作を行う関数が多数定義されています。












●解答

gosh[r7rs.user]> (define (my-length xs) 
(let iter ((xs xs) (c 0))
  (if (null? xs) c (iter (cdr xs) (+ c 1)))))
my-length
gosh[r7rs.user]> (my-length '())
0
gosh[r7rs.user]> (my-length '(a b c d e))
5

gosh[r7rs.user]> (define (longer? xs ys)
(cond ((null? xs) #f)
      ((null? ys) #t)
      (else (longer? (cdr xs) (cdr ys)))))
longer?
gosh[r7rs.user]> (longer? '(a b c) '(a b))
#t
gosh[r7rs.user]> (longer? '(a b c) '(a b c))
#f
gosh[r7rs.user]> (longer? '(a b c) '(a b c d))
#f

gosh[r7rs.user]> (define (take xs n)
(if (zero? n) '() (cons (car xs) (take (cdr xs) (- n 1)))))
take
gosh[r7rs.user]> (take '(a b c d e) 0)
()
gosh[r7rs.user]> (take '(a b c d e) 3)
(a b c)
gosh[r7rs.user]> (take '(a b c d e) 5)
(a b c d e)
gosh[r7rs.user]> (take '(a b c d e) 6)
=> ERROR

gosh[r7rs.user]> (define (drop xs n)
(if (zero? n) xs (drop (cdr xs) (- n 1))))
drop
gosh[r7rs.user]> (drop '(a b c d e) 0)
(a b c d e)
gosh[r7rs.user]> (drop '(a b c d e) 3)
(d e)
gosh[r7rs.user]> (drop '(a b c d e) 5)
()
gosh[r7rs.user]> (drop '(a b c d e) 6)
=> ERROR

gosh[r7rs.user]> (define (sum-list xs)
(let iter ((xs xs) (a 0)) (if (null? xs) a (iter (cdr xs) (+ a (car xs))))))
sum-list
gosh[r7rs.user]> (sum-list '())
0
gosh[r7rs.user]> (sum-list '(1 2 3 4 5))
15

gosh[r7rs.user]> (define (product xs)
(let iter ((xs xs) (a 1)) (if (null? xs) a (iter (cdr xs) (* a (car xs))))))
product
gosh[r7rs.user]> (product '())
1
gosh[r7rs.user]> (product '(1 2 3 4 5 6 7 8 9 10))
3628800

初版 2007 年 12 月 23 日
改訂 2020 年 8 月 23 日

Copyright (C) 2007-2020 Makoto Hiroi
All rights reserved.

[ PrevPage | Scheme | NextPage ]