Hatena::Groupsicp

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

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明けましておめでとうございます!
リストの要素を操作するときは末尾よりも先頭のほうが扱いやすいので逆順にするイディオムがあるということが、よくわかりました!