ビュンと全検索

Question

私はそれの穴にTraversableを持っている - このバイナリーツリー想像：

： - - [2, 4]その結果、私はまたして穴を埋めるために値のリストを持っている

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

を

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

lensインデックス付きトラバーサルを使用してNothingにトラバースし、リストの対応するインデックスの値に置き換えることが可能だと思います。

しかし、インデックスを使わずに直接行うことは可能でしょうか？

ボーナスポイント - このテーマには、いくつかのバリエーション：

1. （私のユースケース）値のリストは、トラバーサルの穴などの要素の正確同じ番号を持つ必要があります。失敗はMaybeと表示されます。
3. など、リストは少なくともなど、多くの要素を持っている必要がありますので、我々はまた、[2, 4, 6]に合格している可能性があり、[2, 4, ..]リストは、任意の数の要素を持つことができ、我々ができるよう、私たちは、できるだけ多くの穴を埋めます与えられた要素この操作は失敗しません。任意の数の穴を埋めることができます。

Answer 1

要素が不足している場合はLeftを返します。

あなたはStateモナドでTraversableのmapM使って穴を埋めることができます。

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" 

Answer 2

A 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) 

Answer 3

はコンパクト一つだ：

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