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