非常教程

Erlang 20参考手册

stdlib

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}。

关系是X×Y.设R的一个子集是一个关系。(x,y)属于R的事实被写为x R y。由于关系是集合,最后一项(子集,联合等)的定义也适用于关系。

R 的是Y中某个y的集合{x:x R y}。

R 的范围是对于X中的某个x的集合{y:x R y}。R 的是R中一些(x,y)的集合{a:a =(y,x)}。

如果A是X的子集,则R下的A 的图像是A中某个x的集合{y:x R y}。

如果B是Y的一个子集,则为反转图像B的集合是{B:中某些y的x:x R y}。

如果R是从X到Y的关系,并且S是从Y到Z的关系,则R和S 的相对乘积是从X到Z定义的关系T,使得x T z当且仅当存在元素y在Y中使得x R y和y S z。

R对A 的限制是定义集合S,使得当且仅当在A中存在元素x使得x R y。

如果S是R键A的限制,则R是一个扩展的S为X.如果X = Y,则R被称为关系 X.该字段在X关系R的是R的域的结合和R的范围。

如果R是X中的关系,并且如果S被定义为使得x S y如果x R y而不是x = y,那么S是严格的相反,如果S是X中的关系,并且如果R被定义为使得x R y

如果x S y或x = y,则R是与S对应的关系.X中的关系R是如果x R x对于X的每个元素x都是自反的,那么如果x R y意味着y R x,则它是对称的,并且如果x R y和y R z意味着x R z ,则它是传递性的

  • 函数 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是从I到X的族,那么xi表示在索引i处的函数的值。“X中的一个家庭”符号用于这样的家庭。

当索引集合是集合X的一组子集时,我们称X为x 的子集家族

如果x是X的子集家族,则x的范围的并集称为 x 的联合

如果x非空(索引集非空),则为该族交集x是x的范围的交集。

在这个模块中,唯一被考虑的家族是一些集合X的子集的家族;在下文中,“家庭”一词用于这些子集族。

  • 分区的一组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的二元关系.

TR和S 的相对乘积是二元定义X到Z的关系T,使得x T z当且仅当在Yi中存在对于每个1 <= i <= n使得x Ri yi和(y1,...,yn)S z的元素yi。现在令TR为从X1到Yi的二元关系的有序集合(R1,...,Rn),以及X1×...×Xn的子集。该对于一些(x1,...,xn),TR和S的多个相对乘积被定义为集合{z:z =((x1,...,xn),(y1,...,yn)在S中,对于Ri中的一些(xi,yi),1 <= i <= n}。

关于坐标i和j的n元关系R和m元关系S 的自然连接被定义为集合{z:z =(x1,...,xn,y1,...,yj- 1,yj + 1,...,ym)对于R中的一些(x1,...,xn)和对于S中的一些(y1,...,ym),使得xi = yj}。

  • 该模块所识别的集合由关系集的元素表示,关系集被定义为最小集,以便:
-  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},但是它是首选,因为它可以更有效地处理这种情况。

SetFuns的例子:

fun sofs:union/1
fun(S) -> sofs:partition(1, S) end
{external, fun(A) -> A end}
{external, fun({A,_,C}) -> {C,A} end}
{external, fun({_,{_,C}}) -> C end}
{external, fun({_,{_,{_,E}=C}}) -> {E,{E,C}} end}
2

没有指定SetFun应用于无序集的元素的顺序,并且可以在该模块的未来版本中更改。

该模块功能的执行时间由排序列表所花费的时间决定。当不需要排序时,执行时间在最坏的情况下与输入参数和返回值的大小之和成正比。一些函数在恒定时间执行:from_external/2is_empty_set/1is_set/1is_sofs_set/1to_external/1 type/1

当给定格式不正确的参数或设置不兼容的类型时,此模块的功能会使用badarg,bad_function或type_mismatch消息退出进程 。

比较外部设置时,使用operator==/2。

数据类型

anyset() = ordset() | a_set()

任何类型的集合(也包括原子集)。

binary_relation() = relation()

一个binary relation

external_set() = term()

一个 external set

family() = a_function()

一个family (子集)。

a_function() = relation()

一个function

ordset()

一个ordered set

relation() = a_set()

一个n-ary relation

a_set()

一个unordered set

set_of_sets() = a_set()

组无序的无序集。

set_fun() =     integer() >= 1 |     {external, fun((external_set()) -> external_set())} |     fun((anyset()) -> anyset())

一个 SetFun

spec_fun() =     {external, fun((external_set()) -> boolean())} |     fun((anyset()) -> boolean())

