Programming Praxis – Remove characters from a string

In today’s Programming Praxis exercise, our task is to remove all the characters in one string from the other. Let’s get started, shall we?

Since this exercise doesn’t mention any performance requirements, we’ll go with the short but naive version, which is O(m * n). If the strings used get larger, you’ll probably want to use different datastructures to have more efficient membership testing, such as a hastable which reduces the complexity to O(m).

remove :: Eq a => [a] -> [a] -> [a]
remove = filter . flip notElem

A quick test to see if it’s working properly:

main = print $ remove "aeiou" "Bonsai Code"

Tags: , , , , , , , , ,

2 Responses to “Programming Praxis – Remove characters from a string”

  1. Chris Says:

    Hi Remco,

    could you explain how the code works. “filter” needs to be passed a function, but in your code it seems you compose filter with a function?

    And why do i get an error if i enter the code directly in ghci:

    > let entferne = filter . flip notElem
    > entferne “aeiou” “Bonsai Code”

    Couldn’t match expected type `()’ with actual type `Char’
    Expected type: [()]
    Actual type: [Char]
    In the first argument of `entferne’, namely `”aeiou”‘
    In the expression: entferne “aeiou” “Bonsai Code”

    Thanks, Chris

  2. Remco Niemeijer Says:

    It appears that unlike replying to Github email notifications WordPress doesn’t automatically post your reply as a new comment, so I’ll copy my reply to Chris here in case anyone else is interested:

    As for the code not working in ghci: It appears that ghci applies monomorphism restriction to function definitions that have no explicit arguments. You can prevent this by either explicitly defining the function signature as follows:

    let remove = filter . notElem :: (Eq a) => [a] -> [a] -> [a]

    or, probably more convenient, just turn off monomorphism restriction like so:

    :set -XNoMonomorphismRestriction

    after which you can define the function as expected.

    As for how it works:

    The definition of (.) is as follows:
    f . g = \x -> f (g x)

    This gives
    remove = \x -> filter ((flip notElem) x)

    Next, we remove the partial application in the filter predicate:
    remove = \x -> filter (\y -> (flip notElem) x y)

    flip f x y = f y x

    We get
    remove = \x -> filter (\y -> notElem y x)

    Let’s do some more cleanup:
    remove x = filter (\y -> notElem y x)
    remove pattern = filter (\element -> notElem element pattern)
    remove pattern from = filter (\element -> notElem element pattern) from

    As you can see, filter does indeed take a function as its first argument.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: