¿Es posible obtener el error tipo infinito en Haskell 98?
Estoy implementando un sistema tipo para un nuevo lenguaje de programación funcional y actualmente estoy escribiendo la función para unificar dos tipos. Hay cuatro casos que dos consideran:
+---------+---------+-------------------------------------------------------+
| k1 | k2 | action |
+=========+=========+=======================================================+
| var | var | k1 := k2 ^ k2 := k1 |
+---------+---------+-------------------------------------------------------+
| var | non var | if (!occurs(k1, k2)) k1 := k2 |
+---------+---------+-------------------------------------------------------+
| non var | var | if (!occurs(k2, k1)) k2 := k1 |
+---------+---------+-------------------------------------------------------+
| non var | non var | ensure same name and arity, and unify respective args |
+---------+---------+-------------------------------------------------------+
- Cuando ambos
k1
yk2
son variables, entonces se instancian entre sí. - Cuando solo
k1
es una variable, entonces se instanciaalk2
iffk1
no ocurre enk2
. - Cuando solo
k2
es una variable, entonces se crea una instancia ak1
iffk2
no ocurre enk1
. - De lo contrario, verificamos si
k1
yk2
tienen el mismo nombre y aridad, y unificamos sus respectivos argumentos.
Para el segundo y tercer caso, necesitamos implementar la verificación de modo que no nos queda atascado en un bucle infinito. Sin embargo, dudo que un programador sea capaz de construir un tipo infinito en absoluto.
En Haskell, es fácil construir un tipo infinito: {[15]]}
let f x = f
Sin embargo, no he sido capaz de construir un tipo infinito no importa cuánto lo intente. Tenga en cuenta que no hice uso de ninguna extensión de idioma.
La razón por la que estoy preguntando esto es porque si no es posible construir un tipo infinito en absoluto, entonces ni siquiera me molestaré en implementar la comprobación de ocurre para tipos en mi sistema de tipos.
2 answers
data F f = F (f F)
En GHC 7.10.1, recibo el mensaje:
kind.hs:1:17:
Kind occurs check
The first argument of ‘f’ should have kind ‘k0’,
but ‘F’ has kind ‘(k0 -> k1) -> *’
In the type ‘f F’
In the definition of data constructor ‘F’
In the data declaration for ‘F’
El mensaje no dice que es un tipo infinito, pero eso es esencialmente lo que es cuando se produce la comprobación falla.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2015-04-29 16:40:49
Otro ejemplo simple
GHCi, version 7.10.1: http://www.haskell.org/ghc/ :? for help
Prelude> let x = undefined :: f f
<interactive>:2:24:
Kind occurs check
The first argument of ‘f’ should have kind ‘k0’,
but ‘f’ has kind ‘k0 -> k1’
In an expression type signature: f f
In the expression: undefined :: f f
In an equation for ‘x’: x = undefined :: f f
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2015-04-29 16:44:36