haskell - verificar - ingreso a canada

¿Cómo puede una eta-reducción de una función bien escrita resultar en un error de tipo?

Question

Estaba jugando con las lentes de van Laarhoven y me encontré con un problema en el que el comprobador de tipos rechaza la forma eta-reducida de una función bien escrita:

{-# LANGUAGE RankNTypes #-}

import Control.Applicative

type Lens c a = forall f . Functor f => (a -> f a) -> (c -> f c)

getWith :: (a -> b) -> ((a -> Const b a) -> (c -> Const b c)) -> (c -> b)
getWith f l = getConst . l (Const . f)

get :: Lens c a -> c -> a
get lens = getWith id lens

Los controles de tipo anteriores, pero si eta-reducir get a

get :: Lens c a -> c -> a
get = getWith id

Entonces GHC (7.4.2) se queja de que

Couldn''t match expected type `Lens c a''
            with actual type `(a0 -> Const b0 a0) -> c0 -> Const b0 c0''
Expected type: Lens c a -> c -> a
  Actual type: ((a0 -> Const b0 a0) -> c0 -> Const b0 c0)
               -> c0 -> b0
In the return type of a call of `getWith''
In the expression: getWith id

Puedo entender que si la función no tuviera una firma de tipo explícita, entonces la reducción eta en combinación con la restricción de monomorfismo podría confundir la inferencia de tipo, especialmente cuando se trata de tipos de rango más alto, pero en este caso no lo soy. seguro de lo que está pasando.

¿Qué causa que GHC rechace la forma eta-reducida y esto es un error / limitación en GHC o algún problema fundamental con los tipos de rango más alto?

Answer 1

En realidad, es bastante sencillo: GHC infiere los tipos por expresión , luego comienza a unificarlos a través de = . Esto funciona siempre bien cuando solo hay rangos de tipo 1, porque se elige el más polimórfico (que está bien definido); Así que cualquier unificación que sea posible tendrá éxito.

Pero no elegirá un tipo de rango 2 más general, incluso si eso fuera posible, por getWith id se infiere que getWith id es ((a -> Const aa) -> c -> Const ac) -> (c -> a) lugar de (forall f . Functor f => (a -> fa) -> c -> fc) -> (c -> a) . Supongo que si GHC hiciera esas cosas, la inferencia de tipo tradicional de rango 1 ya no funcionaría en absoluto. O simplemente nunca terminaría, porque no existe uno de los tipos de rango-n más polimórficos bien definidos.

Eso no explica por qué no puede ver en la firma de get que necesita elegir el rango 2 aquí, pero presumiblemente hay una buena razón para eso también.

Answer 2

Yo diría que la razón no está en la reducción de η en sí misma, el problema es que con RankNTypes pierde tipos principales e inferencia de tipos.

El problema con la inferencia de tipos con rangos de orden superior es cuando se deduce el tipo de λx.M para obedecer la regla

     Γ, x:σ |- M:ρ
----------------------
  Γ |- λx:σ.M : σ→ρ

no sabemos qué tipo σ debemos elegir para x . En el caso del sistema de tipo Hindley-Milner, nos limitamos a tipos libres de cuantificadores de tipo para x y la inferencia es posible, pero no con tipos de clasificación arbitraria.

Entonces, incluso con RankNTypes , cuando el compilador encuentra un término sin información de tipo explícita, recurre a Hindley-Milner e infiere su tipo principal de rango 1. Sin embargo, en su caso, el tipo que necesita para getWith id es rango 2 y, por lo tanto, el compilador no puede deducirlo por sí mismo.

Tu caso explicito

get lens = getWith id lens

corresponde a la situación en la que el tipo de x ya está dado explícitamente λ(x:σ).Mx . El compilador conoce el tipo de lens antes de verificar el tipo getWith id lens .

En el caso reducido.

get = getWith id

el compilador tiene que inferir el tipo de getWidth id de getWidth id por sí mismo, por lo que se mantiene con Hindley-Milner e infiere el tipo inadecuado de rango 1.