haskell - resueltos - transformaciones lineales ejemplos

Efectos de la restricción de monomorfismo en las restricciones de clase de tipo

Question

Este código se rompe cuando se agrega una declaración de tipo para baz :

baz (x:y:_) = x == y
baz [_] = baz []
baz [] = False

Una explicación común (ver ¿Por qué no puedo declarar el tipo inferido? Por ejemplo) es que se debe a una recursión polimórfica.

Pero esa explicación no explica por qué el efecto desaparece con otro ejemplo polimórficamente recursivo:

foo f (x:y:_) = f x y
foo f [_] = foo f []
foo f [] = False

Tampoco explica por qué GHC piensa que la recursión es monomórfica sin declaración de tipo.

¿Se puede aplicar la explicación del ejemplo con reads en http://www.haskell.org/onlinereport/decls.html#sect4.5.5 a mi caso baz ?

Es decir, agregar una firma elimina la restricción de monomorfismo y, sin la restricción, aparece una ambigüedad del lado derecho [], con un tipo "intrínsecamente ambiguo" de todos forall a . Eq a => [a] forall a . Eq a => [a] ?

Answer 1

Las ecuaciones para baz están en un grupo vinculante, la generalización se realiza después de que se haya escrito todo el grupo. Sin una firma de tipo, eso significa que se asume que baz tiene un monotipo, por lo que el tipo de [] en la llamada recursiva viene dado por eso (mire la salida de ghc -ddump-simpl). Con una firma de tipo, al compilador se le dice explícitamente que la función es polimórfica, por lo que no puede asumir que el tipo de [] en la llamada recursiva sea el mismo, por lo tanto, es ambiguo.

Como dijo John L, en foo , el tipo se fija por la aparición de f , siempre que f tenga un monotipo. Puede crear la misma ambigüedad dando a f el mismo tipo que (==) (que requiere Rank2Types ),

{-# LANGUAGE Rank2Types #-}
foo :: Eq b => (forall a. Eq a => a -> a -> Bool) -> [b] -> Bool
foo f (x:y:_) = f x y
foo f[_] = foo f []
foo _ [] = False

Eso da

Ambiguous type variable `b0'' in the constraint:
  (Eq b0) arising from a use of `foo''
Probable fix: add a type signature that fixes these type variable(s)
In the expression: foo f []
In an equation for `foo'': foo f [_] = foo f []

Answer 2

Tu segundo ejemplo no es polimórficamente recursivo. Esto se debe a que la función f aparece tanto en la LHS como en la RHS de la definición recursiva. También considere el tipo de foo , (a -> a -> Bool) -> [a] -> Bool . Esto corrige el tipo de elemento de lista para que sea idéntico al tipo de los argumentos de f . Como resultado, GHC puede determinar que la lista vacía en el RHS debe tener el mismo tipo que la lista de entrada.

No creo que el ejemplo de reads sea ​​aplicable al caso baz , porque GHC es capaz de compilar baz sin firma de tipo y la restricción de monomorfismo está deshabilitada. Por lo tanto, espero que el algoritmo de tipo de GHC tenga algún otro mecanismo por el cual elimine la ambigüedad.