sofs

模块

SOF

模块摘要

用于操作集合集的函数。

描述

该模块提供有限集合和关系表示为集合的操作。直观地说，一个集合是元素的集合; 每个元素都属于该集合，集合包含每个元素。

给定一个集合A和一个句子S（x），其中x是一个自由变量，可以形成一个新的集合B，其元素正好是S（x）成立的那些元素A，这可以表示为B = {x in A：S（x）}。句子用逻辑运算符“对某些”（或“存在”），“for all”，“and”，“or”，“not”来表示。如果包含所有指定元素的集合的存在是已知的（在本模块中总是如此），这表示为B = {x：S（x）}。

包含元素a，b和c 的无序集合表示为{a，b，c}。这个表示法不能与元组相混淆。（a，b）表示具有第一坐标 a和第二坐标b 的有序对 a和b 。

该空集不包含任何元素。

如果它们包含相同的元素，则集合A 等于集合B，其表示为A = B。如果两个有序集合包含相同数量的元素并且在每个坐标处具有相同的元素，则它们是相等的。

如果A包含B包含的所有元素，则集合B是集合A 的子集。

该集合两套A和B是包含和A的所有元素B的所有元素的最小集合

两个集合A和B 的交集是包含属于B的所有A元素的集合。

如果它们的交集是空集，那么两个集合是不相交的。

两个集合A和B 的差别是包含A不属于B的所有元素的集合。

两组的对称差异是包含属于两组中任一组的那些元素的集合，但不是两者。

集合集合的联合是包含属于至少一个集合集合的所有元素的最小集合。

该交集的集合非空集是包含属于每一套集合中的所有元素的集合。

表示为X×Y的两个集合X和Y 的笛卡尔乘积是集合{a：a =（x，y），对于X中的某个x和Y中的某个y}。

函数 F是关系，X×Y的一个子集，使得F的域是等于X和使得对于每x在X有Y中一个独特的元素y与（X，Y）中的F.后者的条件可以表示为：如果x F y和x F z，则y = z。在这个模块中，并不要求F的域等于X，因为一个关系被认为是一个函数。

我们写F（x）= y代替F（x，y）在F或x F y中的函数，并且说F将x映射到y上，或者x在x上的值是y。

由于函数是关系，最后一项（域，范围等）的定义也适用于函数。

如果函数F的反函数是函数F'，则F'被称为F的逆函数。

如果F1的范围是F2的域的子集，则两个函数F1和F2的相对乘积称为F1和F2的合成。

有时，当函数的范围比函数本身更重要时，该函数被称为一个家族。

分区的一组X的是X，其联合是X和其元素是两两不相交的非空子集的集合S上。

集合中的关系是等价关系如果它是自反的，对称的，传递性的。

如果R是X中的等价关系，且x是X的元素，则x关于R 的等价类是x R y所保持的X的所有元素y的集合。等价类构成X的分割。相反，如果C是X的分割，则如果属于相同的等价类的X的任何两个元素都成立的关系是由分割C引发的等价关系。

如果R是X中的等价关系，则规范映射是将X的每个元素映射到其等价类的函数。

上面定义的关系（作为有序对的集合）从现在开始称为二元关系。我们称一组有序集合（x1，...，xn）为一个（n元）关系，并且说该关系是笛卡儿乘积X1×...×Xn的一个子集，其中xi是Xi，1 <= i <= n。该投影一个n元关系R到坐标i上的集合是R中对Xj中某个xj的集合{xi：（x1，...，xi，...，xn），1≤j≤n且不是i = Ĵ}。在第一和第二坐标上的二元关系R的投影分别是R的域和范围。二元关系的相对乘积可以推广到n元关系如下。令TR是从X到Yi的二元关系的有序集合（R1，...，Rn），以及从（Y1×...×Yn）到Z的二元关系.

该模块所识别的集合由关系集的元素表示，关系集被定义为最小集，以便：

-  For every atom T, except '\_', and for every term X, (T, X) belongs to Sets (**atomic sets**).

-  (['\_'], []) belongs to Sets (the **untyped empty set**).

-  For every tuple T = {T[1], ..., T[n]} and for every tuple X = {X[1], ..., X[n]}, if (T[i], X[i]) belongs to Sets for every 1 <= i <= n, then (T, X) belongs to Sets (**ordered sets**).

-  For every term T, if X is the empty list or a non-empty sorted list [X[1], ..., X[n]] without duplicates such that (T, X[i]) belongs to Sets for every 1 <= i <= n, then ([T], X) belongs to Sets (**typed unordered sets**).

