互递归函数的不动点组合子？

Question

是否存在一种固定点组合子，可以创建相互递归函数的元组？也就是说，我正在寻找类似于Y组合子的东西，但它可以接受多个“递归”函数，并返回函数的元组。

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

- pauldoo

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*组合器非常有用，可以定义单子解析器的相互递归定义。我很快会在lambder.com上发布博客，敬请关注；）

- Lambder

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编写的，Scheme是一种严格的语言

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

请查看网页以获取示例和更多讨论。

- Oleg

Answer 3

我对这个问题并不完全确定。我仍在努力寻找它的正式证明。但是在我看来，你不需要一个。

在Haskell中，如果你有像这样的东西：

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

main = let { x = ... y ...; y = ... x ... } in x

你可以将main重写为

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

但就像我说的，我对这个问题并不100%确定。

- Pete

---

Haskell 不等于 λ演算。 - eschulte