Haskell filter string with only the first occuring Char

Question

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

Shouldn't the output be "biddg"? Or am I misunderstanding? With your output it looks like you deleted the first 4 ds, the first o, and the second g. — Jeff Burka, Jul 15 '13 at 21:16
If you have `myFunc :: String -> String -> String`, what is the result of `myFunc s1 s2` for any two Strings? Are you simply removing all of `s1` from the end of `s2`? — Code-Apprentice, Jul 15 '13 at 21:20
Note that I have given the function a name. I suggest that you edit your question similarly since it will help clarify what you are asking. — Code-Apprentice, Jul 15 '13 at 21:22
yeah what i want is to use the chars from s1 to remove the chars from s2. — Clare93, Jul 15 '13 at 21:23
In your question, you give two different outputs for `myFunc "dddog" "bigdddddog"`, `"biddg"` and `"bigd"` - which I suppose is meant to be `"bigdd"`. Which one do you mean? — Boris, Jul 15 '13 at 21:54
@Clare93 you're supposed to accept one of the answers, one that was the most helpful for you. — Will Ness, Jul 19 '13 at 19:29

score 11 · Answer 1 · edited Jul 16 '13 at 09:52

11

How about

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

edited Jul 16 '13 at 09:52

Will Ness

70,110
9
98
181

answered Jul 15 '13 at 22:53

augustss

22,884
5
56
93

Nice many thanks to you and other people who tried to help me:) i didn't think it would be so simple. – Clare93 Jul 15 '13 at 23:04

kaan · Answer 2 · 2013-07-15T23:01:13.167

4

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

edited Jul 15 '13 at 23:01

answered Jul 15 '13 at 21:43

kaan

796
2
6
20

uh? where did your comment go? strange – kaan Jul 15 '13 at 23:05
your `remove` is actually equivalent to `Data.List.delete`, and the recursion pattern of `myfunc` amounts to `myfunc = flip (foldl (flip remove))` which is how `Data.List.(\\)` is defined, [apparently](http://www.haskell.org/ghc/docs/latest/html/libraries/base/src/Data-List.html#%5C%5C). :) IOW, `myfunc == flip Data.List.(\\)`. – Will Ness Jul 16 '13 at 09:47
Yeah it wasn't necessary anymore because i made a working function with guards later on so i deleted my comment. But thnx anyway for your help! :) – Clare93 Jul 16 '13 at 09:51

Jake · Answer 3 · 2013-07-16T02:51:04.693

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

Boris · Answer 4 · 2013-07-15T21:49:41.827

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.

score 1 · Answer 5 · answered Jul 16 '13 at 02:42

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"

score 1 · Answer 6 · answered Jul 16 '13 at 05:10

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

Will Ness · Answer 7 · 2013-07-16T09:37:28.270

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

Haskell filter string with only the first occuring Char

7 Answers7