一个外部组是集的范围的元件。

一个类型是Sets的域的一个元素。

如果S是Sets的一个元素（T，X），那么T是X 的有效类型，T是S的类型，X是S的外部集合。from_term/2从一个类型和一个Erlang项转换成一个集合一个外部设置。

由Sets表示的集合是函数Set from Set到Erlang术语和Erlang术语集的范围的元素：

- Set(T,Term) = Term, where T is an atom
- Set{T[1], ..., T[n]}, {X[1], ..., X[n]}) = (Set(T[1], X[1]), ..., Set(T[n], X[n]))
- Set([T], [X[1], ..., X[n]]) = {Set(T, X[1]), ..., Set(T, X[n])}
- Set([T], []) = {}

如果不存在混淆风险，则使用它们所代表的集合来标识集合的元素。例如，如果U是union/2用S1和S2作为参数调用的结果，则U被认为是S1和S2的并集。更精确的表述是Set（U）是Set（S1）和Set（S2）的并集。

这些类型用于实现必须满足的各种条件。作为一个例子，考虑两个集合R和S的相对乘积，回想一下，如果R是与Y的二元关系，并且S是与Y的二元关系，则定义R和S的相对乘积。实现相对的函数product，relative_product / 2通过匹配{A，B}与第一个参数（Arg1 say）的类型匹配来表示二进制关系，并且针对第二个参数（Arg2说）的类型检查参数{C，D}。 {A，B}匹配Arg1类型的事实将被解释为Arg1，表示从X到Y的二元关系，其中X被定义为所有集合Set（x）对于某些元素x in设置其类型是A，对于Y同样如此。以同样的方式，将Arg2解释为表示从W到Z的二元关系。最后检查B是否匹配C，这足以确保W等于Y.未分类的空集是分开处理：其类型'_'与任何无序集合的类型相匹配。

这个模块的一些功能（drestriction / 3，family_projection / 2，partition / 2，partition_family / 2，projection / 2，restriction / 3，substitution / 2）接受一个Erlang函数作为修改给定无序的每个元素的方法组。这样的函数，在下面称为SetFun，可以被指定为一个函数对象（fun），一个元组{外部，Fun}或一个整数：

如果将SetFun指定为函数，则将函数应用于给定集合的每个元素，并将返回值假定为集合。

如果将SetFun指定为元组{external, Fun}，则Fun将应用于给定集合的每个元素的外部集合，并将返回值假定为外部集合。选择无序集合的元素作为外部集合并从外部集合列表中组装新的无序集合在当前实现中比将每个元素作为集合修改更高效。但是，只有当无序集合的元素是原子集合或有序集合时才能使用此优化。也必须是元素的类型匹配Fun的某个子句（创建的集合的类型是对给定集合的类型应用Fun的结果），并且Fun除了选择，复制或重新安排部分元素。

将SetFun指定为整数I相当于指定{external, fun(X) -> element(I, X) end}，但是它是首选，因为它可以更有效地处理这种情况。

Set3包含不属于Set2的Set1的元素。

Set4包含属于Set2的Set1的元素。

Set5包含不属于Set1的Set2的元素。

to_external(AnySet) -> ExternalSet

类型

返回external set原子，有序或无序集合。

to_sets(ASet) -> Sets

类型

将有序集合的元素ASet作为集合的元组返回，并将无序集合的元素ASet作为集合的排序列表返回，而不重复。

type(AnySet) -> Type

类型

返回type原子，有序或无序集合。

union(SetOfSets) -> Set

类型

返回该union组集合SetOfSets。

union(Set1, Set2) -> Set3

类型

返回Set1和Set2的并集。

union_of_family(Family) -> Set

类型

返回family Family的联合。

1> F = sofs:family([{a,[0,2,4]},{b,[0,1,2]},{c,[2,3]}]),
S = sofs:union_of_family(F),
sofs:to_external(S).
[0,1,2,3,4]

weak_relation(BinRel1) -> BinRel2

类型

返回与二元关系BinRel1对应的弱关系W的子集S. 设F是BinRel1的字段。子集S被定义为使得x S y如果x W y对于F中的一些x以及对于F中的某些y而言是如此。

1> R1 = sofs:relation([{1,1},{1,2},{3,1}]),
R2 = sofs:weak_relation(R1),
sofs:to_external(R2).
[{1,1},{1,2},{2,2},{3,1},{3,3}]

扩展内容

dict(3)，digraph(3)，orddict(3)，ordsets(3)，sets(3)