用于相互递归函数的定点组合器？

是否有一个固定点组合器用于创建相互递归函数的元组？即我正在寻找像Y-Combinator这样的东西，它需要多个“递归”*函数，并将返回一个函数元组？ *：当然不是真正的递归，因为它们是以通常的Y-Combinator方式将自己（和兄弟姐妹）作为参数编写的。

已邀请:

3 个回复

埃庐

你正在寻找的生物是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))
    ))

如果你使用足够大的参数，你可以很容易地用这个函数吹掉堆栈，所以这里是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 *组合器对于定义monadic解析器的相互递归定义非常有用，我将很快在lambder.com上发表博文，敬请关注;） - Lambder

队辅坟阮阶

以下网页详细描述了用于相互递归的固定点组合器（多变量固定点组合器）。到目前为止，它是最简单的组合子。 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)

在这里，它是一种严格的语言

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

请参阅网页以获取示例和更多讨论。

甲车劲

我不完全确定这个。我还在试图找到它的正式证据。但在我看来，你不需要一个。在Haskell中，如果你有类似的东西：修复::（a - > a） - > a 修复f = let x = f x in x main = let {x = ... y ...; x中的y = ... x ...} 你可以重写主要 main = fst $ fix $ （x，y） - >（... y ...，... x ...）但就像我说的那样，我对这一点并不是100％肯定。

要回复问题请先登录或注册

用于相互递归函数的定点组合器？

3 个回复

发起人

combinators

y_combinator

mutual_recursion

问题状态

用于相互递归函数的定点组合器？

与内容相关的链接

3 个回复

发起人

combinators

y_combinator

mutual_recursion

问题状态