Clean and type-safe state machine implementation in a statically typed language?

In Haskell, the idiom for this is just to go ahead and execute the next state:

type StateMachine = IO ()a, b, c :: StateMachinea = print "a()" >> bb = print "b()" >> cc = print "c()" >> a

You need not worry that this will overflow a stack or anything like that. If you insist on having states, then you should make the data type more explicit:

data PossibleStates = A | B | Ctype StateMachine = PossibleStates -> IO PossibleStatesmachine A = print "a()" >> return Bmachine B = print "b()" >> return Cmachine C = print "c()" >> return A

You can then get compiler warnings about any StateMachine that forgot some states.

If you use newtype instead of data, you don't incur any overhead. Also, you can wrap each state's function at the point of definition, so the expressions that use them don't have to:

import Control.Monadnewtype State = State { runState :: IO State }a :: Statea = State $ print "a()" >> return bb :: Stateb = State $ print "b()" >> return cc :: Statec = State $ print "c()" >> return arunMachine :: State -> IO ()runMachine s = runMachine =<< runState smain = runMachine a

Edit: it struck me that runMachine has a more general form; a monadic version of iterate:

iterateM :: Monad m => (a -> m a) -> a -> m [a]iterateM f a = do { b <- f a                  ; as <- iterateM f b                  ; return (a:as)                  }main = iterateM runState a

Edit: Hmm, iterateM causes a space-leak. Maybe iterateM_ would be better.

iterateM_ :: Monad m => (a -> m a) -> a -> m ()iterateM_ f a = f a >>= iterateM_ fmain = iterateM_ runState a

Edit: If you want to thread some state through the state machine, you can use the same definition for State, but change the state functions to:

a :: Int -> Statea i = State $ do{ print $ "a(" ++ show i ++ ")"                ; return $ b (i+1)                }b :: Int -> Stateb i = State $ do{ print $ "b(" ++ show i ++ ")"                ; return $ c (i+1)                }c :: Int -> Statec i = State $ do{ print $ "c(" ++ show i ++ ")"                ; return $ a (i+1)                }main = iterateM_ runState $ a 1

The problem with your Haskell code is, that type only introduces a synonym, which is quite similar to what typedef in C does. One important restriction is, that the expansion of the type must be finite, you can't give a finite expansion of your state machine. A solution is using a newtype: A newtype is a wrapper that does only exist for the type checker; there is absolutely zero overhead (excluded stuff that occurs because of generalization that can't be removed). Here is your signature; it typechecks:

newtype FN = FN { unFM :: (IO FN) }

Please note, that whenever you want to use an FN, you have to unpack it first using unFN. Whenever you return a new function, use FN to pack it.