Haskell 无限类型和我的 FSM 函数

Question

当我尝试编写有限状态机时，我刚刚在 Haskell 中遇到了“无限类型”。我认为以下内容非常直观:

fsm []     _     acc = Right acc
fsm (x:xs) state acc =
    case state acc x of
        Left err     -> Left err
        Right (s, a) -> fsm xs s a

我给状态函数当前状态(累加器)和新事件，状态函数产生下一个状态函数和新累加器。我递归，直到我没有更多的事件。

编译器告诉我:

Occurs check: cannot construct the infinite type:
  t1 = b0 -> t0 -> Either a0 (t1, b0)
In the second argument of `fsm', namely `s'

因为 state现在是无限类型。我如何重新排列它以使其工作？

Answer 1

像这样的无限类型对类型系统造成了严重破坏；它们不会使它变得不安全，但它们会导致大量程序键入您并不真正想要的类型，从而隐藏错误，而且我相信它们也会使类型推断变得更加困难。

值得庆幸的是，解决方案很简单:您只需要制作一个 newtype wrapper 。 data和 newtype声明当然是允许递归的(否则，我们甚至无法定义列表!)；它只是普通的、未包装的类型。

newtype FSMState err acc ev =
    FSMState { stepFSM :: acc -> ev -> Either err (FSMState err acc ev, acc) }

fsm :: [ev] -> FSMState err acc ev -> acc -> Either err acc
fsm []     _     acc = Right acc
fsm (x:xs) state acc =
    case stepFSM state acc x of
        Left err     -> Left err
        Right (s, a) -> fsm xs s a