Combinatore di punti fissi per funzioni reciprocamente ricorsive?

Question

Esiste un combinatore di punti fissi per la creazione di tuple di funzioni reciprocamente ricorsive? Cioè Sto cercando qualcosa come Y-Combinator ma che richiede più funzioni "ricorsive" * e restituirà una tupla di funzioni?

*: ovviamente non ricorsivo, in quanto sono scritti per prendere se stessi (e fratelli) come argomenti, nel solito modo Y-Combinator.

Answer 1

La creatura che stai cercando è combinatore Y *.

Sulla base this page by oleg-at-okmij.org ho portato il Y * a 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))))) 

Il classico esempio di funzione ricorsiva mutuo è pari/dispari: ecco l'esempio:

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

Puoi facilmente saltare lo stack con queste funzioni se si usano argomenti abbastanza grandi, quindi ecco la versione trampolino di esso per esempio la completezza che non consuma affatto:

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

Il Y * Combinator è molto utile per la definizione di definizioni ricorsive reciproci di parser monadici, di cui sarò sul blog presto su lambder.com, restate sintonizzati;)

- Lambder

Answer 2

Non sono completamente sicuro di questo. Sto ancora cercando di trovare una dimostrazione formale di ciò. Ma mi sembra che tu non ne abbia bisogno. In Haskell, se avete qualcosa di simile:

fix :: (a -> a) -> un
correzione f = Sia x = fx in x

principale = Sia {x =. .. y ...; y = ... x ...} in x

si può riscrivere principale per

principale = FST $ fissare $ \ (x, y) -> (... y .. ., ... x ...)

Ma come ho detto, non sono sicuro al 100% di questo.

Answer 3

La seguente pagina web descrive in dettaglio i combinatori di punti fissi per la ricorsione reciproca (combinatori di punti di riferimento polivariadici). Deriva il più semplice combinatore fino ad ora . http://okmij.org/ftp/Computation/fixed-point-combinators.html#Poly-variadic

Per facilità di riferimento, qui è il più semplice combinatore polyvariadic in Haskell (one-liner)

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

e qui è in Scheme, un linguaggio rigoroso

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

prega vedere la pagina Web per esempi e ulteriori discussioni.