Stały kombinator punktowy do wzajemnie rekursywnych funkcji?

Question

Czy istnieje kombinator punktowy do tworzenia krotek funkcji rekurencyjnych? To znaczy. Szukam czegoś takiego jak Y-Combinator, ale który ma wiele funkcji "rekursywnych" * i zwróci krotkę funkcji?

*: Oczywiście nie rekursywne, ponieważ są napisane, aby brać siebie (i rodzeństwo) jako argumenty, w zwykły sposób Y-Combinator.

Answer 1

Istota, której szukasz, to kombinator Y *.

Bazując na this page by oleg-at-okmij.org I przeniesiony do y * do 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))))) 

Klasycznym przykładem wzajemnego funkcji rekurencyjnej jest parzysta/nieparzysta tak oto przykład:

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

Można możesz łatwo wysadzić stos za pomocą tych funkcji, jeśli użyjesz wystarczająco dużych argumentów, więc tutaj jest to trampolowana wersja, na przykład kompletność, która w ogóle nie zużywa stosu:

(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 * syntezatora jest bardzo przydatna do określania wzajemnych rekurencyjne definicje monadycznych parserami, z których będę blog wkrótce na lambder.com, zaglądajcie;)

- Lambder

Answer 2

Nie jestem do końca pewien na ten temat. Nadal próbuję znaleźć formalny dowód na to. Ale wydaje mi się, że go nie potrzebujesz. W Haskell, jeśli masz coś takiego:

fix :: (a -> a) -> a
fix f = Niech X = fx w x

główny = Niech {x =. .. y ...; y = ... x ...} wx

można przepisać głównym do

główny = FST $ naprawić $ \ (X, Y) -> (... y .. ., ... x ...)

Ale jak powiedziałem, nie jestem w 100% pewien tego.

Answer 3

Poniższa strona opisuje szczegółowo kombinatory punktowe do wzajemnej rekursji (kombinatory poliwariotycznych punktów stałych). Jest to najprostszy do tej pory kombinator . http://okmij.org/ftp/Computation/fixed-point-combinators.html#Poly-variadic

Dla ułatwienia, tutaj jest najprostszym polyvariadic syntezatora w Haskell (one-liner)

fix_poly:: [[a]->a] -> [a] 
fix_poly fl = fix (\self -> map ($ self) fl) 
    where fix f = f (fix f) 

a tutaj jest na schemacie, w ścisłym języku

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

proszę zobacz stronę internetową dla przykładów i więcej dyskusji.