filterとmap

http://practical-scheme.net/wiliki/wiliki.cgi?cut-seaで見かけたもの。

(define (analysis quest hint)
  (define (analy p0 q seq)
    (let1 cs (search p0 q)
      (cond ((<= 0 (length q) 1) (sequence-write (reverse seq)))
            ((or (null? cs) (>= (length seq) hint)) #f)
            (else
             (filter (lambda (p1)
                       (let1 new-q (banish p0 p1 q)
                         (filter (lambda (p2)
                                   (analy p2 new-q (cons (cons p0 p1) seq)))
                                 new-q)))
                     cs)))))
  (filter (lambda (p)
            (analy p quest '()))
          quest))

が

(define (analysis quest hint)
  (define (analy p0 q seq)
    (let1 cs (search p0 q)
      (cond ((<= 0 (length q) 1) (sequence-write (reverse seq)))
            ((or (null? cs) (>= (length seq) hint)) '())
            (else
             (map (lambda (p1)
                    (let1 new-q (banish p0 p1 q)
                      (append-map (lambda (p2)
                                    (analy p2 new-q (cons (cons p0 p1) seq)))
                                  new-q)))
                  cs)))))
  (append-map (lambda (p)
                (analy p quest '()))
              quest))

と変更されたという。
これは、なんだか面白そうな変更なので、ちょっと考えてみる。
変更された点は２つ。

1. analy関数内の#fが'()に変わっている
2. filterがappend-mapとmapに変わっている

これが何を意味するのか？

• • • -

プログラムの全体像を見ていないので、文脈は分からないし、Schemeもあまり得意ではないので文法的にも分からないところを含んでいるのでここで考えていることは外れているかもしれませんが・・・

• • • -

ある探索をした結果をどう返すかという問題。
問題が[a,b,c]という３つの入力であって、それぞれ、探索の結果は

• a -> 成功。結果は a1 と a2
• b -> 失敗。
• c -> 成功。結果は c1 のみ

となったとき、失敗を False で表すと、

map f [a,b,c] -> [True, False, True]
filter f [a,b,c] -> [a,c]

となる。それに対し、失敗を [] で表すと、

map f [a,b,c] -> [[a1,a2],[],[c1]]
append_map f [a,b,c] -> [a1,a2,c1]

となる。そういう違いではないか？