¿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 |
+---------+---------+-------------------------------------------------------+
  1. Cuando ambos k1 y k2 son variables, entonces se instancian entre sí.
  2. Cuando solo k1 es una variable, entonces se instanciaal k2 iff k1 no ocurre en k2.
  3. Cuando solo k2 es una variable, entonces se crea una instancia a k1 iff k2 no ocurre en k1.
  4. De lo contrario, verificamos si k1 y k2 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.

Author: false, 2015-04-29

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.

 34
Author: Carl,
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
 26
Author: Reid Barton,
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