11

¿Hay un combinador de punto fijo para crear tuplas de funciones mutuamente recursivas? Es decir. Estoy buscando algo así como el Y-Combinator pero que requiere múltiples funciones "recursivas" *, y devolverá una tupla de funciones.Combinador de punto fijo para funciones mutuamente recursivas?

*: no es realmente recursivo, por supuesto, ya que están escritos para tomarse a sí mismos (y a los hermanos) como argumentos, de la forma habitual de Y-Combinator.

Respuesta

8

La criatura que busca es Y * combinador.

Basándose en this page by oleg-at-okmij.org me portado el 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))))) 

El ejemplo clásico de la función recursiva mutua es par/impar por lo que aquí está el ejemplo:

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

Puede explota fácilmente la pila con estas funciones si usas argumentos lo suficientemente grandes, así que aquí está la versión trampolínda de ella, por ejemplo, la integridad que no consume la pila en absoluto:

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

El Y * combinador es muy útil para definir las definiciones recursivas mutuas de analizadores monádicos, de los cuales voy a blog en breve en lambder.com, estad atentos;)

- Lambder

0

No estoy del todo seguro acerca de este. Todavía estoy tratando de encontrar una prueba formal de ello. Pero me parece que no necesitas uno. En Haskell, si tiene algo como:

solución :: (a -> a) -> a
solución f = dejó x = x fx en

principal = {x = vamos. .. y ...; y = x ... ...} x en

puede reescribir principal para

principal = FST $ fijar $ \ (x, y) -> (... Y .. ., ... x ...)

Pero como he dicho, no estoy 100% seguro de esto.

+0

haskell! = Lambda-calculus – eschulte

4

La siguiente página web describe los combinadores de punto fijo para la recursión mutua (combinadores de puntos de ajuste polivalentes) en detalle. Deriva el más simple combinador. http://okmij.org/ftp/Computation/fixed-point-combinators.html#Poly-variadic

Para facilitar la consulta, aquí es el combinador polyvariadic más simple en Haskell (de una sola línea)

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

y aquí está en el esquema, un lenguaje estricto

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

favor mira la página web para ver ejemplos y más discusión.

Cuestiones relacionadas