type() = term()

一个type

tuple_of(T)

元素类型为T的元组。

输出

a_function(Tuples) -> Function

a_function(Tuples, Type) -> Function

类型

Function = a_function()

Tuples = [tuple()]

Type = type()

创建一个函数。如果结果是一个函数,a_function(F,T)等价于from_term(F,T)。如果没有明确指定类型,则使用[{atom,atom}]作为函数类型。

canonical_relation(SetOfSets) -> BinRel

类型

BinRel = binary_relation()

SetOfSets = set_of_sets()

返回包含元素(E,Set)的二元关系,使得Set属于SetOfSets,E属于Set。如果SetOfSets是集合X的一个分区,R是由SetOfSets引发的X中的等价关系,那么返回的关系是从X到关于R的等价类的规范映射

1> Ss = sofs:from_term([[a,b],[b,c]]),
CR = sofs:canonical_relation(Ss),
sofs:to_external(CR).
[{a,[a,b]},{b,[a,b]},{b,[b,c]},{c,[b,c]}]

composite(Function1, Function2) -> Function3

类型

Function1 = Function2 = Function3 = a_function()

返回函数Function1和Function2的组合

1> F1 = sofs:a_function([{a,1},{b,2},{c,2}]),
F2 = sofs:a_function([{1,x},{2,y},{3,z}]),
F = sofs:composite(F1, F2),
sofs:to_external(F).
[{a,x},{b,y},{c,y}]

constant_function(Set, AnySet) -> Function

类型

AnySet = anyset()

Function = a_function()

Set = a_set()

创建函数这组中的每个元素映射设置到AnySet。

1> S = sofs:set([a,b]),
E = sofs:from_term(1),
R = sofs:constant_function(S, E),
sofs:to_external(R).
[{a,1},{b,1}]

converse(BinRel1) -> BinRel2

类型

BinRel1 = BinRel2 = binary_relation()

返回相反的二元关系BinRel1。

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

difference(Set1, Set2) -> Set3

类型

Set1 = Set2 = Set3 = a_set()

返回Set1和Set2集合的差异

digraph_to_family(Graph) -> Family

digraph_to_family(Graph, Type) -> Family

类型

Graph = digraph:graph()

Family = family()

Type = type()

从有向图Graph创建一个。每个顶点a的 图形由一对表示(A,{B [1],...,B [n]的}),其中B [I]:s为a的外邻居。如果没有明确指定类型,则使用[{atom,[atom]}]作为族的类型。假设Type是家族外部集合的有效类型

如果G是有向图,则认为G的顶点和边与family_to_digraph(digraph_to_family(G))的顶点和边相同 。

domain(BinRel) -> Set

类型

BinRel = binary_relation()

Set = a_set()

返回二元关系BinRel的

1> R = sofs:relation([{1,a},{1,b},{2,b},{2,c}]),
S = sofs:domain(R),
sofs:to_external(S).
[1,2]

drestriction(BinRel1, Set) -> BinRel2

类型

BinRel1 = BinRel2 = binary_relation()

Set = a_set()

返回二元关系之间的差异BinRel1和限制的BinRel1来设置。

1> R1 = sofs:relation([{1,a},{2,b},{3,c}]),
S = sofs:set([2,4,6]),
R2 = sofs:drestriction(R1, S),
sofs:to_external(R2).
[{1,a},{3,c}]

drestriction(R, S) 等同于difference(R, restriction(R, S))。

drestriction(SetFun, Set1, Set2) -> Set3

类型

SetFun = set_fun()

Set1 = Set2 = Set3 = a_set()

作为应用SetFun的结果,返回Set1的子集,其中包含那些不给予Set2中的元素的元素。

1> SetFun = {external, fun({_A,B,C}) -> {B,C} end},
R1 = sofs:relation([{a,aa,1},{b,bb,2},{c,cc,3}]),
R2 = sofs:relation([{bb,2},{cc,3},{dd,4}]),
R3 = sofs:drestriction(SetFun, R1, R2),
sofs:to_external(R3).
[{a,aa,1}]

drestriction(F, S1, S2) 相当于difference(S1, restriction(F, S1, S2))。

empty_set() -> Set

类型

Set = a_set()

返回无类型的空集。empty_set()相当于from_term([],['_'])。

extension(BinRel1, Set, AnySet) -> BinRel2

类型

AnySet = anyset()

BinRel1 = BinRel2 = binary_relation()

Set = a_set()

