在Haskell中找到给定集合A和通用集合U的补集 [英] Find complement set of a given set A and a universal set U in Haskell

问题描述

我尝试编写一个函数(complement)，给定一个集合A和一个通用集合U，返回一个相对于U的A的补充，包装在Just类型构造函数中.我必须仔细检查集合A是否不是U的子集，在这种情况下，我应该返回Nothing.

I have tried to write a function (complement), which given a set A and a universal set U, returns a complement of A with respect to U, wrapped in the Just type constructor. I have to double check if the set A is not a subset of U, in that case, I should return Nothing.

基本上，我发现很少有资源说明如何检查集合(在我们的情况下为A)是否是U的子集. http://www.multiwingspan.co.uk/haskell.php?page=子集 基本上，使用子集"功能(返回布尔值)就足够了，看看A是否是B的子集.

Basically, I found few resources that explain how to check if a set (in our case A), is a subset of U. http://www.multiwingspan.co.uk/haskell.php?page=subsets Basically, it is enough to use the "subset" function (that return a boolean), to see if A is a subset of B.

我找到了一个完全不同的网站，该网站解释了如何使用以下方法创建补集集而无需递归实现函数:

I found an as well different website that explains how to create the complement set without implement recursively functions, using:

import Data.Set(Set)
import qualified Data.Set  as Set

唯一的问题是我无法导入任何外部模块来解决此问题.

The only problem is that I CANNOT import any external modules to solve this problem.

该函数的签名为:

complement :: (Eq a) => [a] -> [a] -> Maybe [a]

我希望得到以下输出:

complement [1,2,3] [1..5] = Just [4,5]
complement [1,2,3] [2..5] = Nothing

有人可以帮助我应对吗?

Can anyone help me to deal with it?

推荐答案

我不想为您解决问题-我认为解决方案应该是您自己的工作.但是，我将提供一些功能列表，这些功能可以为您提供帮助，而您不必导入这些功能:

I don't want to solve your problem for you - I believe the solution should be your own work. However, I will provide a list of functions which could assist you, and which you don't have to import:

• filter f list:返回list的所有元素，其中f element返回True.例如，filter (\x -> (x /= 0)) [0,1,0,2,3]给出[1,2,3].这对not函数很有用，该函数可将Bool求反.例如filter (\x -> not (x > 2)) [1,2,3,4,5]给出[1,2].
• all f list:如果f为list的所有元素提供True，则返回True.例如，all (\x -> (x /= 0)) [1,2,3]给出True;但是，all (\x -> (x /= 0)) [1,0,2,3]给出False.
如果x是list的元素，则
• x `elem` list(实际上只是elem x list的语法糖)返回true.例如，1 `elem` [1,2,3]给出True，而0 `elem` [1,2,3]给出False.

• filter f list: returns all elements of list where f element returns True. For instance, filter (\x -> (x /= 0)) [0,1,0,2,3] gives [1,2,3]. This is useful with the not function, which inverts a Bool; for instance, filter (\x -> not (x > 2)) [1,2,3,4,5] gives [1,2].
• all f list: returns True if f gives True for all elements of list. For example, all (\x -> (x /= 0)) [1,2,3] gives True; however, all (\x -> (x /= 0)) [1,0,2,3] gives False.
• x `elem` list (which is really just syntax sugar for elem x list) returns true if x is an element of list. For example, 1 `elem` [1,2,3] gives True, but 0 `elem` [1,2,3] gives False.

同样，我不会直接为您提供解决此问题的方法.但是我可以向您保证，如果以正确的方式将上述功能(以及Just和Nothing构造函数)组合在一起，则可以使您的complement功能.

Again, I won't directly give you the solution to this problem. But I can guarantee you that if you put the above functions together in the right way - together with the Just and Nothing constructors - you can make your complement function.

这篇关于在Haskell中找到给定集合A和通用集合U的补集的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！