haskell - Haskell 中的状态机模式 : infinite type error

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]

不幸的是， a 的类型和 b是无限的，GHC 提示:
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]