recursion - 递归谓词的例子

Question

在 Stone 的函数式编程算法中，他给出了递归定义谓词的设计模式，在 Scheme 中是

(define (check stop? continue? step)
  (rec (checker . arguments) 
    (or (apply stop? arguments) 
        (and (apply continue? arguments) 
             (apply (pipe step checker) arguments)))))

哪里pipe是作者按图解顺序组合两个函数的函数，((pipe f g) x = (g (f x))。

因此，例如，要测试一个函数是否是 2 的幂，您可以定义

(define power-of-two? (check (sect = <> 1) even? halve))

哪里(sect = <> 1)是作者的柯里化符号，相当于lambda x: x == 1.

很明显，很多谓词可以递归实现，但它没有用。显然有一些递归谓词不会使用这种模式，比如树上的谓词。

有哪些符合这种模式的经典谓词？我猜想测试康托集中是否有某些东西，但这与上面的几乎相同。

标签： recursiondesign-patternsfunctional-programmingscheme

Answer 1

目前尚不清楚您在问什么，但您的示例是使用组合器进行编程的经典示例。

组合器是作为输入函数和返回函数的函数。

组合器是函数式编程的基础。使用它们，您可以实现一切。例如，如果您将对象的数据结构定义为函数，您可以使用一些组合器组合对象并获得一个新对象。

您的示例中的组合器似乎对于检查有关某些单子组成的某些谓词很有用。