Definí un nuevo tipo de datos en Haskell de la siguiente manera:

data Pro = P Int Pro | Idle
              deriving Show

Luego definí a un operador que funciona para este nuevo tipo de datos:

(>*>) :: Pro -> Pro -> Pro
Idle        >*>   ps  = ps
P i ps      >*>   qs  = P i (ps >*> qs)

Entonces, infi r = P r Idle >*> (infi (r+1)) podría representar los datos infinitos y si escribo infi4 1 en la terminal, se imprimirá infinitamente.

Más tarde, me di cuenta de que esta nueva definición de tipo de datos podría modificarse para:

data Try = T [Int] 
     deriving Show

Son bastante similares y el último es una especie de lista, que parece más fácil. Pero cuando definí los siguientes datos infinitos:

(>/>) :: Try -> Try -> Try
T []    >/>     i       = i 
T ts    >/>     T qs    = T (ts ++ qs )

infi2 r = (T [r]) >/> (infi2 r)

Y trató de imprimirlo en la terminal, mostró que:

Exception: stack overflow

Parece que la propiedad perezosa de Haskell no funcionará en este nuevo tipo de datos. Dosis cualquiera podría decirme el motivo y cómo imprimir los datos infinitos por el segundo tipo de datos.

2
Troy Yao 4 feb. 2015 a las 22:14

2 respuestas

La mejor respuesta

Necesitas tilda:

(>/>) :: Try -> Try -> Try
T []    >/>     i       = i 
T ts    >/>     ~(T qs)    = T (ts ++ qs )

Además, no necesita la primera cláusula, por lo que (>/>) se puede definir como

(>/>) :: Try -> Try -> Try
~(T ts) >/> ~(T qs) = T (ts ++ qs)

La definición de {{x0}} es perezosa, porque no hay un patrón que coincida con el segundo argumento.

ACTUALIZACIÓN

Como lo sugiere @MigMit, puede usar newtype y su definición original de (>/>) funcionará. Eche un vistazo a la sección 2 The messy bits de https://wiki.haskell.org/Newtype

3
user3237465 4 feb. 2015 a las 20:33

La otra respuesta es correcta al decir que una solución adecuada es usar un patrón ~ (también llamado patrón irrefutable o patrón perezoso) o un nuevo tipo, pero veamos el por qué .. .

Aquí están sus definiciones nuevamente para referencia:

(>/>) :: Try -> Try -> Try
T []    >/>     i       = i 
T ts    >/>     T qs    = T (ts ++ qs)

infi2 r = T [r] >/> infi2 r -- I've omitted unnecessary parentheses

Ahora, si llamas {{x0}}, se produce la siguiente reducción:

   infi2 1

=    { expanding the definition of infi2 }

   T [1] >/> infi2 1

Ahora bien, este es el punto importante. Queremos reducir la función más externa, que es >/>. Pero tenemos que decidir cuál de los casos se aplica. Es fácil para ver que el primero no lo hace, porque T [1] no coincide con T []. El segundo caso, sin embargo, requiere que el segundo argumento de >/> tenga la forma T qs, y tenemos infi2 1. Aunque Try solo tiene un constructor, GHC / Haskell no hará tal acto de fe. En su lugar, evaluará infi2 1 más hasta que aprenda su constructor más externo. Entonces, el siguiente paso de reducción es

   T [1] >/> infi2 1

=    { expanding the definition of infi2 }

   T [1] >/> (T [1] >/> infi2 1)

Ahora volvemos a estar exactamente en la misma situación. Aún no podemos reducir el >/> más externo porque no conocemos el constructor del argumento correcto; así que tenemos que reducirlo aún más. Pero, de nuevo, tenemos que reducir la argumento derecho más para aprender sobre el constructor del argumento derecho del interior >/>:

   T [1] >/> (T [1] >/> infi2 1)

=    { expanding the definition of infi2 }

   T [1] >/> (T [1] >/> infi2 1)

=    { expanding the definition of infi2 }

   T [1] >/> (T [1] >/> (T [1] >/> infi2 1))

=    ...

Esto continuará indefinidamente hasta que la memoria se llene. Nunca podremos hacer ningún progreso real.

Mirando hacia atrás en las definiciones originales una vez más, es (con un poco de práctica) en realidad es posible ver esto sin hacer la expansión completa:

(>/>) :: Try -> Try -> Try
T []    >/>     i       = i 
T ts    >/>     T qs    = T (ts ++ qs)

infi2 r = T [r] >/> infi2 r

En el segundo caso de la definición de >/>, producimos un T solo después sabemos que ambos argumentos son T s. Entonces, en infi2 r, solo podemos reducir el >/> externo después de que infi2 r regrese, pero esa es una llamada recursiva ...

Ahora sobre las soluciones que abordan esto:

Utilice un tipo nuevo

Con

newtype Try = T [Int]
  deriving (Show)

En lugar de data, la coincidencia de patrones en T se convierte en una operación prohibida. Se garantiza que un nuevo tipo tendrá la misma representación en tiempo de ejecución que el tipo subyacente (aquí [Int]), y la aplicación del constructor T o la coincidencia de patrones tiene un efecto en la conversión de los tipos, pero no tiene ningún efecto en el tiempo de ejecución.

Por lo tanto, una vez que tengamos

T [1] >/> infi2 1

Para tomar una decisión para uno de los casos, ahora solo vemos que la primera lista es no vacía, por lo que no se puede aplicar el primer caso. El segundo caso tiene lado izquierdo.

T ts >/> T qs = ...

Que bajo el supuesto de que la coincidencia de patrones en T es un noop es trivialmente cierto y puede reducirse inmediatamente.

Usando un patrón {{x0}}

De manera similar, si seguimos usando data, pero escribimos

T ts >/> ~(T qs) = ...

La otra respuesta es correcta al decir que una corrección adecuada es usar un patrón {{x0}} (también llamado patrón irrefutable o patrón perezoso) o un PREVIETE, pero veamos el por qué ...

Extrayendo explícitamente

Una tercera opción es escribir una función de extracción.

unT :: Try -> [Int]
unT (T ts) = ts

Y luego decir

(>/>) :: Try -> Try -> Try
T []    >/>     i       = i 
T ts    >/>     qs      = T (ts ++ unT qs)

Esto hace que sea obvio que no esperamos nada del segundo argumento en el momento del patrón. Esta versión se corresponde mucho a lo que se compilará la versión {{x0}}.

Para concluir, veamos la reducción ahora:

   infi2 1

=    { expanding the definition of infi2 }

   T [1] >/> infi2 1

=    { expanding the definition of >/> }

   T ([1] ++ unT (infi2 1))

Suponiendo que queremos imprimir el resultado y una reducción total, continuemos desde aquí por un momento:

   T ([1] ++ unT (infi2 1))

=    { expanding the definition of ++ }

   T (1 : unT (infi2 1))

=    { expanding the definition of infi2 }

   T (1 : unT (T [1] >/> infi2 1))

=    { expanding the definition of >/> }

   T (1 : unT (T ([1] ++ unT (infi2 1))))

=    { expanding the definition of the outer unT }

   T (1 : ([1] ++ unT (infi2 1)))

En este punto, debería ser obvio que de hecho obtenemos la lista infinita de forma incremental.

4
kosmikus 6 feb. 2015 a las 19:12