Una "verdadera" función genérica en Haskell

Question

Supongamos que tengo un tipo de datos compuesto -

data M o = M (String,o) 

Ahora, puedo definir una función que funcione para todos, independientemente de Mo. Por ejemplo -

f :: M o -> M o 
f (M (s,o)) = M (s++"!", o) 

Sin embargo, f en realidad no es tan general como me gustaría que fuera. En particular, el uso de f en una expresión fija el tipo de o así que no puedo utilizar f de nuevo con un tipo diferente de o. Por ejemplo, la siguiente no se typecheck -

p f = undefined where 
    m1 = M ("1",()) 
    m2 = M ("2", True) 
    m1' = f m1 
    m2' = f m2 

Se produce el error - Couldn't match expected type 'Bool' with actual type '()'

Sorprendentemente, si no proporciono f como argumento y en su lugar simplemente uso la definición global de f entonces se compila y ¡funciona bien! es decir, esta compila -

p = undefined where 
    m1 = M ("1",()) 
    m2 = M ("2", True) 
    m1' = f m1 
    m2' = f m2 

¿Hay alguna razón en particular para esto? ¿Cómo puedo solucionar este problema es decir, definir una función f que se puede aplicar a todos (M o), incluso cuando el o varía dentro de la misma expresión? Supongo que existen tipos existenciales aquí, pero no puedo entender cómo.

Answer 1

El problema es que el compilador no puede deducir el tipo de p correctamente. Vas a tener que darle una firma de tipo:

p :: (forall o. M o -> M o) -> a 

Este es un tipo de rango 2, por lo que tendrá una extensión del lenguaje:

{-# LANGUAGE Rank2Types #-} 

o

{-# LANGUAGE RankNTypes #-} 

Leer más sobre esto aquí: http://www.haskell.org/haskellwiki/Rank-N_types

Answer 2

¿Hay una r particular? eason para esto?

De hecho, hay una. Para decirlo en una oración: la inferencia de tipo no funcionará correctamente si se levanta la restricción del sistema HM de que los argumentos lambda deben ser monomórficos.

Simon Peyton Jones ha ideado un comprobador de tipos que se extiende HM y permite una mayor polimorfismo rango. Pero en tales casos, se requieren anotaciones de tipo explícito. Ver la respuesta de Sjoerds.

Answer 3

El f en el ámbito de la función p f no es la misma que la función de nivel superior f. Es cualquier función que se da como el argumento cuando se llama p. Como no proporcionó una firma de tipo p, el compilador debe inferir qué es f según cómo lo usa. Su primer uso implica que f :: M() -> M(), que significa p :: (M() -> M()) -> a. Como dijo otra persona, debe dar p una firma explícita usando forall para hacer lo que está tratando de hacer.