¿Cómo uso la solución y cómo funciona?

Question

Estaba un poco confundido por la documentación para 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 exactamente esto un punto fijo?

Decidí probarlo en la línea de comando:

Prelude Data.Function> fix id
...

Y cuelga allí. Ahora para ser justos, esto está en mi antiguo MacBook, que es un poco lento. Sin embargo, esta función no puede ser también Computacionalmente caro ya que cualquier cosa que pasó a ID le devuelva la misma cosa (sin mencionar que no está comiendo tiempo de CPU). ¿Qué estoy haciendo mal?

Answer 1

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

Cuando decimos que fix Devuelve el punto menos fijo de una función, queremos decir que en el teoría del dominio sentido. Asi que fix (\x -> 2*x-1) es no Voy a regresar 1, porque aunque 1 es un punto fijo de esa función, no es el el menos uno en el orden de dominio.

No puedo describir el orden de dominio en un mero párrafo o dos, por lo que lo remitiré al enlace de la teoría del 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

Que resulta en la lista infinita [1,1..], podrías decir lo mismo usando fix:

fix (\x -> 1:x)

(O simplemente fix (1:)), que dice encontrarme un punto fijo del (1:) función, es un valor x tal que x = 1:x... Justo como lo definimos anteriormente. Como puede ver en la definición, fix No es nada más que esta idea: recursión encapsulada en una función.

También es un concepto verdaderamente general de recursión: puede escribir cualquier función recursiva de esta manera, incluyendo funciones que usan recursión polimórfica. Entonces, por ejemplo, la función fibonacci típica:

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: expandir 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.

Answer 2

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énselo por un minuto.

x = f x

Como 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, para terminar, f tiene que generar algún tipo de estructura, de modo que un posterior f ¿Puede el patrón coincidir con esa estructura y terminar la recursión, sin preocuparse por el "valor" completo de su parámetro (?)

A menos que, por supuesto, desee hacer algo como crear una lista infinita, como Luqui ilustra.

La explicación factorial de Tommd es buena. La firma de tipo de fijación es (a -> a) -> a. El tipo de firma 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 esa manera, la solución toma nuestra función, que es a -> a, o realmente, (b -> b) -> (b -> b), y devolverá un resultado del tipo a, en otras palabras, b -> b, en otras palabras, ¡otra función!

Espera, pensé que se suponía que debía devolver un punto fijo ... no es 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 sepa cómo recurrir (por lo tanto, uno de los parámetros es una función utilizada para recurrir), y fix le enseñó a recurrir.

Recuerda como dije eso f tiene que generar algún tipo de estructura para que un posterior f ¿Puede el patrón coincidir y terminar? Bueno, eso no es exactamente correcto, supongo. Tommd ilustró cómo podemos expandirnos x para aplicar la función y paso hacia el caso base. Para su función, usó un if/entonces, y eso es lo que causa la terminación. Después de reemplazos repetidos, el in parte de toda la definición de fix eventualmente deja de ser definido en términos de x Y es entonces cuando es computable y completo.

Answer 3

Necesita una forma para que el Fixpoint termine. Expandiendo su 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 solución (nota que no uso la solución con frecuencia y probablemente estaba cansada / no me preocupa 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, tu primera fix El argumento generalmente debe ser una función que es el caso de "recurrir" y el segundo argumento son los datos sobre los cuales 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, entonces el 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? Que x se convirtió en una función dentro de nuestro then rama.

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 debes recordar x = f x, 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 4

Cómo entiendo que es, encuentra un valor para la función, de modo que genera lo mismo que le das. La captura es que siempre elegirá indefinido (o un bucle infinito, en los bucles de Haskell, indefinidos e infinitos son los mismos) o lo que tenga los más indefinidos. Por ejemplo, con ID,

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

Como puede ver, undefinado es un punto fijo, así que fix Lo 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

Asi que fix No puedo elegir indefinido. Para hacerlo un poco más conectado a los 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 ligera diferencia. Entonces, ¿cuál es el punto fijo? Probemos 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! Dado que este es el único punto fijo, fix Debe establecerse en ello. Lo siento fix, sin bucles infinitos o indefinidos para usted.