返回BinRel1的扩展名,使得对于Set中不属于BinRel1的每个元素E,BinRel2包含该对(E, AnySet)。

1> S = sofs:set([b,c]),
A = sofs:empty_set(),
R = sofs:family([{a,[1,2]},{b,[3]}]),
X = sofs:extension(R, S, A),
sofs:to_external(X).
[{a,[1,2]},{b,[3]},{c,[]}]

family(Tuples) -> Family

family(Tuples, Type) -> Family

类型

Family = family()

Tuples = [tuple()]

Type = type()

创建一个子集族。 如果结果是家庭,则family(F, T等同于 from_term(F,T)。如果没有明确指定类型,则使用[{atom,[atom]}]作为族类型。

family_difference(Family1,Family2) - > Family3

类型

Family1 = Family2 = Family3 =family()

如果Family1和Family2是家族,那么Family3就是这样一个家族,即索引集等于Family1的索引集,而Family3[i]是Family1[i]和Family2[i]之间的区别,如果Family2映射为i,否则Family1 [i]。

1> F1 = sofs:family([{a,[1,2]},{b,[3,4]}]),
F2 = sofs:family([{b,[4,5]},{c,[6,7]}]),
F3 = sofs:family_difference(F1, F2),
sofs:to_external(F3).
[{a,[1,2]},{b,[3]}]

family_domain(Family1) -> Family2

类型

Family1 = Family2 = family()

如果Family1是一个家族,并且Family1 [i]对于Family1的索引集合中的每个i是二元关系,则Family2是与Family1具有相同索引集合的族,这样Family2 [i]是Family1 [i]。

1> FR = sofs:from_term([{a,[{1,a},{2,b},{3,c}]},{b,[]},{c,[{4,d},{5,e}]}]),
F = sofs:family_domain(FR),
sofs:to_external(F).
[{a,[1,2,3]},{b,[]},{c,[4,5]}]

family_field(Family1) -> Family2

类型

Family1 = Family2 = family()

如果Family1是一个家庭,并且Family1 [i]对于Family1的索引集合中的每个i是二元关系,则Family2是具有与Family1相同的索引集合的族,使得Family2 [i]是Family1 [i]。

1> FR = sofs:from_term([{a,[{1,a},{2,b},{3,c}]},{b,[]},{c,[{4,d},{5,e}]}]),
F = sofs:family_field(FR),
sofs:to_external(F).
[{a,[1,2,3,a,b,c]},{b,[]},{c,[4,5,d,e]}]

family_field(Family1) is equivalent tofamily_union(family_domain(Family1), family_range(Family1)).

family_intersection(Family1) -> Family2

类型

Family1 = Family2 = family()

如果Family1是一个family,并且Family1 [i]是Family1索引集中每个i的一组集合,则Family2是与Family1具有相同索引集的族,这样Family2 [i]是Family1 [i]。

如果Family1 [i]对于某个i是空集,则该过程将以badarg消息退出。

1> F1 = sofs:from_term([{a,[[1,2,3],[2,3,4]]},{b,[[x,y,z],[x,y]]}]),
F2 = sofs:family_intersection(F1),
sofs:to_external(F2).
[{a,[2,3]},{b,[x,y]}]

family_intersection(Family1, Family2) -> Family3

类型

Family1 = Family2 = Family3 = family()

如果Family1和Family2是家庭,那么Family3就是这样一个家庭,即索引集是Family1:和Family2:s索引集的交集,而Family3 [i]是Family1 [i]和Family2 [i]的交集。

1> F1 = sofs:family([{a,[1,2]},{b,[3,4]},{c,[5,6]}]),
F2 = sofs:family([{b,[4,5]},{c,[7,8]},{d,[9,10]}]),
F3 = sofs:family_intersection(F1, F2),
sofs:to_external(F3).
[{b,[4]},{c,[]}]

family_projection(SetFun, Family1) -> Family2

类型

SetFun = set_fun()

Family1 = Family2 = family()

如果Family1是一个家族,则Family2是与Family1具有相同索引集的族,这样Family2 [i]是以Family1 [i]作为参数调用SetFun的结果。

1> F1 = sofs:from_term([{a,[[1,2],[2,3]]},{b,[[]]}]),
F2 = sofs:family_projection(fun sofs:union/1, F1),
sofs:to_external(F2).
[{a,[1,2,3]},{b,[]}]

family_range(Family1) -> Family2

类型

Family1 = Family2 = family()

如果Family1是一个家庭,Family1 [i]是Family1索引集中每个i的二元关系,则Family2是与Family1具有相同索引集的族,这样Family2 [i]是Family1 [i]。

1> FR = sofs:from_term([{a,[{1,a},{2,b},{3,c}]},{b,[]},{c,[{4,d},{5,e}]}]),
F = sofs:family_range(FR),
sofs:to_external(F).
[{a,[a,b,c]},{b,[]},{c,[d,e]}]

family_specification(Fun, Family1) -> Family2

类型

Fun = spec_fun()

Family1 = Family2 = family()

如果Family1是一个家庭,那么Family2对Family1 [i]返回true的索引集中的那些元素i进行限制。 如果Fun是一个元组{外部,Fun2},则Fun2应用于Family1 [i]的外部集合,否则Fun应用于Family1 [i]。

1> F1 = sofs:family([{a,[1,2,3]},{b,[1,2]},{c,[1]}]),
SpecFun = fun(S) -> sofs:no_elements(S) =:= 2 end,
F2 = sofs:family_specification(SpecFun, F1),
sofs:to_external(F2).
[{b,[1,2]}]

family_to_digraph(Family) -> Graph

family_to_digraph(Family, GraphType) -> Graph

类型

Graph = digraph:graph()

Family = family()

GraphType = [digraph:d_type()]

创建家庭Family系列的有向图 。对于每一对(a, {b[1], ..., b[n]})的家庭,(a, b[i]) for 1 <= i <= n被添加到新创建的有向图。

如果未指定图类型,则使用digraph:new/0创建有向图,否则将参数GraphType作为第二个参数传递给 digraph:new/1

它是一个家庭,它认为F是digraph_to_family(family_to_digraph(F), type(F))的一个子集。如果union_of_family(F)是domain(F)的子集, 则平等成立。

在非循环图中创建一个循环用循环消息退出该过程。

family_to_relation(Family) -> BinRel

类型

Family = family()

BinRel = binary_relation()

如果家庭是一个Family,则BinRel是包含所有对(i,x)的二元关系,这样我就属于Family的索引集,并且x属于Family[i]。

1> F = sofs:family([{a,[]}, {b,[1]}, {c,[2,3]}]),
R = sofs:family_to_relation(F),
sofs:to_external(R).
[{b,1},{c,2},{c,3}]

family_union(Family1) -> Family2

类型

Family1 = Family2 = family()

如果Family1是一个family,并且Family1 [i]是Family1的索引集中每个i的集合,则Family2与Family1具有相同索引集的族,这样Family2 [i]就是Family1 [i]。

1> F1 = sofs:from_term([{a,[[1,2],[2,3]]},{b,[[]]}]),
F2 = sofs:family_union(F1),
sofs:to_external(F2).
[{a,[1,2,3]},{b,[]}]

family_union(F) x相当于 family_projection(fun sofs:union/1, F)。

family_union(Family1, Family2) -> Family3

类别

Family1 = Family2 = Family3 = family()

如果Family1和Family2是家族,那么Family3就是这样一个家族,即索引集是Family1:和Family2:s索引集的并集,而Family3 [i]是Family1 [i]和Family2 [i]的并集 都映射i,否则Family1 [i]或Family2 [i]。

1> F1 = sofs:family([{a,[1,2]},{b,[3,4]},{c,[5,6]}]),
F2 = sofs:family([{b,[4,5]},{c,[7,8]},{d,[9,10]}]),
F3 = sofs:family_union(F1, F2),
sofs:to_external(F3).
[{a,[1,2]},{b,[3,4,5]},{c,[5,6,7,8]},{d,[9,10]}]

field(BinRel) -> Set

类型

BinRel = binary_relation()

Set = a_set()

返回二元关系BinRel的字段

1> R = sofs:relation([{1,a},{1,b},{2,b},{2,c}]),
S = sofs:field(R),
sofs:to_external(S).
[1,2,a,b,c]

field(R)相当于union(domain(R), range(R))。

from_external(ExternalSet, Type) -> AnySet

类型

ExternalSet = external_set()

AnySet = anyset()

Type = type()

创建从一组外部设定ExternalSet和类型类型。假定Type是一个有效的ExternalSet类型

from_sets(ListOfSets) -> Set

类型

Set = a_set()

ListOfSets = [anyset()]

返回包含列表ListOfSets集合的无序集合

1> S1 = sofs:relation([{a,1},{b,2}]),
S2 = sofs:relation([{x,3},{y,4}]),
S = sofs:from_sets([S1,S2]),
sofs:to_external(S).
[[{a,1},{b,2}],[{x,3},{y,4}]]

from_sets(TupleOfSets) -> Ordset

类型

Ordset = ordset()

TupleOfSets = tuple_of(anyset())

返回包含非空tupleOfSets集合的有序集合

from_term(Term) -> AnySet

from_term(Term, Type) -> AnySet

类型

AnySet = anyset()

Term = term()

Type = type()

通过遍历术语Term来创建Sets的元素,对列表进行排序,删除重复项以及为如此获得的外部集合派生或验证有效类型。明确指定的类型Type可以用来限制遍历的深度;原子类型会停止遍历,如下例所示,其中“foo”和{“foo”}未被修改:

1> S = sofs:from_term([{{"foo"},[1,1]},{"foo",[2,2]}],
[{atom,[atom]}]),
sofs:to_external(S).
[{{"foo"},[1]},{"foo",[2]}]

from_term可用于创建原子或有序集合。这个集合的唯一目的是后来构建无序集合,因为这个模块中的所有函数都在无序集合上进行操作。如果有序集合很大,并且不想通过重新构建无序集合的元素来浪费堆,那么从有序集合集合中创建无序集合可能是一条路。以下示例显示可以“逐层”构建一个集合:

1> A = sofs:from_term(a),
S = sofs:set([1,2,3]),
P1 = sofs:from_sets({A,S}),
P2 = sofs:from_term({b,[6,5,4]}),
Ss = sofs:from_sets([P1,P2]),
sofs:to_external(Ss).
[{a,[1,2,3]},{b,[4,5,6]}]

其他创建集的函数是from_external/2from_sets/1。的特殊情况下from_term/2是a_function/1,2,empty_set/0,family/1,2,relation/1,2, andset/1,2。

image(BinRel, Set1) -> Set2

类型

BinRel = binary_relation()

Set1 = Set2 = a_set()

返回图像集的设置1的二元关系下BinRel。

1> R = sofs:relation([{1,a},{2,b},{2,c},{3,d}]),
S1 = sofs:set([1,2]),
S2 = sofs:image(R, S1),
sofs:to_external(S2).
[a,b,c]

intersection(SetOfSets) -> Set

Types

Set = a_set()

SetOfSets = set_of_sets()

返回intersection的一套套的SetOfSets。

将一组空的集合与一个badarg消息一起退出该过程 。

intersection(Set1, Set2) -> Set3

类型

Set1 = Set2 = Set3 = a_set()

返回intersection的SET1和SET2。

intersection_of_family(Family) -> Set

类型

Family = family()

Set = a_set()

返回 family 家庭。

与一个空的家庭相交会用badarg消息退出该过程 。

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

inverse(Function1) -> Function2

类型

Function1 = Function2 = a_function()

返回函数Function1的函数。

1> R1 = sofs:relation([{1,a},{2,b},{3,c}]),
R2 = sofs:inverse(R1),
sofs:to_external(R2).
[{a,1},{b,2},{c,3}]

inverse_image(BinRel, Set1) -> Set2

类型

BinRel = binary_relation()

Set1 = Set2 = a_set()

返回逆图像的设置1的二元关系下BinRel。

1> R = sofs:relation([{1,a},{2,b},{2,c},{3,d}]),
S1 = sofs:set([c,d,e]),
S2 = sofs:inverse_image(R, S1),
sofs:to_external(S2).
[2,3]

is_a_function(BinRel) -> Bool

类型

Bool = boolean()

BinRel = binary_relation()

如果二进制关系BinRel是一个函数或无类型的空集,则返回true,否则返回false。

is_disjoint(Set1, Set2) -> Bool

类型

Bool = boolean()

Set1 = Set2 = a_set()

返回真如果SET1和SET2是不相交,否则为false。

is_empty_set(AnySet) -> Bool

类型

AnySet = anyset()

Bool = boolean()

如果AnySet是空无序集合,则返回true,否则返回false。

is_equal(AnySet1, AnySet2) -> Bool

类型

AnySet1 = AnySet2 = anyset()

Bool = boolean()

返回真如果AnySet1和AnySet2是平等的,否则为false。以下示例显示比较集合的等式时使用了==/2:

1> S1 = sofs:set([1.0]),
S2 = sofs:set([1]),
sofs:is_equal(S1, S2).
true

is_set(AnySet) -> Bool

类型

AnySet = anyset()

Bool = boolean()

返回真如果AnySet是一个无序集,和假如果AnySet是一组有序的或原子集合。

is_sofs_set(Term) -> Bool

类型

Bool = boolean()

Term = term()

如果Term是无序集合,有序集合或原子集合,则返回true,否则返回false。

is_subset(Set1, Set2) -> Bool

类型

Bool = boolean()

Set1 = Set2 = a_set()

如果Set1是Set2的子集,则返回true,否则返回false。

is_type(Term) -> Bool

类型

Bool = boolean()

Term = term()

如果术语Term是类型,则返回true。

join(Relation1, I, Relation2, J) -> Relation3

类型

Relation1 = Relation2 = Relation3 = relation()

I = J = integer() >= 1

返回关系Relation1和Relation2在坐标I和J上的自然连接

1> R1 = sofs:relation([{a,x,1},{b,y,2}]),
R2 = sofs:relation([{1,f,g},{1,h,i},{2,3,4}]),
J = sofs:join(R1, 3, R2, 1),
sofs:to_external(J).
[{a,x,1,f,g},{a,x,1,h,i},{b,y,2,3,4}]

multiple_relative_product(TupleOfBinRels, BinRel1) -> BinRel2

类型

TupleOfBinRels = tuple_of(BinRel)

BinRel = BinRel1 = BinRel2 = binary_relation()

如果TupleOfBinRels是一个非空的元组{R [1],...,R [n]的}的二元关系和BinRel1是一个二元关系,然后BinRel2是多个相对的产品的有序集合的(R [I], ...,R [n])和BinRel1。

1> Ri = sofs:relation([{a,1},{b,2},{c,3}]),
R = sofs:relation([{a,b},{b,c},{c,a}]),
MP = sofs:multiple_relative_product({Ri, Ri}, R),
sofs:to_external(sofs:range(MP)).
[{1,2},{2,3},{3,1}]

no_elements(ASet) -> NoElements

类型

ASet = a_set() | ordset()

NoElements = integer() >= 0

返回有序或无序集合ASet的元素数量。

partition(SetOfSets) -> Partition

类型

SetOfSets = set_of_sets()

Partition = a_set()

返回SetOfSets集合的集合的分区,使得如果两个元素属于SetOfSets的相同元素,则认为这两个元素相等。

1> Sets1 = sofs:from_term([[a,b,c],[d,e,f],[g,h,i]]),
Sets2 = sofs:from_term([[b,c,d],[e,f,g],[h,i,j]]),
P = sofs:partition(sofs:union(Sets1, Sets2)),
sofs:to_external(P).
[[a],[b,c],[d],[e,f],[g],[h,i],[j]]

partition(SetFun, Set) -> Partition

类型

SetFun = set_fun()

Partition = Set = a_set()

返回SetOfSets集合的集合的分区,使得如果两个元素属于SetOfSets的相同元素,则认为这两个元素相等。

1> Ss = sofs:from_term([[a],[b],[c,d],[e,f]]),
SetFun = fun(S) -> sofs:from_term(sofs:no_elements(S)) end,
P = sofs:partition(SetFun, Ss),
sofs:to_external(P).
[[[a],[b]],[[c,d],[e,f]]]

partition(SetFun, Set1, Set2) -> {Set3, Set4}

类型

SetFun = set_fun()

Set1 = Set2 = Set3 = Set4 = a_set()

返回一对套的是,视为构成一组,形成分区的SET1。如果将SetFun应用于Set1的元素给出Set2中的元素,则该元素属于Set3,否则该元素属于Set4。

1> R1 = sofs:relation([{1,a},{2,b},{3,c}]),
S = sofs:set([2,4,6]),
{R2,R3} = sofs:partition(1, R1, S),
{sofs:to_external(R2),sofs:to_external(R3)}.
{[{2,b}],[{1,a},{3,c}]}

partition(F, S1, S2)相当于{restriction(F, S1, S2), drestriction(F, S1, S2)}。

partition_family(SetFun, Set) -> Family

类型

Family = family()

SetFun = set_fun()

Set = a_set()

返回family的家庭,其中索引集是一个分区的设置使得两个单元被认为相同,如果申请的结果SetFun是相同的值i。这是我家族映射到等价类的索引。

1> S = sofs:relation([{a,a,a,a},{a,a,b,b},{a,b,b,b}]),
SetFun = {external, fun({A,_,C,_}) -> {A,C} end},
F = sofs:partition_family(SetFun, S),
sofs:to_external(F).
[{{a,a},[{a,a,a,a}]},{{a,b},[{a,a,b,b},{a,b,b,b}]}]

product(TupleOfSets) -> Relation

类型

Relation = relation()

TupleOfSets = tuple_of(a_set())

返回TupleOfSets集合的非空元组的Cartesian乘积。如果(x [1],...,x [n])是n元关系Relation的元素,则x [i]从TupleOfSets的元素i中绘制。

1> S1 = sofs:set([a,b]),
S2 = sofs:set([1,2]),
S3 = sofs:set([x,y]),
P3 = sofs:product({S1,S2,S3}),
sofs:to_external(P3).
[{a,1,x},{a,1,y},{a,2,x},{a,2,y},{b,1,x},{b,1,y},{b,2,x},{b,2,y}]

product(Set1, Set2) -> BinRel

类型

BinRel = binary_relation()

Set1 = Set2 = a_set()

返回笛卡尔积的SET1和SET2。

1> S1 = sofs:set([1,2]),
S2 = sofs:set([a,b]),
R = sofs:product(S1, S2),
sofs:to_external(R).
[{1,a},{1,b},{2,a},{2,b}]

product(S1, S2)相当于product({S1, S2})。

projection(SetFun, Set1) -> Set2

类型

SetFun = set_fun()

Set1 = Set2 = a_set()

将通过将SetFun应用于元素的结果替换Set1的每个元素而创建 的集合。

如果SetFun是编号i> = 1,并且 SET1是一个关系,则返回的集合是投影的 SET1到坐标i。

1> S1 = sofs:from_term([{1,a},{2,b},{3,a}]),
S2 = sofs:projection(2, S1),
sofs:to_external(S2).
[a,b]

range(BinRel) -> Set

类型

BinRel = binary_relation()

Set = a_set()

返回二元关系BinRel的范围

1> R = sofs:relation([{1,a},{1,b},{2,b},{2,c}]),
S = sofs:range(R),
sofs:to_external(S).
[a,b,c]

relation(Tuples) -> Relation

relation(Tuples, Type) -> Relation

类型

N = integer()

Type = N | type()

Relation = relation()

Tuples = [tuple()]

创建一个关系。如果T是一个类型并且结果是关系,则关系(R,T)等同于from_term(R,T)。如果Type是整数N,则元组大小为N的[{atom,...,atom}])被用作关系的类型。如果没有显式指定类型,则使用元组的第一个元组的大小,如果有这样一个元组。关系([])等于关系([],2)。

