检查一个列表是否包含另一个列表中的所有值的习惯Haskell方法是什么?

我的问题类似于我如何使用haskell来检查列表是否包含元组中的值，但在我的情况下，具有必须全部在我的原始列表中的值的列表是字母表。对elem有26个调用感觉真的很混乱，所有的调用都在一起。

是否有更简洁的方法来检查一个给定列表是否包含另一个列表中的所有元素，而另一个列表长26个元素?

我喜欢user1984的答案，但它确实暗示了处理非字母字符的方式。这里有一个几乎同样简单的方法，但是不需要额外的代码来处理非字母字符。基本的想法是走另一个方向;他们的答案建立了一个集合，这个是通过一次删除一个字符来摧毁一个。它也是O(n)，和他们的一样。

import qualified Data.Set as S
isPangram :: String -> Bool
isPangram = S.null . foldr S.delete (S.fromList ['a'..'z'])

如果不区分大小写，可以导入Data.Char，将S.delete修改为(S.delete . toLower)。

这是基于Daniel Wagner的答案，但是如果找到了所有的字母，它就会提前结束，而他遍历整个列表，然后向后删除元素，然后在返回到开头时给出答案。

import qualified Data.Set as S
import Data.Set (Set)
letters :: Set Char
letters = S.fromList ['a'..'z']
isPangram :: String -> Bool
isPangram xs0 = go xs0 letters
where
go :: String -> Set Char -> Bool
go [] letters = S.null letters
go (c : cs) letters =
S.null letters || go cs (S.delete c letters)

您可能想知道为什么我首先匹配字符串并检查匹配下的letters，而不是相反。嗯，这只是因为使用foldr:

重写它很有趣

isPangram :: String -> Bool
isPangram xs0 = foldr step S.null xs0 letters
where
step :: String -> Set Char -> Bool
step c r letters =
S.null letters || r (S.delete c letters)

对于像字母表这样的东西，Data.Set实际上并不是最有效的方法。最好使用IntSet，它更紧凑，速度更快。

import qualified Data.IntSet as S
import Data.IntSet (IntSet)
letters :: IntSet
letters = S.fromList (map fromEnum ['a'..'z'])
isPangram :: String -> Bool
isPangram xs0 = foldr step S.null xs0 letters
where
step :: String -> IntSet -> Bool
step c r letters =
S.null letters || r (S.delete (fromEnum c) letters)

我的理解是，您正在尝试检查字符串是否是一个泛字母，这意味着它包含所有的[插入您首选的语言]字母。

下面的代码使用Data.Set。根据定义，集合数据结构不能包含重复的元素。在将字符串中的所有字符添加到set中后，使用set的这个属性来计算其中的元素个数。如果它等于我们正在处理的字母表的数目，则意味着该字符串包含字母表中的所有字符，因此它是一个泛字母。

请注意，这段代码不考虑小写字母和大写字母之间的区别，还计算空白和标点符号。如果有这些情况，你会得到错误的答案。通过一些调整，你可以使它工作。

这个解的时间复杂度是n * log 26，也就是Daniel Wagner指出的大0中的n。原因是，虽然Haskell的默认集合是一个平衡树，但集合中的元素数量永远不会超过26个，所以它是线性的。使用set的散列实现可能会对非常大的字符串进行一些优化。空间复杂度是恒定的，因为我们使用的额外空间从不超过26个字符。

import qualified Data.Set as S
isPangram :: [Char] -> Bool
isPangram s = length (S.fromList s) == 26

从字面上回答你的问题，

allPresent :: Eq a => [a] -> [a] -> Bool
allPresent alphabet xs = foldr (a r -> elem a xs && r) True alphabet

是一个简洁而低效的代码，它将调用elem的次数与alphabet中的字母数量一样多，并且会使用& & &;结果。

例如，对于三个字母的字母表a、b和c，它将相当于一个&&链，其中包含对elem的三个调用和一个True:

allPresent [a, b, c] xs
==
elem a xs && elem b xs && elem c xs && True

一旦检测到第一个缺失的字母，它将停止，返回False。但是它可能会为alphabet的每个字母重新梳理整个xs，这是低效的。

如果你确实在寻找一个程序，你可以试试我想出的这个解决方案。

import Data.Char ( toLower )
isPangram :: String -> Bool
isPangram text = all isInText ['a'..'z'] where
isInText x = x `elem` map toLower text

相关内容

最新更新

热门标签：