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

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

如果你使用足够大的参数,你可以很容易地用这个函数吹掉堆栈,所以这里是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*组合子是定义单子解析器,其中我会尽快博客上lambder.com,敬请关注相互递归定义非常有用)

- 兰德

Answer 2

以下网页详细描述了用于相互递归的固定点组合器(多变量固定点组合器).它派生出迄今为止最简单的组合子. 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))))

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