relation_to_family(BinRel) -> Family

类型

Family = family()

BinRel = binary_relation()

返回family系列,使得索引集等于二进制关系BinRel的,而Family[i]是BinRel下的一组i的图像

1> R = sofs:relation([{b,1},{c,2},{c,3}]),
F = sofs:relation_to_family(R),
sofs:to_external(F).
[{b,[1]},{c,[2,3]}]

relative_product(ListOfBinRels) -> BinRel2

relative_product(ListOfBinRels, BinRel1) -> BinRel2

类型

ListOfBinRels = [BinRel, ...]

BinRel = BinRel1 = BinRel2 = binary_relation()

如果ListOfBinRels是二元关系的非空列表[R [1],...,R [n]]且 BinRel1 是二元关系,则BinRel2是 有序集合(R [i],... 的 相对乘积。 ..,R [n])和BinRel1。

如果省略BinRel1,则代之以使用范围R [i],范围R [1]×...×范围R [n] 的笛卡尔乘积的元素之间的相等关系(直观地,没有什么是“丢失”)。

1> TR = sofs:relation([{1,a},{1,aa},{2,b}]),
R1 = sofs:relation([{1,u},{2,v},{3,c}]),
R2 = sofs:relative_product([TR, R1]),
sofs:to_external(R2).
[{1,{a,u}},{1,{aa,u}},{2,{b,v}}]

