20 votos

¿Por qué es el tipo de esta función (a -> a) -> a?

¿Por qué es el tipo de esta función (a -> a) -> a?

Prelude> let y f = f (y f)
Prelude> :t y
y :: (t -> t) -> t

No debería ser un infinito/tipo recursivo? Yo iba a tratar de poner en palabras lo que creo que es, debería ser, pero yo simplemente no puede hacerlo por alguna razón.

y :: (t -> t) -> ?WTFIsGoingOnOnTheRHS?

No entiendo cómo f (y f) se resuelve en un valor. El siguiente hace un poco más de sentido para mí:

Prelude> let y f x = f (y f) x
Prelude> :t y
y :: ((a -> b) -> a -> b) -> a -> b

Pero aún así es ridículamente confuso. ¿Qué está pasando?

28voto

ehird Puntos 30215

Bien, y tiene que ser de tipo (a -> b) -> c, para algunos a, b y c aún no lo sabemos; después de todo, toma una función, f, y las aplica a un argumento, por lo que debe ser una función que recibe una función.

Desde y f = f x (de nuevo, para algunos x), sabemos que el tipo de retorno de y debe ser el tipo de retorno de f sí. Así, podemos refinar el tipo de y un poco: debe ser (a -> b) -> b para algunos a y b aún no lo sabemos.

Para averiguar lo a es, sólo tenemos que mirar el tipo del valor que se pasa a f. Es y f, que es la expresión que estamos tratando de averiguar el tipo de la derecha ahora. Estamos diciendo que el tipo de y es (a -> b) -> b (para algunos a, b, etc.), así que podemos decir que esta aplicación de la y f debe ser de tipo b sí.

Así, el tipo de argumento a f es b. Poner todo de nuevo juntos, y llegamos (b -> b) -> b - que es, por supuesto, lo mismo que (a -> a) -> a.

He aquí una más intuitiva, pero menos precisa visión de las cosas: estamos diciendo que y f = f (y f), que podemos ampliar hasta el equivalente y f = f (f (y f)), y f = f (f (f (y f))), y así sucesivamente. Así, sabemos que siempre podemos aplicar otra f alrededor de toda la cosa, y ya que la "cosa" en cuestión es el resultado de la aplicación f a un argumento, f tiene que tener el tipo a -> a; y ya que acaba de concluir, que todo es el resultado de la aplicación f para un argumento, el tipo de retorno de y debe ser de la f sí - venir juntos, de nuevo, como (a -> a) -> a.

9voto

John L Puntos 20989

@ehird hecho un buen trabajo explicando el tipo, así que me gustaría mostrar cómo se puede resolver en un valor con algunos ejemplos.

f1 :: Int -> Int
f1 _ = 5

-- expansion of y applied to f1
y f1
f1 (y f1)  -- definition of y
5          -- definition of f1 (the argument is ignored)

-- here's an example that uses the argument, a factorial function
fac :: (Int -> Int) -> (Int -> Int)
fac next 1 = 1
fac next n = n * next (n-1)

y fac :: Int -> Int
fac (y fac)   -- def. of y
  -- at this point, further evaluation requires the next argument
  -- so let's try 3
fac (y fac) 3  :: Int
3 * (y fac) 2             -- def. of fac
3 * (fac (y fac) 2)       -- def. of y
3 * (2 * (y fac) 1)       -- def. of fac
3 * (2 * (fac (y fac) 1)  -- def. of y
3 * (2 * 1)               -- def. of fac

Usted puede seguir los mismos pasos que con cualquier función que le gusta ver lo que va a suceder. Ambos de estos ejemplos convergen a los valores, pero que no siempre sucede.

8voto

Luis Casillas Puntos 11718

A solo dos puntos a añadir a otros las respuestas de las personas.

La función que se está definiendo es generalmente llamado fix, y es un punto fijo de combinador: una función que calcula el punto fijo de otra función. En matemáticas, el punto fijo de una función f es un argumento x tal que f x = x. Esto ya permite inferir que el tipo de fix ha (a -> a) -> a; "función que toma una función en a a a, y devuelve un a."

Usted ha llamado a su función y, lo que parece ser, después de la de Y combinator, pero esto es un error en nombre de la Y combinator es un específico punto fijo combinator, pero no es el mismo que el que hemos definido aquí.

No entiendo cómo f (y f) se resuelve en un valor.

Bien, el truco es que Haskell es un no-estricto (una.k.a. "perezoso") del lenguaje. El cálculo de f (y f) puede terminar si f no necesita evaluar su y f argumento en todos los casos. Así que si estás en la definición de factorial (como John L ilustra), fac (y fac) 1 evalúa a 1 sin evaluar y fac.

Estricto idiomas no puede hacer esto, por lo que en esos idiomas no se puede definir un punto fijo combinador de esta manera. En esos idiomas, los libros de texto de punto fijo combinator es la de Y combinator adecuada.

5voto

Dan Burton Puntos 26639

Déjenme decirles acerca de un combinador. Es el llamado "punto fijo combinator" y que tiene la siguiente propiedad:

La Propiedad: el "punto fijo combinator" toma una función f :: (a -> a) y descubre un "punto fijo" x :: a de esa función tal que f x == x. Algunas implementaciones de punto fijo combinador podría ser mejor o peor en el "descubrimiento", pero suponiendo que se termina, se va a producir un punto fijo de la función de entrada. Cualquier función que satisface La Propiedad puede ser llamado un "punto fijo combinator".

Llamar a este "punto fijo combinator" y. Basado en lo que acabamos de decir, se cumplen las siguientes condiciones:

-- as we said, y's input is f :: a -> a, and its output is x :: a, therefore
y :: (a -> a) -> a

-- let x be the fixed point discovered by applying f to y
y f == x -- because y discovers x, a fixed point of f, per The Property
f x == x -- the behavior of a fixed point, per The Property

-- now, per substitution of "x" with "f x" in "y f == x"
y f == f x
-- again, per substitution of "x" with "y f" in the previous line
y f == f (y f)

Así que hay que ir. Se han definido y en términos de lo esencial de la propiedad del punto fijo combinador:
y f == f (y f). En lugar de asumir que y f descubre x, se puede asumir que x representa un divergentes de cálculo, y aún llegan a la misma conclusión (iinm).

Ya que su función se ajusta a La Propiedad, se puede concluir que es un punto fijo combinator, y que el resto de propiedades que hemos indicado, incluyendo el tipo, son aplicables a su función.

Esto no es exactamente una prueba sólida, pero espero que proporciona información adicional.

Iteramos.com

Iteramos es una comunidad de desarrolladores que busca expandir el conocimiento de la programación mas allá del inglés.
Tenemos una gran cantidad de contenido, y también puedes hacer tus propias preguntas o resolver las de los demás.

Powered by:

X