結城浩のSICP日記 RSSフィード

2006-05-11

関数list-tail 関数list-tail - 結城浩のSICP日記 を含むブックマーク

R5RSの「ペアとリスト」を読んでいます。

関数list-tailはlistから最初のk個の要素を取り除いた部分リストを返します。自作してみます。

(define (list-tail l k)
  (cond ((null? l) l)
        ((<= k 0) l)
        (else
          (list-tail (cdr l) (- k 1)))))

(list-tail '(a b c d e) 0)
;=> (a b c d e)

(list-tail '(a b c d e) 3)
;=> (d e)

(list-tail '(a b c d e) 5)
;=> ()

ここでR5RSを読み返すと「listの要素数がk個より少い場合はエラー」という条件を見逃していました。ので、仕切り直し。

(define (list-tail l k)
  (cond ((= k 0) l)
        (else
          (list-tail (cdr l) (- k 1)))))

(list-tail '(a b c d e) 0)
;=> (a b c d e)

(list-tail '(a b c d e) 3)
;=> (d e)

(list-tail '(a b c d e) 5)
;=> ()

(list-tail '(a b c d e) 6)
;*** ERROR: pair required, but got ()

R5RSに書いてあった「解答」は次の通り。

(define list-tail
  (lambda (x k)
    (if (zero? k)
        x
        (list-tail (cdr x) (- k 1)))))
  • lambdaを直接書いている。ふうん。
  • zero?を使っている。へえ。

クイズ クイズ - 結城浩のSICP日記 を含むブックマーク

クイズです。次の実行結果になるような関数quizを作りましょう。(追記:結城が用意したのはSchemeの規約に反する解答でした(^_^;)

問題

(define (f) '(0))     ;=> f
(f)                   ;=> (0)
(quiz f)
(f)                   ;=> (1)

(define (f) (list 0)) ;=> f
(f)                   ;=> (0)
(quiz f)
(f)                   ;=> (0)

…………

…………

…………

…………

もちろん解答は何種類も。

…………

…………

…………

…………

解答

(define (quiz f) (set-car! (f) 1))

疑問:set-car!の戻り値は未定義なので、何か戻り値を返したほうがよいんでしょうか。↓のように。

(define (quiz f) (set-car! (f) 1) '())

追記:shiroさんから、コメント欄にて「Schemeの規格上、定数リストは変更してはいけないことになっています」というご指摘を受けました。ありがとうございます。

追記:sumimさんがメソッド定義にリテラルを含む際の注意の最後に「イミュータブル」と書いておられたように、「書き換えられるか」というのは重要な特性の一つですね。スレッド本を書いたときも、immutabilityというのは大事なものだなあと感じました。何だかこうセキュリティと似ているんです。コンストラクタの引数で与えられたオブジェクトがmutableで、後で外部からオブジェクトのおなかの中をかき回されたり(トロイの木馬っぽい話)、オブジェクトの内部で作ったオブジェクトをメソッドの戻り値で外部に渡してしまったために後で外部からオブジェクトのおなかの中をかき回されたり…。オブジェクトをコピーすることで、外部と内部を「切る」という方法は安全ですね。

DanさんによるSICPの思い出 DanさんによるSICPの思い出 - 結城浩のSICP日記 を含むブックマーク

DanさんによるSICPの思い出

「時代はやっとlispに追いついた」や「eval()がある言語はどれもlispの香りがする」というフレーズは良いですねえ。

[]p.150:関数mystery p.150:関数mystery - 結城浩のSICP日記 を含むブックマーク

ひげぽんさんが問題3.9〜3.16のあたりをやっていたので、私も考えた。

問題3.14

(define (mystery x)
  (define (loop x y)
    (if (null? x)
        y
        (let ((temp (cdr x)))
          (set-cdr! x y)
          (loop temp x))))
  (loop x '()))

んんんん。

…………

…………

…………

…………

  • loopは要するに最初に与えられたxの各要素に関してループしている。
  • 破壊的にcdrをすげかえられたxが次回のyになる。

…………

…………

…………

わかったぞ!これは reverse!

最後の感嘆符は破壊的であることを意味している記号です:-)

ついでに、例のnamed-letの練習。

(define (mystery x)
  (let loop ((x x) (y '()))
    (if (null? x) y
        (let ((rest (cdr x)))
          (set-cdr! x y)
          (loop rest x)))))
;=> mystery

(mystery '(a b c d))
;=> (d c b a)

(define x '(a b c d))
;=> x

(mystery x)
;=> (d c b a)

x
;=> (a)

あ、本当にreverse!ってあるんだ。

(reverse! '(a b c d))
;=> (d c b a)

(define x '(a b c d))
;=> x

(reverse! x)
;=> (d c b a)

x
;=> (a)

info reverse!ですぐに見つかった。やっぱりオンラインドキュメントって楽だ♪

shiroshiro2006/05/11 07:37あー、これはGaucheにもちょっと責任があるのですが…
Schemeの規格上、定数リストは変更してはいけないことになっています。
したがって (reverse! '(a b c d)) とか (set-car! '(0) 1) とかやると、処理系によってはエラーになったり、メモリアクセス保護違反で落ちてしまうかもしれません。
(理由は、C言語で文字列定数に書き込めないのと同じです)。
Schemeの規格上はこういう場合にエラーを報告する必要がないことから、Gaucheではさぼっていますが、定数の変更はプログラムそのものを実行時に変更していることになるため、以降の動作は保証されません。
ちゃんとエラーにした方が学習者向けにはいいんですが、今の実装だと高価になるのでやっていないのです。

hyukihyuki2006/05/11 08:25> Schemeの規格上、定数リストは変更してはいけないことになっています。
あ、そうなんですね。
プログラムそのものを変更できて、やっぱりすごい!って思ってしまいましたが(^_^Λ
コメントありがとうございます。

トラックバック - http://sicp.g.hatena.ne.jp/hyuki/20060511