相互再帰関数の固定小数点結合子？

Question

相互再帰関数のタプルを作成するための固定小数点コンビネータはありますか？私。私はY-Combinatorのようなものを探していますが、複数の "再帰的な" *関数を取り、関数の組を返すでしょうか？

*：通常のY-Combinatorのやり方で、引数として自分自身（および兄弟）を取り込むように書かれているので、もちろん再帰的ではありません。

Answer 1

あなたが探している生物はY *コンビネータです。 this page by oleg-at-okmij.orgに基づか

私はClojureのにY *を移植：

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

することができます十分に大きな引数を使用すると、この関数でスタックを簡単に吹き飛ばすことができます。したがって、完全にスタックを消費しない完全性などのトランポリンバージョンです。

Lambder

- ）

;

(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にすぐにブログよそのモナドパーサの相互再帰的な定義を定義するために非常に有用です

Answer 2

私はこれについて完全にはわかりません。私はまだそれの正式な証拠を見つけることを試みている。しかし、それはあなたには必要ないと思われます。 Haskellでは は、あなたのようなものがある場合：

修正::（ - > A） - >
修正Fを=メイン

Xで、X = FXをしましょう= {Xの=を聞かせて。 .. y ...; Y = ... X ...}

X

であなたはFST $ $ \（x、y）を修正=

メインにメイン書き換えることができます - >（... yは... 、... x ...）

私が言ったように、私はこのことについて100％確信していません。

Answer 3

次のWebページでは、相互再帰（多変数固定点コンビネータ）の固定点コンビネータについて詳しく説明します。それは今までのところ最も単純なコンビネータである を導き出します。 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)))) 

でください。例や詳細についてはWebページを参照してください。