Patrón de máquina de estado en Haskell: error de tipo infinito

Question

Estaba intentando implementar una máquina de estado en Haskell. Una versión simplificada es la siguiente:

En cualquier estado, puede alimentar a la máquina con un número entero y obtendrá un número entero. En el estado A, la máquina duplica sus entradas. En el estado B, la máquina simplemente te devuelve tu entrada. Siempre que vea un cero en cualquier estado, cambie al otro estado. De lo contrario, el estado no cambia.

Aquí está mi enfoque: simplemente haga que cada estado sea una función que devuelva tanto su salida como la función correspondiente al otro estado.

module Main where 

a x | x == 0 = (0,b) 
a x = (2*x, a) 

b x | x == 0 = (0,a) 
b x = (x, b) 

evalstate s [] = [] 
evalstate s (x:xs) = (v:evalstate s' xs) 
    where (v,s') = s x 

main :: IO() 
main = putStrLn $ show $ evalstate a [1,1,2,3,4,0,2,3,3] 

Por desgracia, los tipos de a y b son infinitos y GHC se queja:

Occurs check: cannot construct the infinite type: t = t1 -> (t2, t)

¿Cuál es la manera de expresar este patrón en Haskell?

que podría, por supuesto, hacer algo como:

s 'a' x | x == 0 = (0,'b') 

usando códigos de caracteres para el estado, pero el patrón de la función parece más elegante.

Answer 1

usted está tratando de definir una máquina de estados con el tipo

type SM = Int -> (Int, SM) 

pero Haskell no permite esto. Usted tiene que utilizar data o newtype a introducir un nuevo tipo llamado:

newtype SM = SM (Int -> (Int, SM)) 

A continuación se muestra el programa con este pequeño cambio aplicado, de modo que ahora compila y se comporta como se esperaba:

module Main where 

newtype SM = SM (Int -> (Int, SM)) 

a = SM a' 
    where 
    a' x | x == 0 = (0, b) 
    a' x = (2 * x, a) 

b = SM b' 
    where 
    b' x | x == 0 = (0, a) 
    b' x = (x, b) 

evalstate s [] = [] 
evalstate (SM s) (x : xs) = (v:evalstate s' xs) 
    where (v, s') = s x 

main :: IO() 
main = putStrLn $ show $ evalstate a [1,1,2,3,4,0,2,3,3]