将函数应用于列表中的每个元素到另一个列表中的每个元素 - Haskell

Question

我的最终目标是找出列表 y 是否包含列表 x 的所有元素(我正在检查 x 是否是 y 类事物的子集(

subset x y =
and [out | z <- x
         , out <- filter (==z) y ]

这不起作用，我知道这是因为 z 仍然是一个列表。我试图理解这一点。

我想我可能不得不使用 elem 函数，但我不确定如何将 x 拆分为可以通过 y 单独比较的字符。

我很惭愧地说，我已经在这个简单的问题上工作了一个半小时。

Answer 1

检查xs的所有元素是否都是ys的元素非常简单。遍历xs，对于每个元素，检查它是否在ys：

subset xs ys = all (x -> elem x ys) xs

Answer 2

您也可以使用列表差异函数 ( \ (。如果您有列表 y 和列表 x，并且想要检查 x 的所有元素是否都在 y 中，那么x \ y将返回一个新列表，其中包含 x 中不在 y 中的元素。如果 x 的所有元素都在 y 中，则返回的列表将为空。

例如，如果列表 y 是 [1,2,3,4,5]，列表 x 是 [2,4]，您可以执行以下操作：

Prelude> [2,4] \ [1,2,3,4,5]
[]

如果列表 y 是 [1,2,3,4,5]，列表 x 是 [2,4,6]，则：

Prelude> [2,4,6] \ [1,2,3,4,5]
[6]

Answer 3

推理子集的简单方法是使用集作为数据类型。

import qualified Data.Set as S
subset :: Ord a => [a] -> [a] -> Bool
subset xs ys = S.isSubsetOf (S.fromList xs) (S.fromList ys)

然后它就像

：

*Main> subset [1..5] [1..10]
True
*Main> subset [0..5] [1..10]
False

Answer 4

让我们将其分解为两个子问题：

1. 查找值是否为列表的成员;
2. 使用 #1 的解决方案测试列表中的每个值是否都在第二个值中。

对于第一个子问题，已经有一个库函数：

elem :: (Eq a, Foldable t) => a -> t a -> Bool

列表是一种Foldable类型，因此您可以将此函数与t列表一起使用，它将具有以下类型：

elem :: (Eq a) => a -> [a] -> Bool

练习：编写你自己的elem版本，专门用于处理列表(现在不用担心Foldable的东西(。

所以现在，要解决#2，第一步是这样的：

-- For each element of `xs`, test whether it's an element of `ys`.
-- Return a list of the results.
notYetSubset :: Eq a => [a] -> [a] -> [Bool]
notYetSubset xs ys = map (x -> elem x ys) xs

之后，我们需要从单个布尔结果列表转到只有一个布尔值。 还有一个标准的库函数也可以做到这一点：

-- Return true if and only if every element of the argument collection is 
-- is true.
and :: Foldable t => t Bool -> Bool

练习：编写您自己的and版本，专门用于列表：

myAnd :: [Bool] -> Bool
myAnd [] = _fillMeIn
myAnd (x:xs) = _fillMeIn

使用这些工具，现在我们可以编写subset：

subset :: Eq a => [a] -> [a] -> [Bool]
subset xs ys = and (map (x -> elem x ys) xs)

虽然更有经验的哈斯凯勒可能会这样写：

subset :: Eq a => [a] -> [a] -> [Bool]
subset xs ys = every (`elem` ys) xs
{- This:
       (`elem` ys)
   ...is a syntactic shortcut for this:
       x -> x elem ys
-}

。其中every是另一个标准库函数，它只是map和and组合的快捷方式：

-- Apply a boolean test to every element of the list, and
-- return `True` if and only if the test succeeds for all elements.
every :: (a -> Bool) -> [a] -> Bool
every p = and . map p