5

I have a question regarding Haskell that's been stumping my brain. I'm currently required to write a function that removes a string i.e. "word" from a list of strings ["hi", "today", "word", "Word", "WORD"] returns the list ["hi", "today", "Word", "WORD"]. I cannot use any higher-order functions and can only resort to primitive recursion.

Thinking about the problem, I thought maybe I could solve it by using a recursion where you search the head of the first string, if it matches "w" then compare the next head from the tail, and see if that matches "o". But then I soon realized that after all that work, you wouldn't be able to delete the complete string "word".

My question really being how do I compare a whole string in a list rather than only comparing 1 element at a time with something like: removeWord (x:xs). Is it even possible? Do I have to write a helper function to aid in the solution?

Improve this question
3
  • 2
    The fact that your list contains strings isn't really important here. Try solving the problem for e.g. list of Int first, then it should be just a matter of changing the type signature to make it work for lists of strings. Commented May 12, 2013 at 0:28
  • 4
    When you match (x:xs) against ["hi", "today", "word", "Word", "WORD"], x becomes "hi" and xs becomes ["today", "word", "Word", "WORD"]. That is, it matches string by string, not character by character. This works because you have a list of strings rather than just one big string. Commented May 12, 2013 at 0:28
  • 1
    Oh I see! Thank you so much this is where it was giving me trouble. I thought it was only the first element and not the whole word. This clears up everything! Commented May 12, 2013 at 0:44

4 Answers 4

Reset to default
3

Consider the base case: removing a word from an empty list will be the empty list. This can be trivially written like so:

removeWord [] _ = []

Now consider the case where the list is not empty. You match this with x:xs. You can use a guard to select between these two conditions:

  1. x is the word you want to remove. (x == word)
  2. x is not the word you want to remove. (otherwise)
Improve this answer
Sign up to request clarification or add additional context in comments.

4 Comments

I thought for '(x:xs)' x would only match the first element in the list, so in ["Hi", "word"], x would return H, no?
@Phirip: ["Hi", "word"] is a list of two elements. The first element is "Hi". The second element is "word". For (x:xs), x would be "Hi". You'd only get H if you used ((x:xs):ys).
Oh I see! Thank you so much this is where it was giving me trouble. I thought it was only the first element and not the whole word. This clears up everything!
@Phirip: "Hi" is the first element of ["Hi", "word"]. 'H' is the first element of "Hi". 'H' would be the first element of the first element of ["Hi", "word"], and : only goes down one level.
3

You don't need a helper function, though you could write one if you wanted to. You've basically got 3 conditions:

  1. You get an empty list.
  2. You get a list whose first element is the one you want to remove.
  3. You get a list whose first element is anything else.

In other languages, you would do this with a set of if-else statements, or with a case statement, or a cond. In Haskell, you can do this with guards:

remove_word_recursive:: String -> [String] -> [String]
remove_word_recursive _ []                              = []
remove_word_recursive test_word (x:xs) | test_word == x = what in this case?
remove_word_recursive test_word (x:xs)                  = what in default case?

Fill in the correct result for this function in these two conditions, and you should be done.

I think what you're looking for is a special case of the function sought for this question on string filters: Haskell - filter string list based on some conditions . Reading some of the discussion on the accepted answer might help you understand more of Haskell.

Improve this answer

3 Comments

Please don't spread the underscore_naming_convention, the camelCaseConvention seems to be the de-facto standard.
Ah, OK. I wasn't aware of what was standard in the Haskell community, and underscore_naming_convention is the standard across languages where I am. Is there discussion somewhere on why camelCaseConvention is superior for Haskell?
The Haskell programming guidelines form some kind of authoritative source, and the base library (with Prelude) is written using that naming convention, along with most Haskell libraries on Hackage. The underscore is usually instead reserved for function versions that discard values (i.e. mapM_ instead of _ <- mapM).
3

Since you want to remove a list element, it's easy to do it with List Comprehension. 

myList = ["hi", "today", "word", "Word", "WORD"]
[x | x <- myList, x /= "word"]

The result is:

["hi","today","Word","WORD"]
Improve this answer

Comments

1

If isInfixOf is not considered as higher order, then

import Data.List (isInfixOf)
filter  (not . isInfixOf "word")  ["hi", "today", "word", "Word", "WORD"]
Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.