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

Question

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

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

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)) 
    )) 

你可以如果你使用足够大的参数，使用这个函数很容易吹到堆栈，所以这里是它的trampolined版本，例如完全不消耗堆栈的完整性：

(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

我不完全确定这个。我仍然试图找到一个正式的证明。但在我看来，你并不需要一个。 在Haskell，如果你有这样的：

修复::（A - > A） - 在X>一个
修复F =令x = FX

主要=设{X =。 ... y ...; Y = ... X ...}在X

你可以重写主到

主要= $ FST修复$ \（X，Y） - >（... Y .. ...，... x ...）

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

Answer 3

以下网页详细介绍了用于相互递归的定点组合器（多变量定点组合器）。它得到迄今为止最简单的 组合子。 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) 

这里最简单的polyvariadic组合子是方案，严格的语言

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

请请参阅网页中的示例和更多讨论。