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

Question

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

*：当然不是真正的递归，因为它们被编写为以通常的 Y-Combinator 方式将自己（和兄弟姐妹）作为参数。

Answer 1

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

基于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 解析器的相互递归定义非常有用，我很快就会在 lambder.com 上写博客，敬请期待；）

-- 兰伯德

Answer 2

以下网页详细描述了相互递归的定点组合器（多变量定点组合器）。它派生了迄今为止最简单的组合子。 http://okmij.org/ftp/Computation/fixed-point-combinators.html#Poly-variadic

为了便于参考，这里是 Haskell 中最简单的多变量组合器（单线）

fix_poly:: [[a]->a] -> [a]
fix_poly fl = fix (\self -> map ($ self) fl)
  where fix f = f (fix f)

这里是 Scheme，一种严格的语言

 (define (Y* . l)
   ((lambda (u) (u u))
    (lambda (p)
       (map (lambda (li) (lambda x (apply (apply li (p p)) x))) l))))

请参阅网页以获取示例和更多讨论。

Answer 3

我不完全确定这一点。我仍在努力寻找它的正式证明。但在我看来，你不需要一个。在 Haskell 中，如果你有类似的东西：

fix :: (a -> a) -> a
fix f = let x = fx in x

主要 = 让 { x = ... y ...; y = ... x ... } 在 x

您可以将 main 重写为

main = fst $ fix $ \(x, y) -> (... y ..., ... x ...)

但就像我说的，我不是 100% 确定这个。