Haskell无限类型

Question

我正在努力让下面的代码工作.它是一个有限状态机,我传入一个函数作为下一个状态.调用该函数r并返回结果列表+下一个函数作为下一个状态.继续调用直到列表用完,并返回结果的串联.monad是一个错误monad,允许我在需要时抛出错误.

fsm f []     = return []
fsm f (r:rs) = do
    (xs, f') <- f r
    rest     <- fsm f' rs
    return $ xs ++ rest

错误是:

Occurs check: cannot construct the infinite type: t1 = t0 -> m0 ([a0], t1)
In the first argument of `fsm', namely f'

我之前看过无限类型错误,我理解它的方法是用a包装一个类型newtype.但我无法弄清楚如何完成这项工作.

有人能指出洞察力吗？

Answer 1

我想这就是你想要的:

newtype F m = F { unF :: String -> m ([String], F m) }

fsm :: (Monad m) => F m -> [String] -> m [String]
fsm f []     = return []
fsm f (r:rs) = do
    (xs, f') <- unF f r
    rest     <- fsm f' rs
    return $ xs ++ rest

你是正确的,你需要使用data或newtype任何时候你想要一个递归类型.

在回复您的评论时,以下是如何实现您的dup功能:

dup :: (Monad m) => F m
dup = F dup' where dup' xs = return ([xs, xs], F dup')

...或者如果您愿意,可以将其拆分为两个单独的定义.

请注意,如果您不确定类型签名应该是什么,只需启用NoMonomorphismRestriction扩展名,编译器就不会抱怨并正确推断出顶级类型.