為了舉例，讓我們定義一個玩具自動機型別：
data Automaton =
Auto
{ success ::
Automaton
, failure ::
Automaton
}
這種結構被設計成回圈的，我們可以把每Automaton一個都想象成一個狀態隨著成功和失敗而轉換到其他狀態。所以有限自動機必須遞回定義。例如這里是最簡單的自動機：
sink =
Auto sink sink
它由 1 個總是轉換到自身的狀態組成。如果我們愿意，我們可以制作更復雜的自動機：
-- Transitions to a sink once it encounters a failure
otto1 =
Auto otto1 sink
-- Mutually recursive automata
otto2 =
Auto otto2 otto3
otto3 =
Auto otto3 otto2
這些很好。但是接受用戶輸入并構建自動機可能會很好。例如，可以從轉換矩陣中構建一個。這是一個簡單的實作：
fromTransition :: [(Int, Int)] -> Automaton
fromTransition tMatrix =
go 0
where
go n =
let
(succ, fail) =
tMatrix !! n
in
Auto (go succ) (go fail)
但是，當我們嘗試這樣做時，就會出現問題。我們之前的示例O(1)將遵循過渡。然而，由此產生的自動機O(n)將遵循轉換，因為除非快取，每次我們進行轉換時都必須對串列進行索引。此外，只要這個自動機存在，輸入串列就必須保存在記憶體中。使這基本上比使用轉移矩陣作為自動機更糟糕。
我真正喜歡的是使用該方法動態構建的自動機與前面顯示的靜態構建的自動機一樣高效。我想要某種方法來分析輸入，構建一個自動機，然后釋放輸入。
在具有變異的語言中，這很容易做到，因為我們可以一點一點地創建結構，留下漏洞以便以后更正。
我也真的不想拖IO進來，因為一旦引入它就無法包含在內。
有沒有像我想要的那樣動態分配回圈結構的好方法？
uj5u.com熱心網友回復：
懶惰救人。我們可以遞回地定義所有子自動機的串列，以便它們的轉換索引到同一個串列中：
fromTransition :: [(Int, Int)] -> Automaton
fromTransition m = a !! 0 where
a = map (\(succ,fail) -> Auto (a !! succ) (a !! fail)) m
在所有轉換至少遍歷一次之后，生成的自動機將是您期望的回圈圖，沒有任何對矩陣的參考（特別是，轉換將在恒定時間內進行）。
我們還可以使用 提前強制自動機seq。
fromTransition :: [(Int, Int)] -> Automaton
fromTransition m = forced `seq` (a !! 0) where
a = map (\(succ,fail) -> Auto (a !! succ) (a !! fail)) m
forced = foldr (\(Auto x y) r -> x `seq` y `seq` r) () a
轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/392567.html
上一篇：Haskell-用foldr計數