请注意,relative_product([R1],R2)与relative_product(R1,R2)不同。一个元素的列表没有与元素本身一起标识。

relative_product(BinRel1, BinRel2) -> BinRel3

类型

BinRel1 = BinRel2 = BinRel3 = binary_relation()

返回二进制关系BinRel1和BinRel2的相对乘积

relative_product1(BinRel1, BinRel2) -> BinRel3

Types

BinRel1 = BinRel2 = BinRel3 = binary_relation()

返回相关产品的的相反的二元关系BinRel1和二元关系BinRel2。

1> R1 = sofs:relation([{1,a},{1,aa},{2,b}]),
R2 = sofs:relation([{1,u},{2,v},{3,c}]),
R3 = sofs:relative_product1(R1, R2),
sofs:to_external(R3).
[{a,u},{aa,u},{b,v}]

relative_product1(R1, R2)相当于relative_product(converse(R1), R2)。

restriction(BinRel1, Set) -> BinRel2

类型

BinRel1 = BinRel2 = binary_relation()

Set = a_set()

返回限制的二元关系BinRel1来设置。

1> R1 = sofs:relation([{1,a},{2,b},{3,c}]),
S = sofs:set([1,2,4]),
R2 = sofs:restriction(R1, S),
sofs:to_external(R2).
[{1,a},{2,b}]

