定点组合器是否具有相互递归的功能? [英] Fixed point combinator for mutually recursive functions?

问题描述

是否存在用于创建相互递归函数元组的定点组合器? IE.我正在寻找类似Y-Combinator的东西，但是它需要多个递归" *函数，并且将返回一个函数元组?

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 * 组合器.

The creature you are looking for is Y* combinator.

基于此页面由 oleg-at-okmij.org 我将 Y * 移植到Clojure:

Basing on this page by oleg-at-okmij.org I ported the Y* to 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))
    ))

Y * 组合器对于定义monadic解析器的相互递归定义非常有用，我将很快在lambder.com上发布其博客，敬请期待；)

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

- 羔羊

这篇关于定点组合器是否具有相互递归的功能?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！