haskell - quita - ¿Cómo uso fix y cómo funciona?

pintura para rayones de autos

Question

Estaba un poco confundido por la documentación de la fix (aunque creo que entiendo lo que se supone que debe hacer ahora), así que miré el código fuente. Eso me dejó más confundido:

fix :: (a -> a) -> a
fix f = let x = f x in x

¿Cómo devuelve esto exactamente un punto fijo?

Decidí probarlo en la línea de comando:

Prelude Data.Function> fix id
...

Y se cuelga allí. Ahora, para ser justos, esto es en mi viejo macbook, que es un poco lento. Sin embargo, esta función no puede ser demasiado costosa desde el punto de vista informático, ya que todo lo que se transfiere a la identificación devuelve esa misma cosa (sin mencionar que no consume tiempo de la CPU). ¿Qué estoy haciendo mal?

Answer 1

Cómo entiendo que es, encuentra un valor para la función, de modo que produce el mismo resultado que usted le da. El truco es que siempre elegirá indefinido (o un bucle infinito, en haskell, indefinido y los bucles infinitos son los mismos) o lo que tenga la mayor cantidad indefinida en él. Por ejemplo, con id,

λ <*Main Data.Function>: id undefined
*** Exception: Prelude.undefined

Como puede ver, undefined es un punto fijo, por lo que fix elegirá. Si en su lugar lo hace (/ x-> 1: x).

λ <*Main Data.Function>: undefined
*** Exception: Prelude.undefined
λ <*Main Data.Function>: (/x->1:x) undefined
[1*** Exception: Prelude.undefined

Entonces, la fix no puede seleccionar indefinido. Para hacerlo un poco más conectado a bucles infinitos.

λ <*Main Data.Function>: let y=y in y
^CInterrupted.
λ <*Main Data.Function>: (/x->1:x) (let y=y in y)
[1^CInterrupted.

De nuevo, una pequeña diferencia. Entonces, ¿cuál es el punto fijo? Intentemos repeat 1 .

λ <*Main Data.Function>: repeat 1
[1,1,1,1,1,1, and so on
λ <*Main Data.Function>: (/x->1:x) $ repeat 1
[1,1,1,1,1,1, and so on

¡Es lo mismo! Como este es el único punto fijo, el fix debe establecerse en él. Disculpe, no hay bucles infinitos ni indefinidos para usted.

Answer 2

Necesitas una forma para que termine el punto fijo. Ampliando su ejemplo, es obvio que no terminará:

fix id
--> let x = id x in x
--> id x
--> id (id x)
--> id (id (id x))
--> ...

Este es un ejemplo real de mi uso de la corrección (tenga en cuenta que no uso la corrección a menudo y que probablemente estaba cansado / sin preocuparme 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 primer argumento de fix debería ser una función que es el caso ''recursivo'' y el segundo argumento es la información sobre la cual actuar. Aquí está el mismo código que una función nombrada:

getQ h
      | pred h = getQ (mutate h)
      | otherwise = h

Si todavía está confundido, tal vez factorial será un ejemplo más fácil:

fix (/recurse d -> if d > 0 then d * (recurse (d-1)) else 1) 5 -->* 120

Observe 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? Esa x convirtió en una función dentro de nuestra rama then .

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 = fx , de 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í!

Answer 3

No estás haciendo nada mal. fix id es un bucle infinito.

Cuando decimos que fix devuelve el menor punto fijo de una función, queremos decir eso en el sentido de la teoría de dominio . Entonces fix (/x -> 2*x-1) no va a devolver 1 , porque aunque 1 es un punto fijo de esa función, no es el menos en el orden del dominio.

No puedo describir el orden del dominio en un solo párrafo o dos, así que lo referiré al enlace de la teoría de dominio 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 resulta en la lista infinita [1,1..] , se podría decir lo mismo con el fix :

fix (/x -> 1:x)

(O simplemente fix (1:) ), que dice, encuéntreme un punto fijo de la función (1:) , IOW un valor x tal que x = 1:x ... tal como lo definimos anteriormente. Como puede ver en la definición, fix no es más que esta idea: recursión encapsulada en una función.

También es un concepto realmente general de recursión: puede escribir cualquier función recursiva de esta manera, incluidas las funciones que utilizan la recursión polimórfica . Entonces, por ejemplo, la función típica de Fibonacci:

fib n = if n < 2 then n else fib (n-1) + fib (n-2)

Se puede escribir usando la fix esta manera:

fib = fix (/f -> /n -> if n < 2 then n else f (n-1) + f (n-2))

Ejercicio: amplíe 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 de dominio. Es realmente genial.

Answer 4

No pretendo entender esto en absoluto, pero si esto ayuda a alguien ... entonces yippee.

Considera la definición de fix . fix f = let x = fx in x . La parte alucinante es que x se define como fx . Pero piensa en eso por un minuto.

x = f x

Dado que x = fx, entonces 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.

Entonces, el truco es que, para terminar, f tiene que generar algún tipo de estructura, de modo que un patrón f posterior pueda emparejar esa estructura y terminar la recursión, sin preocuparse por el "valor" completo de su parámetro (?)

A menos que, por supuesto, quieras hacer algo como crear una lista infinita, como luqui ilustró.

La explicación factorial de TomMD es buena. La firma de tipo de Fix 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 -> b , en otras palabras, (b -> b) -> (b -> b) . Entonces podemos decir que a = (b -> b) . De esta forma, fix toma nuestra función, que es a -> a , o realmente, (b -> b) -> (b -> b) , y devolverá un resultado de tipo a , en otras palabras, b -> b en otras palabras, otra función!

Espera, pensé que se suponía que devolvería un punto fijo ... no una función. Bueno, sí, tipo de (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 sabe cómo recurse (de ahí que uno de los parámetros es una función que se usa para recidivar), y fix enseñó cómo recurse.

¿Recuerdas cómo dije que f tiene que generar algún tipo de estructura para que un patrón posterior de f pueda 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, utilizó un if / then, y eso es lo que causa la terminación. Después de repetidos reemplazos, la parte de la definición completa de fix finalmente deja de definirse en términos de x es cuando es computable y completa.

Answer 5

Una definición clara es: ¡podrías haber reinventado la solución también!