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

Question

有没有一个用于创建相互递归函数的元组的定点组合器？也就是说，我正在寻找类似Y-Combinator的东西，但它接受多个“递归”*函数，并将返回一个函数元组？

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

Answer 1

下面的网页详细描述了用于相互递归的定点组合器(多变量固定点组合器)。它派生出目前为止最简单的组合子。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 2

我对这一点不是很确定。我还在努力寻找正式的证据。但在我看来你不需要。在Haskell中，如果你有这样的东西：

修复:：(a -> a) -> a

fix f= let x=f x in x

main = let {x= ...Y ...；y= ...X ... }在x中

您可以将main重写为

fix main = fst $

$ (x，y) -> (...你...，..。X ...)

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