用於相互遞歸函數的定點組合器？

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

請請參閱網頁中的示例和更多討論。