Hatena::Groupsicp

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

2010-01-16

P06 (*) Find out whether a list is a palindrome.

| 02:17 | P06 (*) Find out whether a list is a palindrome.  - a666666の日記 を含むブックマーク はてなブックマーク - P06 (*) Find out whether a list is a palindrome.  - a666666の日記 P06 (*) Find out whether a list is a palindrome.  - a666666の日記 のブックマークコメント

A palindrome can be read forward or backward; e.g. (x a m a x).

palindrome は、回文。前後どちらから読んでも同じ語句文、だそうで。

で、問題は、リストが回文になってるかどうか、を判定しろというものか。

元のリストを逆順にしたリストを作って、二つのリストの要素を順番に比べていって、全部同じだったら回文だといえそうだ。

元のリストを逆順にしたリストを作るのには、前回やった my-reverse が使えるかな。 reverse 使ってもいいのだろうけど、復習のためにもう一度書いてみよう。

(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)))))

(my-reverse '(a b c d))
;; => (d c b a)

ここからが今回の問題用に書いたぶん。

(define (is-palindrome l)
  (is-palindrome-rec l (my-reverse l)))
(define (is-palindrome-rec l lr)
  (cond ((and (null? l) (null? lr)) #t)
        ((not (eq? (car l) (car lr))) #f)
        (else (is-palindrome-rec (cdr l) (cdr lr)))))

(is-palindrome '(x a m a x))
;; => #t
(is-palindrome '(x a m a))
;; => #f
(is-palindrome '())
;; => #t

うまくいったようだ。 ( (and (null? l) (null? lr)) #t) がないと再帰でリストを食べ尽くしたときにエラーになる。

l か lr のどちらかが空リストの場合(二つのリストの要素数が違う場合)はやはりエラーになると思うけど、二つ目のリストは一つ目のリストを逆順にしたものなので要素数は必ず同じになる。だから大丈夫。

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)))
なんというか、左を減らして、右を増やす、みたいな…

2010-01-05

P03 (*) Find the K'th element of a list.

| 02:40 | P03 (*) Find the K'th element of a list. - a666666の日記 を含むブックマーク はてなブックマーク - P03 (*) Find the K'th element of a list. - a666666の日記 P03 (*) Find the K'th element of a list. - a666666の日記 のブックマークコメント

明けましておめでとうございます。今年の目標は L-99 を完走して Perl Cookbook チャレンジも完走して The Little Schemer を全部読み終えたいです。 SICP にはまだまだ届く気がしない。

    The first element in the list is number 1.
    Example:
    * (element-at '(a b c d e) 3)
    C
(define (element-at l n)
  (cond
   ((= n 1) (car l))
   (else (element-at (cdr l) (- n 1)))))

(element-at '(a b c d e) 3)
;; => c
(element-at '(a b c d e) 1)
;; => a
(element-at '(a b c d e) 5)
;; => e

再帰を使って。こんなんでいいのかな。ちょっと例が意地悪だな。最初 (element-at '(a b c d e) 1) が e になるコードを書いてしまって、解答をみたら妙ちきりんで複雑なことをやってるように見えて引数を変えて実行してみて間違いに気づいた。最初から n が 3 以外になってる例だったらすぐ気づいたのになぁ。結局、解答を見てから改めて書き直したので、見ながら書いたわけじゃないとはいえ自力で解いたとは言い難い。

Emacsプログラム部分を書いてからコピペしてるのでローカルのファイルとここの内容が同期してないのがちょっとやなかんじ。 Emacs から直接投稿できるやつを使うようにすべきか。

2009-12-29

P02 (*) Find the last but one box of a list.

| 03:14 | P02 (*) Find the last but one box of a list.  - a666666の日記 を含むブックマーク はてなブックマーク - P02 (*) Find the last but one box of a list.  - a666666の日記 P02 (*) Find the last but one box of a list.  - a666666の日記 のブックマークコメント

    Example:
    * (my-but-last '(a b c d))
    (C D)
(define (my-but-last l)
  (cond ((null? (cdr (cdr l))) l)
        (else (my-but-last (cdr l)))))

(my-but-last '(a b c d))
;; => (c d)

(use gauche.test)
(test* "L-99 P02" '(c d) (my-but-last '(a b c d)))

これも手抜き?で要素が二つ以下のリストを渡すと動かない。それはそれとして解答をみると reverse して逆順のリストを作っているみたいなんだけど意味がわからない。どうして逆にする必要があるんだ?

追記

http://sicp.g.hatena.ne.jp/a666666/20091229#c1262190684 ということで、リストを最初に逆順にして操作するというのは Lisp におけるイディオムなんだそうだ。コメントを踏まえて解答コードを読み直し、 Gauche に翻訳してみると(ほぼ同じだけど)、少し意味がわかった。 first, second は Gaucheリファレンスマニュアルには書いてなかったが car, cadr で代用できたのでそこを変更してみた。

(define (penultimo lista)
  (let ((reverso (reverse lista)))
    (cond
     ((null? reverso) '())
     ((<= (length reverso) 2) lista)
     (else (list (cadr reverso) (car reverso)))
     )
    )
  )

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

「リストの要素のうち後ろの二つを取り出す」ことを考えたとき、愚直に再帰でリストを先頭からたどっていくよりも、最初に逆順にしてしまえば「逆順にしたリストの先頭と二番目の要素」が求めるものなので、取り出しやすいということか。なるほど、確かにパズルだ。

g000001g0000012009/12/31 01:31lispのリストは片方向の連結リストなので、先頭に追加するのはコストが低いのですが、その都度末尾に追加するのはコストが高いので、先頭に追加していって最後にドバっと逆転させる(もしくは先に逆転させる)というのがイディオムになってます。最初は自分も不思議でした('-'*)

a666666a6666662010/01/04 02:45明けましておめでとうございます!
リストの要素を操作するときは末尾よりも先頭のほうが扱いやすいので逆順にするイディオムがあるということが、よくわかりました!

2009-12-26

L-99 はじめました

| 00:45 | L-99 はじめました - a666666の日記 を含むブックマーク はてなブックマーク - L-99 はじめました - a666666の日記 L-99 はじめました - a666666の日記 のブックマークコメント

g000001 さんにすすめられて、 L-99 を Scheme (Gauche) ではじめてみます。一日一問、パズルを楽しむ感じで。

L-99: Ninety-Nine Lisp Problems

P01 (*) Find the last box of a list.

| 00:45 | P01 (*) Find the last box of a list. - a666666の日記 を含むブックマーク はてなブックマーク - P01 (*) Find the last box of a list. - a666666の日記 P01 (*) Find the last box of a list. - a666666の日記 のブックマークコメント

問題

    Example:
    * (my-last '(a b c d))
    (D)

解答

(define (my-last l)
  (cond ((null? (cdr l)) l)
        (else (my-last (cdr l)))))

(my-last '(a b c d))
;; => (d)

(use gauche.test)
(test* "L-99 P01" '(d) (my-last '(a b c d)))
;; test L-99 P01, expects (d) ==> ok

さいしょ、

((null? (cdr l)) (car l)

って書いてしまって d だけかえってきて、なんか違うような?って思った。 (d) と d の差がいまいちピンとこない。あ、あとこれ空リスト渡すとうごかないな。


g000001 さんにコメントをもらって、 srfi-1 に last (last-pair) なんてのがあることを知ったのでソースを読んでみようと思って /opt/local/share/gauche/0.8.13/lib/srfi-1.scm をひらいたら残念な感じだった。。

g000001g0000012009/12/27 01:03伝統的なLISPだとlastは最後のコンスを返すんですよね。何故なのかはわからないのですが… (use srfi-1)(last '(a b c d));=>dだったりしますね、Schemeだと。
あと、()のcdrはエラーになるというのも伝統的なLISPとSchemeの主な違いですね。

a666666a6666662009/12/30 03:13なるほどー > 伝統的な LISP
srfi-1 に last ありましたか!そして last-pair なんてのもありました。