如何在Haskell中通过字符串过滤一个字符串列表？

Question

我有一个字符串，其中包含我希望确保在列表中的单词中存在的字母。然而，运行它会导致仍然留下包含不想要字母的单词。

这是我的函数：

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

我需要改变什么才能使这个工作？

为了清楚起见，我想过滤掉任何包含不是 "poultry outwits ants" 中字母的单词，这意味着像 "years" 这样的单词将被删除，因为尽管它包含满足谓词的 'y'、'a'、'r' 和 's'，但它也包含不符合谓词的 'e'。

- Electric Coffee

---

我不理解这个任务 - 你想要删除所有不包含“poultry outwits ants”中任何一个字母的单词吗？ - Frerich Raabe

@FrerichRaabe，这里指的不是包含字母“yes”的内容，而是类似“years”这样的单词也被过滤掉了，因为它包含字母“e”。 - Electric Coffee

你真的想要 letters :: Data.Set Char，而不是一个列表吗？ - Bartek Banachewicz

回到这里已经五年了，真的不记得我曾经发过这篇帖子，也不知道当时的背景是什么，感觉很有趣。 - Electric Coffee

Answer 1

过滤列表（例如单词）的好方法是使用 filter 函数。您需要提供一个谓词，告诉它哪些字符串应该包含在内。您评论说想要包括那些由字母组成的字符串 "poultry outwits ants"，那么就可以这样做：

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

现在，根据你在另一条评论中的写法：

“有些单词中相同字母的数量比原始单词中的数量多。”

因此，我怀疑你实际上想知道哪些单词可以由“poultry outwits ants”中的字母组成。

为了做到这一点，您可以计算给定单词（以及mgic字符串“poultry outwits ants”）中每个字符出现的频率，然后验证不仅单词中的每个字母都出现在魔术字符串中，而且该字母在魔术字符串中出现的次数也不超过单词中的次数。

我建议首先定义一个函数来计算“字符频率表”，即它计算给定字符串中每个字符出现的次数：

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

此外，我会定义一个函数来判断一个频率表 x 是否为另一个表 y 的"子集"，也就是验证每个在 x 中的字符是否也出现在 y 中，但不会出现更多次：

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

您可以使用这个方法来定义 acceptableWord，以便它只接受其频率表是魔术字符串的频率表的子集的单词，因此我们得到：

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

- Frerich Raabe

---

我试图想出一种使用过滤器的方法，但是无法理解它... 猜测解决方案太简单了... 谢谢！ - Electric Coffee

如果你想成为 Haskell 时髦人，你可以将其变为 point-free，将定义缩短为 filterWords = filter (all (\elem` "poultry outwits ants")) . words`。实际上，现在我看到它 - 在我看来它仍然相当易懂！ - Frerich Raabe

我实际上已经做了...现在要过滤掉不符合字母数量的东西... - Electric Coffee

“doesn't fit the number of letters” 是什么意思？ - Frerich Raabe

有些单词中可能包含比原始单词更多相同字母的副本。 - Electric Coffee

@ElectricCoffee，既然您更明确地指定了您的要求，我已经扩展了我的答案。 - Frerich Raabe