Haskell中的状态机模式:无限类型错误

Question

我试图在Haskell中实现一个状态机.简化版如下:

在任何状态下,您都可以为机器提供一个整数,然后返回一个整数.在状态A中,机器将其输入加倍.在状态B,机器只是给你你的输入.每当您在任一状态中看到零时,请更改为其他状态.否则,状态不会改变.

这是我的方法:让每个状态成为一个函数,它返回其输出和对应于另一个状态的函数.

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]

不幸的是,GHC 的类型a和b无限的抱怨:

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

在Haskell中表达这种模式的方法是什么？

我当然可以这样做:

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

使用字符代码表示状态,但功能模式看起来更优雅.

Answer 1

您正在尝试使用该类型定义状态机

type SM = Int -> (Int, SM)

但是Haskell不允许这样做.您必须使用data或newtype引入新的命名类型:

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

下面是您应用此次要更改的程序,因此它现在可以按预期编译和运行:

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]