連結串列

說明

你的團隊決定用雙向鏈結串列來表示時刻表上的每一條火車路線。火車路線上每一站，都會用鏈結串列中的一個節點來表示。

你不需要煩惱各站的抵達和出發時間。每一站單純用一個數字來表示就好。

路線可以延伸，在路線的開頭或結尾加入車站。路線也可以縮短，把開頭或結尾的車站移除。

有時候某個車站會關閉，這時就必須把這個車站從路線中移除，即使它不在路線的開頭或結尾也一樣。

路線的大小不是用火車行駛的距離來衡量，而是看它停靠幾站。

有狀態的資料結構

在 Lean 等函式語言中，大多數的值在設計上都是不可變的。這表示更新通常是透過產生一個新的值來完成，而舊值與新值會同時存在，兩者都可以被參照和使用。

不過，在許多情況下，我們會需要、甚至必須使用有狀態的值。有狀態的值是透過變動來更新，也就是取代舊值，而不是產生一個新值。變動之後，只有更新過的值還能被存取。

請注意，變動可能會破壞語言的一些保證。純函式對於同一組輸入必須永遠回傳相同的結果，但如果某個輸入可能會隨時間改變，那麼即使以相同的引數呼叫，函式也可能回傳不同的結果。同樣地，如果一個函式除了回傳結果之外還會造成外部變更，或是能從參數以外的來源讀取資料，那麼對同一個函式的兩次呼叫可能會有不同、有時甚至無法預測的結果。

為了處理這類有狀態的行為，Lean 和其他函式語言一樣，要求帶有效應的函式必須包裝在一種特殊的結構中，以便與純函式區分開來。這類結構稱為 monad。

必須注意的是，雖然每個有狀態的值都存在於某個帶有效應的 monad 之中，但並非每個 monad 都代表可變狀態。「純」monad 的著名例子包括 Option、Except 和 Id。

在這個練習中，你將會定義一個稱為LinkedList的有狀態資料結構。這種資料結構的實例是透過變動來更新的。

為了支援這一點，所有函式都包裝在ST monad 裡面。在這個 monad 中，可變狀態是唯一的副作用，而且可變參考無法逃逸。如果想了解更多資訊，可以參閱參考文件。