haskell - 压缩遍历

Question

我有一个Traversable，里面有洞——想象一下这个二叉树:

         /       \
       /    \     Nothing
 Just 1    /  \  
    Nothing   Just 3

我还有一个值列表来填补漏洞 - [2, 4] - 结果是:

         /       \
       /    \     Just 4
 Just 1    /  \  
     Just 2   Just 3

我认为可以使用 lens 索引遍历来遍历 Nothing 并将它们替换为列表中相应索引处的值。

但是不使用索引一定可以直接做更多的事情吗？

奖励积分——这个主题的一些变化:

1. (我的用例)值列表的元素数量必须与遍历中的空洞数量完全相同。失败以也许表示。
2. 列表必须至少包含同样数量的元素，因此我们还可以传入 [2, 4, 6], [2, 4, ..]等
3. 列表可以有任意数量的元素，我们用给定的元素填充尽可能多的漏洞。此操作不会失败，它可以填补任意数量的漏洞。

Answer 1

利用mapAccumL的简单(但部分)解决方案:

import qualified Data.Traversable as T

fill :: forall a t. T.Traversable t => t (Maybe a) -> [a] -> t a
fill t fillers = snd $ T.mapAccumL go fillers t
    where
      go :: [a] -> Maybe a -> ([a], a)
      go fs     (Just x) = (fs, x)
      go (f:fs) Nothing  = (fs, f)
      go []     Nothing  = error "not enough fillers!"

完全的替代方案:

fill2 :: forall a t. T.Traversable t => 
        t (Maybe a) -> [a] -> Maybe (t a)
fill2 t fillers  = sequenceA . snd $ T.mapAccumL go fillers t
    where
      go :: [a] -> Maybe a -> ([a], Maybe a)
      go (f:fs) Nothing  = (fs, Just f)
      go fs     x        = (fs, x)