restriction(SetFun, Set1, Set2) -> Set3

类型

SetFun = set_fun()

Set1 = Set2 = Set3 = a_set()

返回包含这些元素的Set1的子集,这些元素将Set2中的元素作为SetFun的结果提供给Set2中的元素。

1> S1 = sofs:relation([{1,a},{2,b},{3,c}]),
S2 = sofs:set([b,c,d]),
S3 = sofs:restriction(2, S1, S2),
sofs:to_external(S3).
[{2,b},{3,c}]

set(Terms) -> Set

set(Terms, Type) -> Set

类型

Set = a_set()

Terms = [term()]

Type = type()

创建一个无序集。如果结果是无序集合,则集合(L,T)等价于from_term(L,T)。如果没有明确指定类型,则使用[atom]作为集合类型。

specification(Fun, Set1) -> Set2

类型

Fun = spec_fun()

Set1 = Set2 = a_set()

返回包含Fun为其返回true的Set1的每个元素的集合。如果Fun是一个元组{外部,Fun2},则Fun2被应用于每个元素的外部集合,否则Fun被应用于每个元素。

1> R1 = sofs:relation([{a,1},{b,2}]),
R2 = sofs:relation([{x,1},{x,2},{y,3}]),
S1 = sofs:from_sets([R1,R2]),
S2 = sofs:specification(fun sofs:is_a_function/1, S1),
sofs:to_external(S2).
[[{a,1},{b,2}]]

