Комбинатор с фиксированной точкой для взаимно-рекурсивных функций?

Ответ 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 * очень полезен для определения взаимно-рекурсивных определений монадических парсеров, из которых я буду вести блог на lambder.com, следите за обновлениями;)

- Ламбер

Ответ 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)

и здесь он находится в Scheme, строгом языке

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

Пожалуйста, просмотрите веб-страницу для примеров и более подробных обсуждений.

Ответ 3

Я не совсем уверен в этом. Я все еще пытаюсь найти официальное доказательство этого. Но мне кажется, что он вам не нужен. В Haskell, если у вас есть что-то вроде:

fix:: (a → a) → a
fix f = пусть x = f x в x

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

вы можете переписать main на

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

Но, как я уже сказал, я не уверен на 100% об этом.