recursion - 相互再帰関数の不動点コンビネータ？

Question

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

*：もちろん、通常のY-Combinatorの方法で、自分自身（および兄弟）を引数として取るように記述されているため、実際には再帰的ではありません。

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*コンビネータは、モナド パーサーの相互再帰的な定義を定義するのに非常に便利です。

-- ラムダー

Answer 2

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

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

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

main に書き換えることができます

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

しかし、私が言ったように、私はこれについて 100% 確信があるわけではありません。