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 Nothing
s 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:
Maybe
.[2, 4, 6]
, [2, 4, ..]
, etc.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)
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"
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With