strict_relation(BinRel1) -> BinRel2

类型

BinRel1 = BinRel2 = binary_relation()

返回与二进制关系BinRel1对应的严格关系

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

substitution(SetFun, Set1) -> Set2

类型

SetFun = set_fun()

Set1 = Set2 = a_set()

返回一个函数,其域为Set1。域的元素的值是将SetFun应用于元素的结果。

1> L = [{a,1},{b,2}].
[{a,1},{b,2}]
2> sofs:to_external(sofs:projection(1,sofs:relation(L))).
[a,b]
3> sofs:to_external(sofs:substitution(1,sofs:relation(L))).
[{{a,1},a},{{b,2},b}]
4> SetFun = {external, fun({A,_}=E) -> {E,A} end},
sofs:to_external(sofs:projection(SetFun,sofs:relation(L))).
[{{a,1},a},{{b,2},b}]

{a,b,c}元素之间的平等关系:

1> I = sofs:substitution(fun(A) -> A end, sofs:set([a,b,c])),
sofs:to_external(I).
[{a,a},{b,b},{c,c}]

让SetOfSets是一组集和BinRel的二元关系。每个元素映射功能设置的SetOfSets到图像的设置下BinRel由以下函数返回:

images(SetOfSets, BinRel) ->
   Fun = fun(Set) -> sofs:image(BinRel, Set) end,
   sofs:substitution(Fun, SetOfSets).

