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包装器.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