正在壓縮遍歷

我有它孔Traversable - 想象一下二叉樹：正在壓縮遍歷

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

我也有值的列表，以填補漏洞 - [2, 4] - 導致：

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

我認爲可以使用lens索引遍歷遍歷到Nothings，並將它們替換爲列表中相應索引處的值。

但是，如果不使用索引，可以直接做更多的事情嗎？

獎勵積分 - 關於這一主題的幾個變化：

（我的使用情況）值的列表必須完全相同相同數量的元素作爲遍歷漏洞。失敗以Maybe表示。
名單必須至少儘可能多的元素，所以我們也可以通過在[2, 4, 6]，[2, 4, ..]等
列表可以有任意數量的元素，並填寫儘可能多的孔，我們可以用我們得到的元素。該操作不會失敗，它可以填充任意數量的孔。

來源

2016-07-29 Joel Burget

這是一個版本，如果沒有足夠的元素，返回Left。

您可以填寫使用的mapMTraversable孔在State單子：

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"

如果你想確保所有元素都被使用，改變fill到：

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"

來源

2016-07-29 15:33:53 ErikR

一簡單（但部分）解決方案利用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)

來源

2016-07-29 16:50:04 chi

這裏的一個緊湊之一：

fill :: Traversable t => t (Maybe a) -> [a] -> Maybe (t a) 
fill = evalStateT . traverse foo where 
    foo x = maybe empty pure x <|> StateT uncons

來源

2016-07-30 01:21:34 Gurkenglas

正在壓縮遍歷

回答

相關問題