外部无序集表示为排序列表。因此,在关系R下创建集合的图像可以遍历R的所有元素(即结果排序,图像)。在image/2中,BinRel针对SetOfSets的每个元素遍历一次,这可能需要很长时间。下面的有效函数可以用来代替BinRel下的SetOfSets的每个元素的图像是非空的:

images2(SetOfSets, BinRel) ->
   CR = sofs:canonical_relation(SetOfSets),
   R = sofs:relative_product1(CR, BinRel),
   sofs:relation_to_family(R).

symdiff(Set1, Set2) -> Set3

类型

Set1 = Set2 = Set3 = a_set()

返回Set1和Set2的对称差分(或布尔和)。

1> S1 = sofs:set([1,2,3]),
S2 = sofs:set([2,3,4]),
P = sofs:symdiff(S1, S2),
sofs:to_external(P).
[1,4]

symmetric_partition(Set1, Set2) -> {Set3, Set4, Set5}

类型

Set1 = Set2 = Set3 = Set4 = Set5 = a_set()

返回一组三元组:

  • 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)

Erlang 20

Erlang 是一种通用的面向并发的编程语言,可应付大规模开发活动的程序设计语言和运行环境。

主页 https://www.erlang.org/
源码 https://github.com/erlang/otp
版本 20
发布版本 20.1