recursion - 相互递归函数的定点组合器？

Question

是否有用于创建相互递归函数的元组的定点组合器？ IE。我正在寻找类似 Y-Combinator 的东西，但它需要多个“递归”* 函数，并且会返回一个函数元组？

*:当然不是真正的递归，因为它们是以通常的 Y-Combinator 方式将自己(和 sibling )作为参数编写的。

Answer 1

您正在寻找的生物是 Y* 组合器。

基于this page by oleg-at-okmij.org我将 Y* 移植到 Clojure:

(defn Y* [& fs]
  (map (fn [f] (f))
    ((fn [x] (x x))
      (fn [p]
        (map
          (fn [f]
            (fn []
              (apply f
                (map
                  (fn [ff]
                    (fn [& y] (apply (ff) y)))
                  (p p)))))
          fs)))))

相互递归函数的经典例子是偶数/奇数，所以这里是例子:

(let
  [[even? odd?]
   (Y*
     (fn [e o]
       (fn [n]
         (or (= 0 n) (o (dec n)))))
     (fn [e o]
       (fn [n]
         (and (not= 0 n) (e (dec n)))))
     )
   ]
  (do
    (assert (even? 14))
    (assert (odd? 333))
    ))

如果你使用足够大的参数，你可以很容易地用这个函数炸毁堆栈，所以这里是它的蹦床版本，例如完全不消耗堆栈的完整性:

(let
  [[even? odd?]
   (Y*
     (fn [e o]
       (fn [n]
         (or (= 0 n) #(o (dec n)))))
     (fn [e o]
       (fn [n]
         (and (not= 0 n) #(e (dec n)))))
     )
   ]
  (do
    (assert (trampoline even? 144444))
    (assert (trampoline odd? 333333))
    ))

Y* 组合器对于定义 monadic 解析器的相互递归定义非常有用，我很快就会在 lamder.com 上写博客，敬请关注 ;)

——
兰德