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（实际上是 两个 实现，这要归功于效果排序问题）。