可穿越結構作為具有內容的形狀

如果型別 tTraversable 那麼 t a 的值可以分成兩部分:它們的形狀和它們的內容

data Traversed t a = Traversed { shape::t (), contents :: [a] }

其中內容與使用 Foldable 例項訪問的內容相同。

朝著一個方向,從 t aTraversed t a 除了 FunctorFoldable 之外不需要任何東西

break :: (Functor t, Foldable t) => t a -> Traversed t a 
break ta = Traversed (fmap (const ()) ta) (toList ta)

但回去使用 traverse 功能至關重要

import Control.Monad.State

-- invariant: state is non-empty
pop::State [a] a
pop = state $ \(a:as) -> (a, as)

recombine::Traversable t => Traversed t a -> t a
recombine (Traversed s c) = evalState (traverse (const pop) s) c

Traversable 法則要求 break . recombinerecombine . break 都是同一性。值得注意的是,這意味著在 contents 中有完全正確的數字元素來完全填充 shape 而沒有剩餘。

Traversed t 本身就是 Traversabletraverse 的實現通過使用列表的 Traversable 例項訪問元素然後將惰性形狀重新附加到結果來工作。

instance Traversable (Traversed t) where
    traverse f (Traversed s c) = fmap (Traversed s) (traverse f c)