Zipping Traversals

Question

I have a Traversable with holes in it -- imagine this binary tree:

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

I also have a list of values to fill the holes with -- [2, 4] -- resulting in:

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

I think it's possible to use a lens indexed traversal to traverse to the Nothings and replace them with the value at the corresponding index from the list.

But it must be possible to do more directly without using indices?

Bonus points -- a few variations on this theme:

1. (my use case) The list of values must have exactly the same number of elements as holes in the traversal. Failure indicated with a Maybe.
2. The list must have at least as many elements, so we could have also passed in [2, 4, 6], [2, 4, ..], etc.
3. The list can have any number of elements, and we fill as many holes as we can with the elements we're given. This operation can't fail, it can just fill any number of holes.

Answer 1

A simple (but partial) solution exploiting 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!"

A total alternative:

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)

Answer 2

Here's a version which returns a Left if there are not enough elements.

You can fill the holes using Traversable's mapM in the State monad:

 import qualified Data.Traversable as T
 import Control.Monad.State.Strict
 import Control.Error

 import qualified Data.Tree as Tree
 import Data.Tree (Tree(..))

 visit :: Maybe a -> ExceptT String (State [a]) a
 visit (Just x) = return x
 visit Nothing = do xs <- lift get
                    case xs of
                      (a:as) -> do lift (put as); return a
                      []     -> throwE "out of elements"

 fill :: T.Traversable t => t (Maybe a) -> [a] -> Either String (t a)
 fill t vals  = evalState (runExceptT (T.mapM visit t) ) vals

 tree = Node Nothing [ Node (Just "2") [], Node Nothing [] ]

 ex1 =  print $ fill tree ["a", "b", "c", "d" ] -- Right ...
 ex2 =  print $ fill tree ["a" ]                -- Left "out of elements"

If you want to make sure all the elements are used, change fill to:

fill :: T.Traversable t => t (Maybe a) -> [a] -> Either String (t a)
fill t vals = evalState (runExceptT doit) vals
  where doit = do t' <- T.mapM visit t
                  xs <- lift get
                  case xs of
                    [] -> return t'
                    _  -> throwE "not all elements were used"