Hatena::Groupsicp

a666666の日記 このページをアンテナに追加 RSSフィード

2010-01-10

P04 (*) Find the number of elements of a list.

| 23:40 | P04 (*) Find the number of elements of a list. - a666666の日記 を含むブックマーク はてなブックマーク - P04 (*) Find the number of elements of a list. - a666666の日記 P04 (*) Find the number of elements of a list. - a666666の日記 のブックマークコメント

リストの長さを求めよ、ってことかな。 length を自分で書けってことだと解釈してやってみる。 The Little Lisper に書いてあったので覚えてる。

(define (mylength l)
  (cond ((null? l) 0)
        (else (+ 1 (mylength (cdr l))))))
(mylength '(a b c))
;; => 3
(mylength '())
;; => 0

P05 (*) Reverse a list.

| 00:43 | P05 (*) Reverse a list. - a666666の日記 を含むブックマーク はてなブックマーク - P05 (*) Reverse a list. - a666666の日記 P05 (*) Reverse a list. - a666666の日記 のブックマークコメント

リストを逆順にするのか。 reverse を自前で。全然わかんない。再帰ってほんとイメージできない。

(define (myreverse l)
  (cond ((null? l) '())
        (else (cons (myreverse (cdr l)) (cons (car l) '())))))
(myreverse '(a b c))

うーん。。惜しいところまでいってると思うんだけど、余計な () が増え過ぎちゃう。

答えみてしまったら意味ないよなぁ。でもわかんないままなのは悔しいなぁ。

追記

(define (myreverse l)
  (cond
   ((null? l) '())
   (else (append (myreverse (cdr l)) (cons (car l) '())))))
(myreverse '(a b c d))
;; => (d c b a)

できた!...けど g000001 さんにヒントをもらったのでやっぱり自力では解けなかったな...。 append を使うとできるようだ。 cons では無理なのかなぁ。どうしても append を使いたくなかったら自分で myappend でも書くしかないのだろうか。

組み込みライブラリの reverse を使ったら解く意味ないよなぁと思って、他の組み込み関数を探して使うことまでダメだと思い込んでしまっていた。既存のものをどこまで使っていいかの切り分けを考えるのが難しそう。

append 使ったら解決した、だけだと勉強にならないので、 The Little Schemer に書いてあったのと同じ方式で、具体的に値を置き換えて再帰をたどっていき、どういう風に動作しているかを追ってみる。

;; 一回目
(myreverse '(a b c d))
~~~~~~~~~~(1)~~~~~~~~~
(null? '(a b c d)) ; => #f なので else を実行
;; (cdr l) => (b c d)
;; (car l) => a
;; (cons (car l) '()) => (a)
(else (append (myreverse '(b c d)) (a))) ; 再帰
              ~~~~~~~~~(2)~~~~~~~~

;; 二回目
(myreverse '(b c d))
(null? '(b c d)) ; => #f なので else を実行
;; (cdr l) => (c d)
;; (car l) => b
;; (cons (car l) '()) => (b)
(else (append (myreverse '(c d)) (b))) ; 再帰
              ~~~~~~~~~(3)~~~~~~

;; 三回目
(myreverse '(c d)
(null? '(c d)) ; => #f なので else を実行
;; (cdr l) => (d)
;; (car l) => c
;; (cons (car l) '()) => (c)
(else (append (myreverse '(d)) (c))) ; 再帰
              ~~~~~~~(4)~~~~~~

;; 四回目
(myreverse '(d))
(null? '(d)) ; => #f なので else を実行
;; (cdr l) => ()
;; (car l) => d
;; (cons (car l) '()) => (d)
(else (append (myreverse '()) (d)) ; 再帰
              ~~~~~~~(5)~~~~~

;; 五回目
(myreverse '())
(null? '()) ; => #t なので '() を返す。再帰終了。

;; (5) (4) (3) (2) (1) の順に、再帰の内側から実際の帰り値で置き換えていく

;; (5)
(myreverse '()) ; => '()

;; (4)
(myreverse '(d)) ; => (append (myreverse '()) (d))
                 ; => (append '() (d))
                 ; => (d)

;; (3)
(myreverse '(c d)) ; => (append (myreverse '(d)) (c))
                   ; => (append (apend (myreverse '()) (d)) (c))
                   ; => (append (append '() (d)) (c))
                   ; => (append (d) (c))
                   ; => (d c)

;; (2)
(myreverse '(b c d)) ; => (append (myreverse '(c d)) (b))
                     ; => (append (append (myreverse '(d)) (c)) (b))
                     ; => (append (append (append (myreverse '()) (d)) (c)) (b))
                     ; => (append (append (append '() (d)) (c)) (b))
                     ; => (append (append (d) (c)) (b))
                     ; => (append (d c) (b))
                     ; => (d c b)

;; (1)
(myreverse '(a b c d) ; => (append (myreverse '(b c d) (a)))
                      ; => (append (append (myreverse '(c d)) (b)) (a))
                      ; => (append (append (append (myreverse '(d)) (c)) (b)) (a))
                      ; => (append (append (append (append (myreverse '()) (d)) (c)) (b)) (a))
                      ; => (append (append (append (append '() (d)) (c)) (b)) (a))
                      ; => (append (append (append (d) (c)) (b)) (a))
                      ; => (append (append (d c) (b)) (a))
                      ; => (append (d c b) (a))
                      ; => (d c b a)

やっぱり、再帰に慣れるまでは面倒でもこうやって具体的な置き換えで考えていったほうがいいかな。さすがにここまで細かく分解すれば俺にも理解できる。

さらに追記

append に相当するものを使わずに書けるらしいので、引き続き考える。のだけどその前に解答をちらっと読んでみたら、なんと append を使っていなかった。。下請けの関数を定義するやり方が正解らしい。じっくり読んでないとはいえ、さっと見ただけだとさっぱり意味が分からなかったのでかなりへこむ。がしかし、そのほうが自分の頭で考える余地があるという点では良かったのかもしれない。

(define (myreverse List)
  (_myreverse (cdr List) (car List)))
(define (_myreverse List Atom)
  (cond
   ((null? List) Atom)
   (else
    (cons (_myreverse (cdr List) (car List))
          (cons Atom '())))))

(myreverse '(a b c d))
;; => (((d c) b) a) になってしまう

(define (myreverse List)
  (_myreverse (cdr List) (car List)))
(define (_myreverse List Atom)
  (cond
   ((null? List) Atom)
   (else
    (cons Atom (_myreverse (cdr List) (car List))))))

(myreverse '(a b c d))
;; => (a b c . d) になってしまう

どうもうまくいかない。↓こーいう形にならないといけないということはわかるのだが、どうすればそういう実行結果になるようにもっていけるかがまだわからない。ちなみに下のコードは単に gosh で (d c b a) を cons だけで作ってみたらこういう風になったというだけ。。

(cons 'd (cons 'c (cons 'b (cons 'a '()))))

追記3

結局 http://www.shido.info/lisp/scheme7.html に書いてあるのを読んだりして、よくわからないまま書き写したら動いた。お粗末な結末。せっかく末尾再帰というキーワードが出てきたのだから、答えの書いてありそうなページだからといって読むのをやめずにそこの説明だけはしっかり読むべきだった。

(define (my-reverse l)
  (my-reverse-rec l '()))
(define (my-reverse-rec ll lr)
  (cond
   ((null? ll) lr)
   (else
    (my-reverse-rec
     (cdr ll)
     (cons
      (car ll)
      lr)))))
(myreverse '(a b c d))
;; (d c b a)

(else (my-reverse-rec ...)) という風に、 cons とかせずにいきなり my-reverse-rec再帰呼び出しするのがキモってことなんだろう。この問題だけでたっぷり二時間は考えたはずだけど、この形はついぞ思い浮かばず。

あーもう、 (null? ll) が #t になるとき、つまり再帰が終わるときの lr の値は何なんだ?と考え出したらもう頭がこんがらがってしまった。もう一度順番に置き換えをやっていかないと理解できない。

;; (1)
(my-reverse-rec '(a b c d) '())
(else
 (my-reverse-rec ; => (2)
  '(b c d) ; (cdr '(a b c d))
  '(a))) ; (cons 'a '())

;; (2)
(my-reverse-rec '(b c d) '(a))
(else
 (my-reverse-rec ; => (3)
  '(c d) ; (cdr '(b c d)
  '(b a) ; (cons 'b '(a))

;; (3)
(my-reverse-rec '(c d) '(b a))
(else
 (my-reverse-rec ; => (4)
  '(d) ; (cdr '(c d))
  '(c b a) ; (cons 'c '(b a))

;; (4)
(my-reverse-rec '(d) '(c b a))
(else
 (my-reverse-rec ; => (5)
  '() ; (cdr '(d))
  '(d c b a) ; => (cons 'd '(c b a))

;; (5)
(my-reverse-rec '() '(d c b a))
(null? '()) ; => #t
;; => '(d c b a)

なるほど、大事なのは lr にあたる部分だったのか。ここに要素が逆順になったリストがたまっていくと。これは難しいなぁ。毎度分解していかないと、とてもじゃないがソラで思い浮かべられる気がしない。

あと、 (fold cons '() '(a b c d)) でオシマイ、とか書いてあるページも見つけたけど、これ以上複雑なことを頭に入れる余裕はないので見なかったことにしておく。どうせすぐ忘れてしまうのだし。

g000001g0000012010/01/11 01:07再帰の部分は完成してますね!
リストとリストを()を増やさないように合体させるには、appendが使えます('-'*)

a666666a6666662010/01/11 19:36アドバイスありがとうございます。
なるほど、 append を使えばいいのかぁ。どの組み込み関数を使っていいかを考えるのがちょっと悩ましいです。。

g000001g0000012010/01/11 20:03ちなみに、下請けの関数を定義する方法で、appendを使わない(定義しない)でも解ける方法が1つあります!

a666666a6666662010/01/12 01:17http://www.shido.info/lisp/scheme7.html にも似た問題があって、ちょうどその問題の直前で末尾再帰の解説があり下請けの関数を定義してたので、「myreverse とは別に、引数を二つとる別の関数を使うのかなぁ」と予想はできたのですが、いざ実装してみようとするとさっぱり手が動きませんでした。どうも、僕の頭は自分で思っていたよりずっとリスト操作が苦手なようです。

g000001g0000012010/01/12 03:12またまた再帰の部分は完成してますね!
consされるところを変えれば完成ではないでしょうか!
(myreverse '(1 2 3 4) ())
-> (myreverse '(2 3 4) (cons 1 '()))
-> (myreverse '(3 4) (cons 2 '(1)))
-> (myreverse '(4) (cons 3 '(2 1)))
-> (myreverse '() (cons 4 '(3 2 1)))
なんというか、左を減らして、右を増やす、みたいな…