Scheme中如何从通用代码重构出特化行为？

我经常遇到这种情况：手里有一个实用函数，但需要一个行为略有不同的版本。比如先写了一个能找出子串在长文本中所有出现位置的搜索函数，之后又需要找第一个、最后一个或第n个匹配项的场景。

有没有惯用方法能从大量通用代码里提取出这些不同的特化行为？

举个例子，下面两个子串搜索函数：一个返回第一个匹配项的索引，无匹配则返回#f；另一个返回所有匹配位置的列表，无匹配则返回'()。（忽略这是低效实现）

;; Return the index of the first matching instance of `pattern` in
;; `s`. Returns #f if there is no match.
(define (naive-string-find-first pattern s)
  (let* ((p-len (string-length pattern))
         (limit (- (string-length s) p-len)))
    (let outer ((i 0))
      (if (<= i limit)
          (let inner ((j i)
                      (k 0))
            (if (< k p-len)
                (if (char=? (string-ref s j) (string-ref pattern k))
                    (inner (+ j 1) (+ k 1))
                    (outer (+ i 1)))
                i))
          #f))))

;; Return a list of all positions in `s` where `pattern` occurs.
;; Returns '() if there is no match.
(define (naive-string-find-all pattern s)
  (let* ((p-len (string-length pattern))
         (limit (- (string-length s) p-len)))
    (let outer ((i 0))
      (if (<= i limit)
          (let inner ((j i)
                      (k 0))
            (if (< k p-len)
                (if (char=? (string-ref s j) (string-ref pattern k))
                    (inner (+ j 1) (+ k 1))
                    (outer (+ i 1)))
                (cons i (outer (+ i 1)))))
          '()))))

可以看到，它们几乎完全相同，只有最后几行有差异：一处处理匹配后的逻辑，另一处处理遍历结束后的逻辑。

我尝试写了通用函数naive-string-find-common，传入匹配和失败处理函数，但实现find-all功能时，lambda无法访问named let定义的outer，导致代码失效：

(define (naive-string-find-common pattern s match-func fail-func)
  (let* ((p-len (string-length pattern))
         (limit (- (string-length s) p-len)))
    (let outer ((i 0))
      (if (<= i limit)
          (let inner ((j i)
                      (k 0))
            (if (< k p-len)
                (if (char=? (string-ref s j) (string-ref pattern k))
                    (inner (+ j 1) (+ k 1))
                    (outer (+ i 1)))
                (match-func i)))
          (fail-func i)))))

(define (naive-string-find-first-common pattern s)
  (let ((match-f (lambda (x) x))
        (fail-f (lambda (x) #f)))
    (naive-string-find-common pattern s match-f fail-f)))

(define (naive-string-find-all-common pattern s)
  (let ((match-f (lambda (x) (cons x (outer (+ x 1))))) ;; <-- 这里报错，因为outer不可访问
        (fail-f (lambda (x) #f)))
    (naive-string-find-common pattern s match-f fail-f)))

请问这种场景下，有没有惯用的方法提取所需功能？

针对这种需要复用核心逻辑、仅调整结果收集/终止行为的场景，有几种惯用的Lisp风格解决方案：

1. 把继续搜索的函数传给回调 #

核心思路是让match-func不仅接收匹配到的索引，还接收一个能继续从下一个位置搜索的函数。这样在需要收集所有结果时，就可以调用这个函数来递归获取后续匹配。

重构后的通用函数：

(define (naive-string-find-common pattern s match-func fail-func)
  (let* ((p-len (string-length pattern))
         (limit (- (string-length s) p-len)))
    (let outer ((i 0))
      (if (<= i limit)
          (let inner ((j i)
                      (k 0))
            (if (< k p-len)
                (if (char=? (string-ref s j) (string-ref pattern k))
                    (inner (+ j 1) (+ k 1))
                    (outer (+ i 1)))
                ;; 把继续搜索的函数传给match-func
                (match-func i (lambda () (outer (+ i 1))))))
          (fail-func)))))

实现两个特化函数：

;; 找第一个匹配：匹配到就直接返回索引，不继续搜索
(define (naive-string-find-first pattern s)
  (naive-string-find-common
   pattern s
   (lambda (idx continue) idx)  ;; 匹配到就返回索引，忽略continue
   (lambda () #f)))             ;; 遍历结束返回#f

;; 找所有匹配：收集当前索引，再递归获取后续结果
(define (naive-string-find-all pattern s)
  (naive-string-find-common
   pattern s
   (lambda (idx continue) (cons idx (continue)))  ;; 收集当前索引并继续搜索
   (lambda () '())))                              ;; 遍历结束返回空列表

这种方式让回调拥有了控制搜索流程的能力，既可以终止（比如找第一个），也可以继续（比如找所有）。

2. 使用累加器模式 #

如果需要更复杂的结果收集（比如找第n个、最后一个），可以让通用函数接收一个累加器和更新累加器的回调，把状态传递下去：

(define (naive-string-find-accum pattern s init-acc update-acc finalize-acc)
  (let* ((p-len (string-length pattern))
         (limit (- (string-length s) p-len)))
    (let outer ((i 0)
                (acc init-acc))
      (if (<= i limit)
          (let inner ((j i)
                      (k 0))
            (if (< k p-len)
                (if (char=? (string-ref s j) (string-ref pattern k))
                    (inner (+ j 1) (+ k 1))
                    (outer (+ i 1) acc))
                ;; 匹配到，更新累加器，然后决定是否继续
                (let ((new-acc (update-acc acc i)))
                  (if (finalize-acc new-acc)  ;; 判断是否需要终止搜索
                      new-acc
                      (outer (+ i 1) new-acc)))))
          acc))))

实现各种特化：

;; 找第一个匹配：累加器存第一个索引，匹配到就终止
(define (naive-string-find-first pattern s)
  (naive-string-find-accum
   pattern s
   #f  ;; 初始累加器：未找到
   (lambda (acc idx) idx)  ;; 匹配到就更新为当前索引
   (lambda (acc) acc)))    ;; 只要累加器不是#f就终止

;; 找所有匹配：累加器存列表，一直收集到结束
(define (naive-string-find-all pattern s)
  (naive-string-find-accum
   pattern s
   '()  ;; 初始累加器：空列表
   (lambda (acc idx) (cons idx acc))  ;; 把索引加到列表头部
   (lambda (acc) #f)))                ;; 永远不提前终止，最后反转列表得到顺序结果

这种模式适合需要维护状态的场景，比如计数匹配次数、收集前n个匹配等。

3. 使用生成器/惰性序列 #

如果希望一次实现核心逻辑，然后按需提取不同结果，可以返回一个惰性序列（Scheme里的delay/force），然后基于这个序列实现各种特化：

(define (naive-string-find-generator pattern s)
  (let* ((p-len (string-length pattern))
         (limit (- (string-length s) p-len)))
    (letrec ((next (lambda (i)
                     (if (<= i limit)
                         (let inner ((j i)
                                     (k 0))
                           (if (< k p-len)
                               (if (char=? (string-ref s j) (string-ref pattern k))
                                   (inner (+ j 1) (+ k 1))
                                   (next (+ i 1)))
                               (cons i (delay (next (+ i 1))))))
                         '()))))
      (delay (next 0)))))

;; 找第一个匹配
(define (naive-string-find-first pattern s)
  (let ((gen (naive-string-find-generator pattern s)))
    (if (null? (force gen))
        #f
        (car (force gen)))))

;; 找所有匹配：展开惰性序列
(define (naive-string-find-all pattern s)
  (let loop ((gen (naive-string-find-generator pattern s))
             (acc '()))
    (let ((val (force gen)))
      (if (null? val)
          (reverse acc)
          (loop (cdr val) (cons (car val) acc))))))

这种方式把核心搜索逻辑封装成生成器，后续的特化逻辑只需要处理序列的提取，非常灵活。

内容的提问来源于stack exchange，提问作者clartaq