ハスケルの無限型と私のFSM関数

Question

有限状態機械を書くときに、ハスケルの "無限型"に遭遇しました。私は次のように非常に直感的だと思った：

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