对于相互递归函数的定点组合器?

Is there a fixed point combinator for creating tuples of mutually recursive functions? I.e. I'm looking for something like the Y-Combinator but which takes multiple "recursive"* functions, and will return a tuple of functions?

是否有一个固定点组合器来创建相互递归函数的元组?也就是说，我在寻找Y-Combinator之类的函数，它具有多个“递归”*函数，并返回一组函数?

*: not really recursive of course, as they are written to take themselves (and siblings) as arguments, in the usual Y-Combinator way.

*:当然不是递归的，因为它们是用来把自己(和兄弟姐妹)当作参数的，通常是Y-Combinator。

3 个解决方案

#1

The creature you are looking for is Y* combinator.

你要找的生物是Y* combinator。

Basing on this page by oleg-at-okmij.org I ported the Y* to Clojure:

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

The classic example of mutual recursive function is even/odd so here is the example:

互递归函数的经典例子是偶数/奇数，这里有一个例子:

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

You can easily blow the stack with this functions if you use big enough arguments, so here is trampolined version of it for example completeness which do not consume stack at all:

如果你使用足够大的参数，你可以很容易地使用这个函数来破坏堆栈，所以这里是它的蹦床版本，例如完整性，它根本不消耗堆栈:

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

The Y* combinator is very useful for defining mutual recursive definitions of monadic parsers, of which I'll blog soon on lambder.com , stay tuned ;)

Y* combinator对于定义monadic分析器的相互递归定义非常有用，我将很快在lambder.com上发表这篇文章，敬请关注。

-- Lambder

——Lambder

#2

The following web page describes the fix-point combinators for mutual recursion (polyvariadic fixpoint combinators) in detail. It derives the simplest so far combinator. http://okmij.org/ftp/Computation/fixed-point-combinators.html#Poly-variadic

下面的web页面详细描述了用于相互递归的fix点组合器(polyvariadic fixpoint组合器)。它得到了迄今为止最简单的组合器。http://okmij.org/ftp/Computation/fixed-point-combinators.html Poly-variadic

For ease of reference, here is the simplest polyvariadic combinator in Haskell (one-liner)

为了便于参考，这里是Haskell中最简单的多元组合器(单线性)

fix_poly:: [[a]->a] -> [a]
fix_poly fl = fix (\self -> map ($ self) fl)
  where fix f = f (fix f)

and here it is in Scheme, a strict language

这里是Scheme，一种严格的语言

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

Please see the web page for examples and more discussion.

有关示例和更多讨论，请参见web页面。

#3

I'm not entirely sure about this one. I'm still trying to find a formal proof of it. But it seems to me you don't need one. In Haskell, if you have something like:

我不太确定。我还在试图找到一个正式的证据。但在我看来，你不需要。在Haskell中，如果你有:

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

fix::(a -> a) -> a fix f =设x = f x in x

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

main =让{x =…y…;y =…x……在x }

you can rewrite main to

你可以重写main到。

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

主= fst $ fix $ (x, y) ->(…)y……,……x…)

But like I said, I'm not 100% sure about this one.

但是就像我说的，我不是百分之百的确定。

#1