title: State Machine Pattern in Haskell : infinite type error
body: <p>I was trying to implement a state machine in Haskell. A simplified version is the following:</p>
  
  <p>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.</p>
  
  <p>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.</p>
  
  <pre><code>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]
  </code></pre>
  
  <p>Unfortunately, the types for <code>a</code> and <code>b</code> are infinite and GHC complains:</p>
  
  <p><code>Occurs check: cannot construct the infinite type: t = t1 -&gt; (t2, t)</code></p>
  
  <p>What is the way to express this pattern in Haskell?</p>
  
  <p>I could of course do something like:</p>
  
  <pre><code>s 'a' x | x == 0 = (0,'b')
  </code></pre>
  
  <p>using character codes for the state, but the function pattern seems more elegant.</p>