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

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

Выс помощью этих функций можно легко взорвать стек, если вы используете достаточно большие аргументы, поэтому вот его трамплинная версия, например, полнота, которая вообще не использует стек:

(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, следите за обновлениями;)

- Lambder

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

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

Answer 3

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

fix :: (a -> a) -> a
fix f = let x = fx в x

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

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

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

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