2529. そんな事やっちゃダメなんだっての。

亀田馬志 (Dec 02, 2009)
面白いブログ発見。

prograndum:
http://prograndum.blogspot.com/

ふ?ん、と思いながら斜め読み。

ここと別のブログの著者がいて、ちょっとしたやり取りを目にする。
お題は「プログラミングGauche」のp.56の話。

・リストの中から、条件を満たす要素だけを抜き出したリストを返すfilterを定義してみる。

その別のブログの著者がこーゆーコードをブログに挙げていたわけです。

(define (filter predicate ls) 
  (cond 
   ((null? ls) '()) 
   ((predicate (car ls))(cons (car ls)(filter predicate (cdr ls)))) 
   (else (filter predicate (cdr ls)))))

(filter even? '(1 2 3 4 5 6 7 8 9 10)) ;; => (2 4 6 8 10) 
(filter odd? '(1 2 3 4 5 6 7 8 9 10)) ;; => (1 3 5 7 9) 
(filter even? '()) ;; => ()

うん。これでいいと思います。及第点ですよね。
でも、prograndumの著者が疑問を呈するわけですよ。

＞このfilterだと入れ子のリストは処理できないですね
＞
＞たとえば
＞(1 2 (3 4) 5 (6 7))

まあ、確かにエラー返すわな。
ただし、「エラーを返す」のはこのfilterのせいじゃない、んです。そうじゃなくって、even?とかodd?が「整
数しか引数を取らない」からエラーを返すの。
さて、ここで問題。このfilterは第一引数の関数の「データ型指定」を無視して入れ子のリストを潜っていって
良いものでしょうか?

いやあ、それはやっちゃいけねえんじゃねえの?あまりに危険です。

そもそも、問題の本質は、無意識に「整数が並んでるリストを引数に取る前提だ」と考えている辺り。
例えば、

(filter odd? '(1 2 "three" 4 5 6 7 8 9 10))

だってエラー返すぜ。filterのせい?違うよね、odd?が整数しか引数に取れないのに、文字列喰っちゃったから
エラーがでる。
重要なのは、filterは、第一引数で取る述語が「想定したデータ型」以外に関して、余計な事したらダメなんだ
。それは非常に危険です、って事。
つまり、

(filter even? '(1 2 (3 4) 5 (6 7)))

はエラーを返すべき、なんです。何故なら「整数じゃない」データであるリストがあるんだもの。第一引数の述
語が「想定してない」型にあったら迷わず処理を中断すべきです。勝手に入れ子に潜って行っちゃいけない。それ
は「危険なプログラム」だ。

元々、filterってのはANSI Common Lispのremove-if-notなんですけど。

CL-USER> (remove-if-not #'evenp '(1 2 3 4 5 6 7 8 9 10))
(2 4 6 8 10)
CL-USER> (remove-if-not #'oddp '(1 2 3 4 5 6 7 8 9 10))
(1 3 5 7 9)
CL-USER> 

全く同じ動作です。SRFI-1のfilterなんかも、良く機能をコピーしています。
んで、同じケースで実験してみたら分かるんですが、remove-if-notも「堂々と」エラー返しますね。
何故なら。remove-if-notも「第一引数で与えられた述語が想定したデータ型」に従って処理を繰り返すから。
リストもデータ型である以上、勝手に入れ子に入って行っちゃダメ、なのです。
何故なら、それやっちゃうと、listp(schemeで言うlist?)とかatom(not pair?)とかの述語が使えなくなっちゃ
うし。
remove-if-notあるいはfilterはもっと汎用で、あらゆる述語を「取れるようにしておく」べきなんです。

この辺の話、受け手の著者も頑張ってコードを書いてたんで、面白かったんですけど、焦点がちょっとズレてる
な、とか少し感じました。入れ子に潜っていくようなfilterはマジで危険ですよ。「汎用的に」使えなくなっちゃ
いますからね。

ちなみに、僕だったらfilterこう書きますね(笑)。

(define (filter predicate ls)
  (let loop ((ls0 ls) (ls1 '()))
    (if (null? ls0)
        (reverse ls1)
        (let ((x (car ls0)) (y (cdr ls0)))
          (if (predicate x)
              (loop y (cons x ls1))
              (loop y ls1))))))

まあ、素直に書くと上のような感じですか。call/cc使うなら、

(define (filter predicate ls)
  (call/cc
   (lambda (break)
     (let loop ((ls0 ls) (ls1 '()))
       (loop (cdr (if (null? ls0)
                      (break (reverse ls1))
                      ls0))
             (let ((elm (car ls0)))
               (if (predicate elm)
                   (cons elm ls1)
                   ls1)))))))

こうか(笑)。
あるいは、

(define (filter predicate ls)
  (call/cc
   (lambda (1st-break)
     (let ((x (car (if (null? ls)
                       (1st-break '())
                       ls)))
           (y (cdr ls)))
       (let ((z (filter predicate y)))
         (call/cc
          (lambda (2nd-break)
            (cons (if (predicate x)
                      x
                      (2nd-break z)) z))))))))

こうとか(笑)。
さすがにやり過ぎか(笑)。
元ねた:
フォローアップ: