我想用一个字符串过滤一个字符串。我想要的是使用删除每个第一个出现的字符。
myFunc :: String -> String -> String
喜欢：
myFunc "dddog" "bigdddddog" = "biddg"
在"dddog": 3x d, 1x o, 1x g
在第二个字符串中，它删除了 3x d、1x o 和 1x g 所以输出：biddg
我不能使用过滤器，因为它会删除所有出现的字符。我挣扎了很长时间。
提前致谢：）
问问题
1340 次
7 回答
11
怎么样
Prelude> :m +Data.List
Prelude Data.List> "bigdddddog" \\ "dddog"
"biddg"
于 2013-07-15T22:53:54.883 回答
4
不是最好的解决方案，但您可以更容易地理解发生了什么：
myfunc :: String -> String -> String
myfunc [] xs = xs
myfunc (x:xs) ys = myfunc xs $ remove x ys
where
remove _ [] = []
remove x (y:ys) = if x == y then ys else y : remove x ys
正如您评论的那样，您想使用警卫。你是这个意思吗？
myfunc :: String -> String -> String
myfunc [] xs = xs
myfunc (x:xs) ys = myfunc xs $ remove x ys
remove :: Char -> String -> String
remove _ [] = []
remove x (y:ys)
| x == y = ys
| otherwise = y : remove x ys
于 2013-07-15T21:43:08.443 回答
2
其他一些解决方案似乎不会产生您发布的相同结果。我想我有一个简单的解决方案可以满足您的要求，但我可能会误解您想要的。我在以下代码中所做的只是遍历列表并将“删除”应用于列表中的每个元素。它并不完全有效，但可以完成工作。
import Data.List
myFunc (x:xs) ys = myFunc xs (delete x ys)
myFunc [] ys = ys
可能有更有效的解决方案，例如将“要删除”列表存储在树中，并将出现次数存储为值，然后遍历主列表测试以查看该键处的计数是否仍大于零。我认为这会给你 O(n*lg(m)) （其中 n 是要从中删除的列表的大小，m 是“要删除”列表的大小）而不是 O(n*m)是上面的情况。我想这个版本也可以是懒惰的女仆。
编辑：
这是我正在谈论的使用 Data.Map 的树版本。它有点复杂，但对于大型列表应该更有效，而且有点懒惰
myFunc l ys = myFunc' (makeCount l) ys
where makeCount xs = foldr increment (Map.fromList []) xs
increment x a = Map.insertWith (+) x 1 a
decrement x a = Map.insertWith (flip (-)) x 1 a
getCount x a = case Map.lookup x a of
Just c -> c
Nothing -> 0
myFunc' counts (x:xs) = if (getCount x counts) > 0
then myFunc' (decrement x counts) xs
else x : myFunc' counts xs
myFunc' _ [] = []
于 2013-07-16T02:12:25.733 回答
1
我不太确定你希望你的函数如何表现，这个怎么样？
import Data.List (isPrefixOf)
myFunc :: String -> String -> String
myFunc _ [] = []
myFunc y x'@(x:xs) | y `isPrefixOf` x' = drop (length y) x'
| otherwise = x : myFilter xs y
这在 GHCi 中给出了以下输出：
> myFunc "dddog" "bigdddddog"
> "bigdd"
如果这不是您的想法，请给出另一个输入/输出示例。
于 2013-07-15T21:41:54.407 回答
1
我喜欢 kaan 优雅的解决方案。如果你的意思是这个......这是一个只有在整体匹配时才会删除“ddd”的地方：
import Data.List (group,isPrefixOf,delete)
f needles str = g (group needles) str where
g needles [] = []
g needles xxs@(x:xs)
| null needle' = [x] ++ g needles xs
| otherwise = let needle = head needle'
in g (delete needle needles) (drop (length needle) xxs)
where needle' = dropWhile (not . flip isPrefixOf xxs) needles
输出：
*Main> f "dddog" "bigdddddog"
"biddg"
*Main> f "dddog" "bdigdogd"
"bdidgd"
于 2013-07-16T02:42:29.670 回答
1
还没有一元的解决方案，你去：
import Control.Monad.State
myFunc :: String -> State String String
myFunc [] = return ""
myFunc (x:xs) = get >>= f where
f [] = return (x:xs)
f (y:ys) = if y == x then put ys >> myFunc xs
else myFunc xs >>= return . (x:)
main = do
let (a,b) = runState (myFunc "bigdddddog") "dddog" in
putStr a
于 2013-07-16T05:10:58.583 回答
0
使用 Data.List 中的预定义函数，
-- mapAccumL :: (acc -> x -> (acc, y)) -> acc -> [x] -> (acc, [y])
-- lookup :: (Eq a) => a -> [(a, b)] -> Maybe b
{-# LANGUAGE PatternGuards #-}
import Data.List
picks [] = [] -- http://stackoverflow.com/a/9889702/849891
picks (x:xs) = (x,xs) : [ (y,x:ys) | (y,ys) <- picks xs]
myFunc a b = concat . snd $ mapAccumL f (picks a) b
where
f acc x | Just r <- lookup x acc = (picks r,[])
f acc x = (acc,[x])
测试：
Prelude Data.List> myFunc "dddog" "bigdddddog"
"biddg"
编辑：这当然比(\\). 我让它作为一个例子。它仍然可能有一些优点，因为它不会一遍又一遍地复制第二个（更长的？）字符串，对于来自第一个（较短）字符串的每个不匹配字符，delete显然在(\\) = foldl (flip delete).
于 2013-07-15T21:58:01.593 回答