string - 你如何在 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' 而不是。

Answer 1

过滤事物列表(例如单词)的一个好方法是使用 filter 功能。您需要提供的是一个谓词，它告诉您是否应该包含一个字符串。你评论说你想包括那些由 "poultry outwits ants" 中的字母组成的字符串, 所以会是

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

现在，在你写的另一条评论中

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

所以我怀疑您真正想要的是找出哪些单词可以由 "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")