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

Question

Есть ли комбинатор с фиксированной точкой для создания кортежей взаимно-рекурсивных функций? То есть Я ищу что-то вроде Y-Combinator, но которое принимает несколько «рекурсивных» * функций и вернет кортеж функций?

*: Не совсем рекурсивный, поскольку они написаны, чтобы взять себя (и братьев и сестер) в качестве аргументов в обычном порядке Y-Combinator.

Answer 1

Существо, которого вы ищете, является Y * Комбинатор.

Основываясь на this page by 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

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

затруднительного :: (а -> а) -> а
затруднительных е = Пусть х = Fx в й

основных = Пусть {х =. .. y ...; у = ... х ...} х

вы можете переписать основной для

главная = FST $ оставляющих $ \ (х, у) -> (... у .. ., ... x ...)

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

Answer 3

На следующей веб-странице подробно описаны комбинаторы фиксированной точки для взаимной рекурсии (многовариантные комбинаторы исправлений). Он получает самый простой до сих пор комбинатор . http://okmij.org/ftp/Computation/fixed-point-combinators.html#Poly-variadic

Для простоты ссылки здесь простейший polyvariadic комбинатор в 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)))) 

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