Modèle de machine d'état dans Haskell: erreur de type infinie

Question

J'essayais de mettre en œuvre une machine d'état dans Haskell. Une version simplifiée est la suivante:

Dans n'importe quel état, vous pouvez alimenter la machine en entier et vous obtenez un nombre entier. Dans l'état A, la machine double ses entrées. Dans l'état B, la machine vous restitue simplement votre entrée. Chaque fois que vous voyez un zéro dans l'un ou l'autre état, passez à l'autre état. Sinon, l'état ne change pas.

Voici la méthode mon: il suffit que chaque état soit une fonction qui renvoie à la fois sa sortie et la fonction correspondant à l'autre état.

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] 

Malheureusement, les types de a et b sont infinies et se plaint GHC:

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

Quelle est la façon d'exprimer ce modèle dans Haskell?

je pourrais bien sûr faire quelque chose comme:

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

en utilisant des codes de caractères pour l'état, mais le modèle de fonction semble plus élégante.

Answer 1

Vous essayez de définir une machine d'état avec le type

type SM = Int -> (Int, SM) 

mais Haskell ne permet pas. Vous devez utiliser data ou newtype d'introduire un nouveau type nommé:

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

est en dessous de votre programme avec ce changement mineur appliqué, de sorte qu'il compile et se comporte maintenant comme prévu:

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]