Haskell infiniti tipi e la mia funzione FSM

Question

Ho appena incontrato il "tipo infinito" in Haskell mentre stavo tentando di scrivere una macchina a stati finiti. Ho pensato che il seguente è stato molto intuitivo:

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 

rendo la funzione di stato allo stato attuale (l'accumulatore) e il nuovo evento, e la funzione stato produce la funzione stato successivo insieme al nuovo accumulatore. Ricevo fino a quando non ho più eventi.

Il compilatore mi dice:

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

Perché state è ora un tipo di infinito. Come riorganizzare questo per farlo funzionare?

Answer 1

I tipi infiniti come questo causano il caos con il sistema di tipi; non lo rendono pericoloso, ma causano una grande quantità di programmi da digitare che in realtà non si desidera, nascondendo così gli errori, e credo che rendano anche più difficile l'inferenza di tipo.

Per fortuna, la soluzione è semplice: devi solo creare un wrapper newtype. Le dichiarazioni data e newtype sono ovviamente consentite per essere ricorsive (altrimenti, non potremmo nemmeno definire le liste!); sono tipi semplici, non confezionati che non lo sono.

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