Este tutorial fue analizado por especialistas para garantizar la exactitud de este enunciado.
Solución:
No estás haciendo nada malo. fix id es un bucle infinito.
cuando decimos eso fix devuelve el punto fijo mínimo de una función, lo decimos en el sentido de la teoría del dominio. Asi que fix (x -> 2*x-1) es no voy a volver 1porque aunque 1 es un punto fijo de esa función, no es el menos uno en la ordenación del dominio.
No puedo describir el orden de los dominios en uno o dos párrafos, por lo que lo referiré al enlace de la teoría de dominios anterior. Es un excelente tutorial, fácil de leer y bastante esclarecedor. Lo recomiendo altamente.
Para la vista desde 10,000 pies, fix es una función de orden superior que codifica la idea de recursión. Si tienes la expresión:
let x = 1:x in x
Lo que da como resultado la lista infinita. [1,1..]podrías decir lo mismo usando fix:
fix (x -> 1:x)
(O simplemente fix (1:)), que dice encuéntrame un punto fijo de la (1:) función, OIA un valor x tal que x = 1:x… tal como lo definimos anteriormente. Como se puede ver en la definición, fix no es más que esta idea: recursividad encapsulada en una función.
También es un concepto verdaderamente general de recursión: puede escribir cualquier función recursiva de esta manera, incluidas las funciones que usan recursividad polimórfica. Entonces, por ejemplo, la típica función de fibonacci:
fib n = if n < 2 then n else fib (n-1) + fib (n-2)
Se puede escribir usando fix Por aquí:
fib = fix (f -> n -> if n < 2 then n else f (n-1) + f (n-2))
Ejercicio: amplía la definición de fix para mostrar que estas dos definiciones de fib son equivalentes.
Pero para una comprensión completa, lea sobre la teoría del dominio. Es algo realmente genial.
No pretendo entender esto en absoluto, pero si esto ayuda a alguien... entonces yippee.
Considere la definición de fix. fix f = let x = f x in x. La parte alucinante es que x Se define como f x. Pero piénsalo por un minuto.
x = f x
Como x = fx, podemos sustituir el valor de x en el lado derecho de eso, ¿verdad? Asi que, por lo tanto...
x = f . f $ x -- or x = f (f x)
x = f . f . f $ x -- or x = f (f (f x))
x = f . f . f . f . f . f . f . f . f . f . f $ x -- etc.
Así que el truco es, para terminar, f tiene que generar algún tipo de estructura, para que una posterior f puede el patrón coincidir con esa estructura y terminar la recursividad, sin preocuparse realmente por el "valor" completo de su parámetro (?)
A menos, por supuesto, que quieras hacer algo como crear una lista infinita, como ilustró luqui.
La explicación factorial de TomMD es buena. La firma de tipo de corrección es (a -> a) -> a. La firma de tipo para (recurse d -> if d > 0 then d * (recurse (d-1)) else 1) es (b -> b) -> b -> ben otras palabras, (b -> b) -> (b -> b). Entonces podemos decir que a = (b -> b). De esa manera, fix toma nuestra función, que es a -> ao realmente, (b -> b) -> (b -> b)y devolverá un resultado de tipo aen otras palabras, b -> ben otras palabras, ¡otra función!
Espera, pensé que se suponía que devolvería un punto fijo... no una función. Bueno, lo hace, más o menos (ya que las funciones son datos). Puedes imaginar que nos dio la función definitiva para encontrar un factorial. Le dimos una función que no sabía cómo recurrir (por lo tanto, uno de los parámetros es una función que se usa para recurrir), y fix le enseñó a recurrir.
Recuerda como dije eso f tiene que generar algún tipo de estructura para que una posterior f ¿Puede el patrón coincidir y terminar? Bueno, eso no es exactamente correcto, supongo. TomMD ilustró cómo podemos expandir x para aplicar la función y avanzar hacia el caso base. Para su función, usó un si/entonces, y eso es lo que causa la terminación. Después de repetidos reemplazos, el in parte de toda la definición de fix finalmente deja de definirse en términos de x y ahí es cuando es computable y completo.
Necesita una forma de que el punto fijo termine. Expandiendo tu ejemplo, es obvio que no terminará:
fix id
--> let x = id x in x
--> id x
--> id (id x)
--> id (id (id x))
--> ...
Aquí hay un ejemplo real de mí usando la corrección (tenga en cuenta que no uso la corrección con frecuencia y probablemente estaba cansado/no me preocupaba por el código legible cuando escribí esto):
(fix (f h -> if (pred h) then f (mutate h) else h)) q
WTF, dices! Bueno, sí, pero hay algunos puntos realmente útiles aquí. En primer lugar, su primera fix el argumento debería ser normalmente una función que es el caso 'recursivo' y el segundo argumento son los datos sobre los que actuar. Aquí está el mismo código que una función con nombre:
getQ h
| pred h = getQ (mutate h)
| otherwise = h
Si todavía está confundido, quizás factorial sea un ejemplo más fácil:
fix (recurse d -> if d > 0 then d * (recurse (d-1)) else 1) 5 -->* 120
Note la evaluación:
fix (recurse d -> if d > 0 then d * (recurse (d-1)) else 1) 3 -->
let x = (recurse d -> if d > 0 then d * (recurse (d-1)) else 1) x in x 3 -->
let x = ... in (recurse d -> if d > 0 then d * (recurse (d-1)) else 1) x 3 -->
let x = ... in (d -> if d > 0 then d * (x (d-1)) else 1) 3
Oh, ¿acabas de ver eso? Ese x se convirtió en una función dentro de nuestro then sucursal.
let x = ... in if 3 > 0 then 3 * (x (3 - 1)) else 1) -->
let x = ... in 3 * x 2 -->
let x = ... in 3 * (recurse d -> if d > 0 then d * (recurse (d-1)) else 1) x 2 -->
En lo anterior, debe recordar x = f xde ahí los dos argumentos de x 2 al final en lugar de solo 2.
let x = ... in 3 * (d -> if d > 0 then d * (x (d-1)) else 1) 2 -->
¡Y me detendré aquí!
Recuerda que tienes la capacidad de interpretar .