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
haskell! = Lambda-calculus – eschulte