Các loại vô hạn Haskell và chức năng FSM của tôi

Question

Tôi vừa mới bắt gặp "loại vô hạn" trong Haskell khi tôi đang cố viết một máy trạng thái hữu hạn. Tôi nghĩ những điều sau đây là rất trực quan:

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 

tôi cung cấp cho các chức năng nhà nước hiện trạng (accumulator) và sự kiện mới, và các chức năng nhà nước tạo ra các chức năng nhà nước tiếp theo cùng với accumulator mới. Tôi chấp nhận cho đến khi tôi không còn sự kiện nữa.

Trình biên dịch nói với tôi:

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

Vì state hiện nay là một loại vô hạn. Làm thế nào để tôi sắp xếp lại điều này để làm cho nó hoạt động?

Answer 1

Các loại vô hạn như thế này sẽ tàn phá với hệ thống kiểu; họ không làm cho nó không an toàn, nhưng chúng gây ra rất nhiều chương trình để gõ mà bạn không thực sự muốn, do đó ẩn lỗi, và tôi tin rằng họ làm cho suy luận kiểu khó hơn.

Rất may, giải pháp rất đơn giản: bạn chỉ cần tạo một bao bì newtype. Tất cả các khai báo data và newtype đều được phép đệ quy (nếu không, chúng tôi thậm chí không thể xác định danh sách!); nó chỉ đơn giản, chưa được loại mà không phải.

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