State Machine Pattern in Haskell : infinite type error

Question

I was trying to implement a state machine in Haskell. A simplified version is the following:

In any state, you can feed the machine an integer and you get back an integer. In state A, the machine doubles its inputs. In state B, the machine just gives you back your input. Whenever you see a zero in either state, change to the other state. Otherwise, the state does not change.

Here's the my approach: just have each state be a function which returns both its output and the function corresponding to the other state.

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]

Unfortunately, the types for a and b are infinite and GHC complains:

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

What is the way to express this pattern in Haskell?

I could of course do something like:

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

using character codes for the state, but the function pattern seems more elegant.

Answer 1

You are trying to define a state machine with the type

type SM = Int -> (Int, SM)

but Haskell doesn't allow this. You have to use data or newtype to introduce a new named type:

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

Below is your program with this minor change applied, so that it now compiles and behaves as expected:

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]