How do you filter a list of strings by a string in haskell?

Question

I have a string containing letters I want to be sure are in the words in the list. Running it however results in it still leaving behind words that contain the undesired letters.

Here's my function:

import Data.List    

filterWords :: String -> [String]
filterWords str =
  let strs      = words str
      letters   = concat . words . nub $ "poultry outwits ants"
      predicate = dropWhile (`elem` letters) ['a' .. 'z']
  in  dropWhile (any (`elem` predicate)) strs

What do I need to change to make this work?

To make it clear, I want to filter away any words that contain letters not in "poultry outwits ants", meaning a word like "years" would be dropped because despite containing 'y', 'a', 'r', and 's' which all satisfy the predicate, it also contains 'e' which doesn't.

I don't understand the task - you want to drop all those words which contain none of the letters in "poultry outwits ants"? — Frerich Raabe
– Frerich Raabe, Commented Feb 18, 2015 at 9:07
@FrerichRaabe that contain none of the letters yes, but I mean extended to something like "years" being filtered away as well because it contains 'e' — Electric Coffee
– Electric Coffee, Commented Feb 18, 2015 at 9:07
It's funny, coming back to this five years later, and I honestly don't remember ever making this post or what the original context for this was.... — Electric Coffee
– Electric Coffee, Commented Aug 14, 2020 at 9:02

Frerich Raabe · Accepted Answer · 2015-02-18 13:17:45Z

4

A good way to filter a list of things (e.g. words) is to use the filter function. What you need to provide is a predicate which tells whether a string should be included or not. You commented that you want to include those strings which consists of letters in "poultry outwits ants", so that would be

filterWords :: String -> [String]
filterWords str = filter acceptableWord (words str)
  where
    acceptableWord = all (`elem` "poultry outwits ants")

Now, in another comment you wrote that

Some of the words I get have more copies of the same letter than there are in the original.

So I suspect what you really want is to figure out which words can be formed out of the letters in "poultry outwits ants".

To do this, you could count how often each character appears in the given word (and in the mgic string poultry outwits ants) and then verify that not only each letter in the word appears in the magic string but also that the letter doesn't appear more often than in the magic string.

I'd start by defining a function which calculates 'character frequency table', i.e. it counts how often each character occurs in the given string:

freq :: String -> [(Char, Int)]
freq = map (\s -> (head s, length s)) . group . sort

Furthermore, I'd define a function which tells whether one frequency table x is a "subset" of another table y, i.e. it verifies that each character in x also appears in y, but it doesn't occur more often:

subset :: [(Char, Int)] -> [(Char, Int)] -> Bool
subset x y = all f x
  where
    f (ch, occ) = case lookup ch y of
                      Just occ' -> occ <= occ'
                      Nothing   -> False

You can then use this to define acceptableWord such that it only accepts words whose frequency table is a subset of the frequency table of the magic string, so we get:

filterWords :: String -> [String]
filterWords str = filter acceptableWord (words str)
  where
    acceptableWord w = subset (freq w) (freq "poultry outwits ants")

edited Feb 18, 2015 at 13:17

answered Feb 18, 2015 at 9:11

Frerich Raabe

95.2k20 gold badges127 silver badges216 bronze badges

Sign up to request clarification or add additional context in comments.

6 Comments

Electric Coffee Over a year ago

I tried to think of a way to use filter, but couldn't wrap my head around it... Guess the solution was too simple... Thanks!

Frerich Raabe Over a year ago

It you want to be a Haskell hipster you could make it point-free, shortening the definition to filterWords = filter (all (`elem` "poultry outwits ants")) . words. Actually, now that I see it - it still looks fairly comprehensible IMHO!

Electric Coffee Over a year ago

I actually did... Now to filter away stuff that doesn't fit the number of letters...

Frerich Raabe Over a year ago

What does doesn't fit the number of letters mean?

Electric Coffee Over a year ago

Some of the words I get have more copies of the same letter than there are in the original

|

Collectives™ on Stack Overflow

How do you filter a list of strings by a string in haskell?

1 Answer 1

6 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

6 Comments

Your Answer

Sign up or log in

Post as a guest

Related