2012-01-17 1 views
6

Antecedentes: estoy investigando la recursión anónima, y ​​estoy asumiendo el desafío de implementar el preludio sin utilizar ninguna recursividad con nombre solo para ayudarlo a que todo quede bien en mi mente. Aún no llegué, y en el camino me encontré con algo que no está relacionado pero que sigue siendo interesante.Funciones equivalentes que producen diferentes resultados de intérprete

map1  = \f -> \x -> if (tail x) == [] 
         then [f (head x)] 
         else f (head x) : (map1 f (tail x)) 

map2 f x =    if (tail x) == [] 
         then [f (head x)] 
         else f (head x) : (map2 f (tail x)) 

map3 f (x:xs) = if xs == [] then [f x] else f x : (map3 f xs) 

map4 f (x:[]) = [f x] 
map4 f (x:xs) = f x : map4 f xs 

GHC se queja de la primera, está muy bien con la segunda y la tercera y cuarta son allí sólo para mostrar cómo podrían ser implementadas de manera diferente.

*Main> map1 (*2) [1..10] 

<interactive>:1:15: 
    No instance for (Num()) 
     arising from the literal `10' 
    Possible fix: add an instance declaration for (Num()) 
    In the expression: 10 
    In the second argument of `map1', namely `[1 .. 10]' 
    In the expression: map1 (* 2) [1 .. 10] 
*Main> map2 (*2) [1..10] 
[2,4,6,8,10,12,14,16,18,20] 
*Main> map3 (*2) [1..10] 
[2,4,6,8,10,12,14,16,18,20] 
*Main> map4 (*2) [1..10] 
[2,4,6,8,10,12,14,16,18,20] 

Si agrego un tipo de firma a map1, todo está bien.

map1 :: Eq a => (a -> b) -> [a] -> [b] 

Las dos primeras funciones parecen más o menos lo mismo para mí, así que supongo que mi pregunta es, simplemente, "¿Qué está pasando aquí?"

+2

No estoy seguro si tiene razones específicas para escribir de esta manera. ¿Por qué no usa [] como caso base para la recursión en lugar de (x: [])? Ninguna de sus funciones funcionará con la lista vacía. –

Respuesta

12

Fuiste mordido por el . Cualquier cosa que esté escrita como foo = ..., lo que significa que no hay argumentos para la definición, y no se proporciona ningún tipo explícito, debe tener un tipo no genérico de acuerdo con esta restricción. El tipo genérico en este caso, como usted dijo, tuvo que ser Eq a => (a -> b) -> [a] -> [b], pero dado que se aplica la restricción de monomorfismo, ambos a y b se reemplazan por (), el tipo más simple que se puede inferir para las variables de tipo disponibles.

6

Pero, si se utiliza el null sin restricciones en lugar de (== []),

Prelude> let map0 = \f -> \x -> if null (tail x) then [f (head x)] else f (head x) : map0 f (tail x) 
Prelude> :t map0 
map0 :: (a -> t) -> [a] -> [t] 
Prelude> map (*2) [1 .. 10] 
[2,4,6,8,10,12,14,16,18,20] 

funciona sin argumentos o una firma. Solo las variables de tipo restringido están sujetas a la restricción de monomorfismo.

Y si se pone la definición de map1 en un archivo y se intenta compilar o cargarlo en ghci,

Ambiguous type variable `a0' in the constraint: 
    (Eq a0) arising from a use of `==' 
Possible cause: the monomorphism restriction applied to the following: 
    map1 :: forall t. (a0 -> t) -> [a0] -> [t] (bound at Maps.hs:3:1) 
Probable fix: give these definition(s) an explicit type signature 
       or use -XNoMonomorphismRestriction 
In the expression: (tail x) == [] 
In the expression: 
    if (tail x) == [] then 
     [f (head x)] 
    else 
     f (head x) : (map1 f (tail x)) 
In the expression: 
    \ x 
    -> if (tail x) == [] then 
      [f (head x)] 
     else 
      f (head x) : (map1 f (tail x)) 

ghci sólo se quejaron de la manera que lo hizo porque utiliza ExtendedDefaultRules, de lo contrario tendrían Obtuve un mensaje de error comprensible.

Cuestiones relacionadas