¿Por qué este código Haskell produce el error de "tipo infinito"?

Question

Soy nuevo en Haskell y estoy frente a un error de "no se puede construir el tipo infinito" que no puedo entender.

De hecho, más allá de eso, no he podido encontrar una buena explicación de lo que este error significa, así que si pudieras ir más allá de mi pregunta básica y explicar el error del "tipo infinito", realmente apreciaría eso.

Aquí está el código:

intersperse :: a -> [[a]] -> [a] 

-- intersperse '*' ["foo","bar","baz","quux"] 
-- should produce the following: 
-- "foo*bar*baz*quux" 

-- intersperse -99 [ [1,2,3],[4,5,6],[7,8,9]] 
-- should produce the following: 
-- [1,2,3,-99,4,5,6,-99,7,8,9] 

intersperse _ [] = [] 
intersperse _ [x] = x 
intersperse s (x:y:xs) = x:s:y:intersperse s xs 

Y aquí está el error de tratar de cargarlo en el intérprete:

Prelude> :load ./chapter.3.ending.real.world.haskell.exercises.hs 
[1 of 1] Compiling Main (chapter.3.ending.real.world.haskell.exercises.hs, interpreted) 

chapter.3.ending.real.world.haskell.exercises.hs:147:0: 
Occurs check: cannot construct the infinite type: a = [a] 
When generalising the type(s) for `intersperse' 
Failed, modules loaded: none. 

Gracias.

-

Aquí es un poco de corregir el código y una guía general para tratar con el error "infinita" en Haskell:

código corregido

intersperse _ [] = [] 
intersperse _ [x] = x 
intersperse s (x:xs) = x ++ s:intersperse s xs 

Lo que el el problema era:

Mi estado de firma de tipo s que el segundo parámetro para intercalar es una lista de de listas. Por lo tanto, cuando el patrón coincide con "s (x: y: xs)", xey se convirtieron en listas. Y sin embargo, estaba tratando x e y como elementos, no como listas.

Guía para hacer frente a la "infinita de tipo" error:

mayoría de las veces, cuando recibe este error, se han olvidado de los tipos de las diversas variables que está tratando, y usted han intentado usar una variable como si fuera de algún otro tipo de lo que es. Mire cuidadosamente qué tipo es todo versus cómo lo está usando, y esto generalmente descubrirá el problema.

Answer 1

El problema está en la última cláusula, donde trata xey como elementos, mientras que son listas. Esto funcionará:

intersperse _ [] = [] 
intersperse _ [x] = x 
intersperse s (x:y:xs) = x ++ [s] ++ y ++ intersperse s xs 

se produce el error de tipo infinita porque el: operador tiene el tipo a -> [a] -> [a], mientras que usted lo trata como [a] -> a -> [a] , lo que significa que [a] debe identificarse con a, lo que significaría que a es una lista infinitamente anidada. Eso no está permitido (y no es lo que quieres decir, de todos modos).

Editar: También hay otro error en el código anterior. Debería ser:

intersperse _ [] = [] 
intersperse _ [x] = x 
intersperse s (x:xs) = x ++ [s] ++ intersperse s xs 

Answer 2

Puedo estar equivocado, pero parece que estás tratando de resolver un problema más difícil. Su versión de intersperse no solo intercala el valor con la matriz, sino que también lo allana un nivel.

El módulo List en Haskell realmente proporciona una función intercalada. Introduce el valor entre cada elemento en la lista.Por ejemplo:

intersperse 11 [1, 3, 5, 7, 9] = [1, 11, 3, 11, 5, 11, 7, 11, 9] 
intersperse "*" ["foo","bar","baz","quux"] = ["foo", "*", "bar", "*", "baz", "*", "quux"] 

Estoy asumiendo que esto es lo que quiere hacer porque es lo que mi profesor quería que nosotros hacemos cuando estaba aprendiendo Haskell. Podría, por supuesto, estar totalmente fuera.

Answer 3

También encontré this que explica el significado del error.

Cada vez que el intérprete/compilador me da este error es porque estoy usando una tupla tipo-parametrizada como parámetro formal. Todo funciona correctamente al eliminando la definición de tipo de la función, que contenía variables de tipo.

Todavía no puedo encontrar la manera de solucionarlo y mantener la definición del tipo de función.

Answer 4

A menudo, agregar una definición explícita de tipo puede hacer que el mensaje de error de tipo del compilador tenga más sentido. Pero en este caso, la escritura explícita empeora el mensaje de error del compilador.

Mira lo que pasa cuando dejo GHC adivinar el tipo de intersperse:

Occurs check: cannot construct the infinite type: a = [a] 
    Expected type: [a] -> [[a]] -> [[a]] 
    Inferred type: [a] -> [[a]] -> [a] 
In the second argument of `(:)', namely `intersperse s xs' 
In the second argument of `(:)', namely `y : intersperse s xs' 

que apunta claramente hacia el error en el código. Usando esta técnica no tienes que mirar todo y pensar mucho sobre los tipos, como otros han sugerido hacer.