Los combinadores de punto fijo son útiles cuando intentamos introducir la recursividad en el cálculo lambda. Considere la definición de factorial (usaré la notación similar a Haskell):
fac n = si n == 1 entonces 1 más n * fac (n-1)
En el cálculo lambda no tenemos ‘argumentos’ o coincidencia de patrones, por lo que debemos escribirlo así:
- ¿Cuáles son algunos algoritmos rápidos para calcular la enésima potencia de un número?
- ¿Puedo ser un gran programador si no soy bueno en matemáticas? ¿Cómo puedo mejorar mis habilidades matemáticas?
- ¿Cómo se puede encontrar el número de iteraciones requeridas para la integración usando la regla de Simpson para una precisión dada?
- ¿P es igual a DTIME (2 ^ n)?
- ¿Qué es el helecho Barnsley?
fac = \ n -> si n == 1 entonces 1 más n * fac (n-1)
Es una definición casi correcta de factorial. Desafortunadamente, es recursivo y el cálculo lambda no tiene recursividad, ya que no tiene ‘funciones con nombre’ en absoluto. Hagamos un truco: extraeremos la definición de ‘fac’ a una función separada ‘g’, que tomará ‘fac’ como parámetro y no será recursiva:
fac n = g fac n
g fac = \ n -> si n == 1 entonces 1 más n * fac (n-1)
– o
fac = g fac
g = \ fac, n -> si n == 1 entonces 1 más n * fac (n-1)
Genial, ahora tenemos una definición no recursiva para ‘g’ y una ecuación simple para ‘fac’: debe ser un punto fijo de ‘g’. Como tenemos combinadores de punto fijo (p. Ej., Combinador Y), también podemos escribir ‘fac’ de forma no recursiva:
fac = Y g
