Haskell/解決方案/可遍歷

← 返回可遍歷

為遍歷而生的函子

1.

instance Traversable Tree where
    traverse f t = case t of
        Leaf x       -> Leaf <$> f x
        Branch tl tr -> Branch <$> traverse f tl <*> traverse f tr

Traversable 的解釋

1.

transpose :: [[a]] -> [[a]]
transpose = getZipList . traverse ZipList

請注意，這個 transpose 的行為與 Data.List 中的 transpose 不同。當給定大小不一致的行時，後者會很樂意組裝大小不一致的列，而我們的版本會截斷多餘的元素。這兩種解決方案都不是很好，但巢狀列表本身就不是矩陣的好表示方法。

2.

traverse mappend :: (Traversable t, Monoid b) => t b -> b -> t b

traverse mappend t 是一個 (Traversable t, Monoid b) => b -> t b 函式，它將它的引數單子地追加到 t 中的所有值。相關的 Applicative 例項是函式的例項。

3.

這是 mapAccumL 的型別

mapAccumL :: Traversable t 
          =>‌ (a -> b -> (a, c)) -> a -> t b -> (a, t c)

經過幾次翻轉，型別變成了...

(b -> (a -> (a, c))) -> t b -> (a -> (a, t c))

... 等同於

(b -> State a c) -> t b -> State a (t c)

這強烈表明我們可以使用 State 應用函子將 mapAccumL 寫成一個遍歷。要考慮的一個重要問題是 State 的應用函子例項如何排序效果（因為 State 不是 可交換的）。由於我們知道庫中的例項從左到右排序，所以我們可以繼續（否則，我們將不得不使用 Control.Applicative.Backwards 來避免最終得到 mapAccumR）。

-- Using a different name because of the flips.
mapAccumLS :: (b -> State a c) -> t b -> State a (t c)
mapAccumLS step t = traverse step t -- i.e. mapAccumLS = traverse

.. 這就是全部。只需要撤銷翻轉，並新增 state/runState 樣板程式碼即可。

mapAccumL :: Traversable t 
          =>‌ (a -> b -> (a, c)) -> a -> t b -> (a, t c)
mapAccumL step z t = runState (traverse (state . flip step) t) z

這就像 Data.Traversable 中的實際實現一樣。唯一的區別是 Data.Traversable 使用了 State 的內部實現來避免匯入 Control.Monad.Trans.State（實際上是 兩個 實現，這要歸功於效果排序問題）。