Nieskończone typy Haskella i moja funkcja FSM

Question

Właśnie natknąłem się na "nieskończony typ" w Haskell, kiedy próbowałem napisać skończoną maszynę stanów. Myślałem, że następuje bardzo intuicyjny:

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 

daję funkcja State aktualny stan (akumulator) i nowe zdarzenie, a funkcja stan produkuje następną funkcję państwowej wraz z nowym akumulatorem. Powtarzam, dopóki nie będę miał więcej wydarzeń.

Kompilator mówi mi:

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

Ponieważ state jest teraz typ nieskończona. Jak mogę zmienić to, aby działało?

Answer 1

Nieskończone typy, takie jak ta, sieją spustoszenie w systemie typu; nie powodują, że jest to niebezpieczne, ale powodują one wiele programów do wpisania, których tak naprawdę nie chcemy, a co za tym idzie ukrywanie błędów, i uważam, że one również bardziej utrudniają wnioskowanie typu.

Na szczęście rozwiązanie jest proste: wystarczy utworzyć opakowanie jednostkowe newtype. Deklaracje data i newtype mogą oczywiście być rekurencyjne (w przeciwnym razie nie moglibyśmy nawet zdefiniować list!); to po prostu nieopakowane typy, które nie są.

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