CODEWITHSUNDEEP
haskell
Clare93
Clare93

Reputation: 41

Haskell filter string with only the first occuring Char

I want to filter a string with a string. What I want is to use delete every first occurring char.

myFunc :: String -> String -> String

Like: 

myFunc "dddog" "bigdddddog" = "biddg"

In "dddog": 3x d, 1x o, 1x g

In the second string it removed 3x d, 1x o and 1x g So the output: biddg

I can't use filter for it, because it will delete all occurring chars. And I struggled a long time with it.

Thanks in advance:)

Upvotes: 3

Views: 1496

Answers (7)

augustss
augustss

Reputation: 23014

How about

Prelude> :m +Data.List
Prelude Data.List> "bigdddddog" \\ "dddog"
"biddg"

Upvotes: 11

Will Ness
Will Ness

Reputation: 71065

Using predefined functions from 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])

Testing:

Prelude Data.List> myFunc "dddog" "bigdddddog"
"biddg"

edit: this is of course a bit more complex than (\\). I'll let it stand as an illustration. There could be some merit to it still, as it doesn't copy the 2nd (longer?) string over and over, for each non-matching character from the 1st (shorter) string, as delete apparently does, used in (\\) = foldl (flip delete).

Upvotes: 0

Ankur
Ankur

Reputation: 33637

No monadic solution yet, there you go:

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

Upvotes: 1

Jake
Jake

Reputation: 757

some of the other solutions don't seem to produce the same result you posted. I think I have a simple solution that does what you asked for but I may be misunderstanding what you want. All I do in the following code is go though the list and apply 'delete' to every element in the list. It's not exactly efficient but it gets the job done.

import Data.List

myFunc (x:xs) ys = myFunc xs (delete x ys)
myFunc []     ys = ys

There are perhaps more efficient solutions like storing the "to remove" list in a tree with the number of occurences stored as the value then traversing the main list testing to see if the count at that key was still greater than zero. I think that would give you O(n*lg(m)) (where n is the size of the list to be removed from and m is the size of the "to remove" list) rather than O(n*m) as is the case above. This version could also be maid to be lazy I think.

edit:

Here is the tree version I was talking abut using Data.Map. It's a bit complex but should be more efficient for large lists and it is somewhat lazy

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' _ []          = []

Upvotes: 2

גלעד ברקן
גלעד ברקן

Reputation: 23955

I like kaan's elegant solution. In case you meant this...here's one where the "ddd" would only be removed if matched as a whole:

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

Output:

*Main> f "dddog" "bigdddddog"
"biddg"

*Main> f "dddog" "bdigdogd"
"bdidgd"

Upvotes: 1

kaan
kaan

Reputation: 796

Not the nicest solution, but you can understand easier what's going on:

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

As you commented, you want to use guards. Do you mean this?

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

Upvotes: 4

Boris
Boris

Reputation: 5176

I am not quite sure about how you want your function to behave, how about this?

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

This gives the following output in GHCi:

> myFunc "dddog" "bigdddddog" 
> "bigdd"

If this is not what you had in mind, please give another input/output example.

Upvotes: 1

Related Questions