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"
About these ads

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”

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

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

WordPress.com Logo

You are commenting using your WordPress.com 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 )

Google+ photo

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

Connecting to %s


Follow

Get every new post delivered to your Inbox.

Join 35 other followers

%d bloggers like this: