符合Stone提出的Scheme递归谓词设计模式的经典示例有哪些？

符合该check设计模式的经典谓词 #

这个模式的核心是单路径线性递归验证：每次仅对输入做一次固定变换、走唯一的递归分支，不需要多路径递归（比如树结构遍历的多分支递归就不满足），符合这个特性的经典谓词都可以用该模式实现，以下是常见的例子：

• 判断正整数是否为k的幂（和示例的2的幂逻辑一致，可扩展到任意正整数k）
  示例为判断3的幂：

  (define power-of-three? 
    (check 
      (sect = <> 1)                   ; 停止条件：降到1则是3的幂
      (sect zero? (modulo <> 3))      ; 继续条件：当前值能被3整除
      (sect / <> 3)))                 ; 变换步骤：除以3
  

• 判断字符串是否为回文

  (define palindrome?
    (check
      (lambda (s) (<= (string-length s) 1))  ; 停止条件：长度<=1则是回文
      (lambda (s)                             ; 继续条件：首尾字符相等
        (char=? (string-ref s 0) 
                (string-ref s (- (string-length s) 1))))
      (lambda (s)                             ; 变换步骤：去掉首尾字符
        (substring s 1 (- (string-length s) 1)))))
  

• 判断两个正整数是否互质（基于欧几里得算法实现）

  (define coprime?
    (check
      (lambda (a b)                           ; 停止条件：其中一个为0时，另一个等于1则互质
        (cond [(zero? a) (= b 1)]
              [(zero? b) (= a 1)]
              [else #f]))
      (lambda (a b) (and (not (zero? a)) (not (zero? b)))) ; 继续条件：两个数都不为0
      (lambda (a b) (list b (modulo a b)))))  ; 变换步骤：替换为(b, a mod b)
  

  调用时传入两个正整数即可：(coprime? 12 7) ; 返回#t

• 判断正整数是否为丑数（丑数定义：质因子仅包含2、3、5的正整数）

  (define ugly?
    (check
      (sect = <> 1)                           ; 停止条件：降到1则为丑数
      (lambda (n)                             ; 继续条件：能被2/3/5任意一个整除
        (or (even? n) 
            (zero? (modulo n 3)) 
            (zero? (modulo n 5))))
      (lambda (n)                             ; 变换步骤：除以最小的可整除质因子
        (cond
          [(even? n) (/ n 2)]
          [(zero? (modulo n 3)) (/ n 3)]
          [else (/ n 5)])))
  

• 判断正整数是否为完全平方数（基于连续奇数相减法实现）

  (define perfect-square?
    (check
      (lambda (n k)                           ; 停止条件：减到0是平方数，小于0则不是
        (if (<= n 0) (zero? n) #f))
      (lambda (n k) (> n 0))                  ; 继续条件：当前值大于0
      (lambda (n k) (list (- n k) (+ k 2))))) ; 变换步骤：减去当前奇数，奇数加2
  

  调用时初始第二个参数传1即可：(perfect-square? 16 1) ; 返回#t

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