1sofs(3)                    Erlang Module Definition                    sofs(3)
2
3
4

NAME

6       sofs - Functions for manipulating sets of sets.
7

DESCRIPTION

9       This  module  provides  operations  on finite sets and relations repre‐
10       sented as sets. Intuitively, a set is a collection of  elements;  every
11       element belongs to the set, and the set contains every element.
12
13       Given  a  set  A and a sentence S(x), where x is a free variable, a new
14       set B whose elements are exactly those elements of  A  for  which  S(x)
15       holds can be formed, this is denoted B = {x in A : S(x)}. Sentences are
16       expressed using the logical operators "for some" (or  "there  exists"),
17       "for all", "and", "or", "not". If the existence of a set containing all
18       the specified elements is known (as is always the case in this module),
19       this is denoted B = {x : S(x)}.
20
21         * The  unordered  set  containing the elements a, b, and c is denoted
22           {a, b, c}. This notation is not to be confused with tuples.
23
24           The ordered pair of a and b, with first  coordinate  a  and  second
25           coordinate  b, is denoted (a, b). An ordered pair is an ordered set
26           of two elements. In this module, ordered sets can contain one, two,
27           or more elements, and parentheses are used to enclose the elements.
28
29           Unordered  sets and ordered sets are orthogonal, again in this mod‐
30           ule; there is no unordered set equal to any ordered set.
31
32         * The empty set contains no elements.
33
34           Set A is equal to set B if they contain the same elements, which is
35           denoted  A = B. Two ordered sets are equal if they contain the same
36           number of elements and have equal elements at each coordinate.
37
38           Set B is a subset of set A if A contains all elements that  B  con‐
39           tains.
40
41           The union of two sets A and B is the smallest set that contains all
42           elements of A and all elements of B.
43
44           The intersection of two sets A and B is the set that  contains  all
45           elements of A that belong to B.
46
47           Two sets are disjoint if their intersection is the empty set.
48
49           The  difference  of  two  sets A and B is the set that contains all
50           elements of A that do not belong to B.
51
52           The symmetric difference of two sets is the set that contains those
53           element that belong to either of the two sets, but not both.
54
55           The union of a collection of sets is the smallest set that contains
56           all the elements that belong to at least one set of the collection.
57
58           The intersection of a non-empty collection of sets is the set  that
59           contains all elements that belong to every set of the collection.
60
61         * The  Cartesian  product  of two sets X and Y, denoted X x Y, is the
62           set {a : a = (x, y) for some x in X and for some y in Y}.
63
64           A relation is a subset of X x Y. Let R be a relation. The fact that
65           (x, y) belongs to R is written as x R y. As relations are sets, the
66           definitions of the last item (subset, union, and so  on)  apply  to
67           relations as well.
68
69           The domain of R is the set {x : x R y for some y in Y}.
70
71           The range of R is the set {y : x R y for some x in X}.
72
73           The converse of R is the set {a : a = (y, x) for some (x, y) in R}.
74
75           If A is a subset of X, the image of A under R is the set {y : x R y
76           for some x in A}. If B is a subset of Y, the inverse image of B  is
77           the set {x : x R y for some y in B}.
78
79           If  R  is  a relation from X to Y, and S is a relation from Y to Z,
80           the relative product of R and S is the  relation  T  from  X  to  Z
81           defined so that x T z if and only if there exists an element y in Y
82           such that x R y and y S z.
83
84           The restriction of R to A is the set S defined so that x S y if and
85           only if there exists an element x in A such that x R y.
86
87           If S is a restriction of R to A, then R is an extension of S to X.
88
89           If X = Y, then R is called a relation in X.
90
91           The  field of a relation R in X is the union of the domain of R and
92           the range of R.
93
94           If R is a relation in X, and if S is defined so that x S y if x R y
95           and  not  x  = y, then S is the strict relation corresponding to R.
96           Conversely, if S is a relation in X, and if R is defined so that  x
97           R y if x S y or x = y, then R is the weak relation corresponding to
98           S.
99
100           A relation R in X is reflexive if x R x for every element x  of  X,
101           it  is  symmetric if x R y implies that y R x, and it is transitive
102           if x R y and y R z imply that x R z.
103
104         * A function F is a relation, a subset of X x Y, such that the domain
105           of F is equal to X and such that for every x in X there is a unique
106           element y in Y with (x, y) in F. The latter condition can be formu‐
107           lated  as  follows: if x F y and x F z, then y = z. In this module,
108           it is not required that the domain of F is equal to X for  a  rela‐
109           tion to be considered a function.
110
111           Instead  of  writing (x, y) in F or x F y, we write F(x) = y when F
112           is a function, and say that F maps x onto y, or that the value of F
113           at x is y.
114
115           As  functions  are  relations,  the  definitions  of  the last item
116           (domain, range, and so on) apply to functions as well.
117
118           If the converse of a function F is a function F', then F' is called
119           the inverse of F.
120
121           The  relative product of two functions F1 and F2 is called the com‐
122           posite of F1 and F2 if the range of F1 is a subset of the domain of
123           F2.
124
125         * Sometimes,  when the range of a function is more important than the
126           function itself, the function is called a family.
127
128           The domain of a family is called the index set, and  the  range  is
129           called the indexed set.
130
131           If  x  is  a family from I to X, then x[i] denotes the value of the
132           function at index i. The notation "a family in X" is used for  such
133           a family.
134
135           When  the  indexed  set is a set of subsets of a set X, we call x a
136           family of subsets of X.
137
138           If x is a family of subsets of X, the union of the range  of  x  is
139           called the union of the family x.
140
141           If x is non-empty (the index set is non-empty), the intersection of
142           the family x is the intersection of the range of x.
143
144           In this module, the only families that are considered are  families
145           of  subsets  of  some set X; in the following, the word "family" is
146           used for such families of subsets.
147
148         * A partition of a set X is a collection S of non-empty subsets of  X
149           whose union is X and whose elements are pairwise disjoint.
150
151           A  relation in a set is an equivalence relation if it is reflexive,
152           symmetric, and transitive.
153
154           If R is an equivalence relation in X, and x is an element of X, the
155           equivalence  class  of  x with respect to R is the set of all those
156           elements y of X for which x R y holds. The equivalence classes con‐
157           stitute  a partitioning of X. Conversely, if C is a partition of X,
158           the relation that holds for any two elements of X if they belong to
159           the  same  equivalence class, is an equivalence relation induced by
160           the partition C.
161
162           If R is an equivalence relation in X,  the  canonical  map  is  the
163           function that maps every element of X onto its equivalence class.
164
165         * Relations  as defined above (as sets of ordered pairs) are from now
166           on referred to as binary relations.
167
168           We call a set of ordered sets (x[1], ..., x[n])  an  (n-ary)  rela‐
169           tion,  and say that the relation is a subset of the Cartesian prod‐
170           uct X[1] x ... x X[n], where x[i] is an element of X[i], 1 <= i  <=
171           n.
172
173           The  projection of an n-ary relation R onto coordinate i is the set
174           {x[i] : (x[1], ..., x[i], ..., x[n]) in R for some x[j] in X[j],  1
175           <=  j  <=  n and not i = j}. The projections of a binary relation R
176           onto the first and second coordinates are the domain and the  range
177           of R, respectively.
178
179           The  relative  product of binary relations can be generalized to n-
180           ary relations as follows. Let TR be  an  ordered  set  (R[1],  ...,
181           R[n])  of  binary  relations from X to Y[i] and S a binary relation
182           from (Y[1] x ... x Y[n]) to Z. The relative product of TR and S  is
183           the binary relation T from X to Z defined so that x T z if and only
184           if there exists an element y[i] in Y[i] for each 1 <= i <=  n  such
185           that  x  R[i]  y[i]  and  (y[1], ..., y[n]) S z. Now let TR be a an
186           ordered set (R[1], ..., R[n]) of binary relations from X[i] to Y[i]
187           and  S a subset of X[1] x ... x X[n]. The multiple relative product
188           of TR and S is defined to be the set {z : z = ((x[1],  ...,  x[n]),
189           (y[1],...,y[n]))  for  some  (x[1],  ...,  x[n])  in S and for some
190           (x[i], y[i]) in R[i], 1 <= i <= n}.
191
192           The natural join of an n-ary relation R and an m-ary relation S  on
193           coordinate  i  and  j is defined to be the set {z : z = (x[1], ...,
194           x[n], y[1], ..., y[j-1], y[j+1], ..., y[m]) for  some  (x[1],  ...,
195           x[n])  in  R  and  for some (y[1], ..., y[m]) in S such that x[i] =
196           y[j]}.
197
198         * The sets recognized by this module are represented by  elements  of
199           the relation Sets, which is defined as the smallest set such that:
200
201           * For  every  atom  T,  except  '_',  and  for every term X, (T, X)
202             belongs to Sets (atomic sets).
203
204           * (['_'], []) belongs to Sets (the untyped empty set).
205
206           * For every tuple T = {T[1], ..., T[n]} and for  every  tuple  X  =
207             {X[1], ..., X[n]}, if (T[i], X[i]) belongs to Sets for every 1 <=
208             i <= n, then (T, X) belongs to Sets (ordered sets).
209
210           * For every term T, if X is the empty list or  a  non-empty  sorted
211             list  [X[1],  ...,  X[n]]  without duplicates such that (T, X[i])
212             belongs to Sets for every 1 <= i <= n, then ([T], X)  belongs  to
213             Sets (typed unordered sets).
214
215           An external set is an element of the range of Sets.
216
217           A type is an element of the domain of Sets.
218
219           If  S  is an element (T, X) of Sets, then T is a valid type of X, T
220           is the type of S, and X is the external set of S. from_term/2  cre‐
221           ates  a  set from a type and an Erlang term turned into an external
222           set.
223
224           The sets represented by Sets are the elements of the range of func‐
225           tion Set from Sets to Erlang terms and sets of Erlang terms:
226
227           * Set(T,Term) = Term, where T is an atom
228
229           * Set({T[1],  ...,  T[n]},  {X[1],  ..., X[n]}) = (Set(T[1], X[1]),
230             ..., Set(T[n], X[n]))
231
232           * Set([T], [X[1], ..., X[n]]) = {Set(T, X[1]), ..., Set(T, X[n])}
233
234           * Set([T], []) = {}
235
236           When there is no risk of confusion, elements of Sets are identified
237           with  the  sets  they represent. For example, if U is the result of
238           calling union/2 with S1 and S2 as arguments, then U is said  to  be
239           the  union  of S1 and S2. A more precise formulation is that Set(U)
240           is the union of Set(S1) and Set(S2).
241
242       The types are used to implement the various conditions that  sets  must
243       fulfill. As an example, consider the relative product of two sets R and
244       S, and recall that the relative product of R and S is defined if R is a
245       binary  relation  to  Y and S is a binary relation from Y. The function
246       that implements the relative product, relative_product/2,  checks  that
247       the  arguments  represent  binary relations by matching [{A,B}] against
248       the type of the first argument (Arg1 say), and [{C,D}] against the type
249       of  the  second  argument (Arg2 say). The fact that [{A,B}] matches the
250       type of Arg1 is to be interpreted as Arg1 representing a  binary  rela‐
251       tion  from  X to Y, where X is defined as all sets Set(x) for some ele‐
252       ment x in Sets the type of which is A, and similarly for Y. In the same
253       way  Arg2 is interpreted as representing a binary relation from W to Z.
254       Finally it is checked that B matches C, which is sufficient  to  ensure
255       that  W is equal to Y. The untyped empty set is handled separately: its
256       type, ['_'], matches the type of any unordered set.
257
258       A few functions of this  module  (drestriction/3,  family_projection/2,
259       partition/2, partition_family/2, projection/2, restriction/3, substitu‐
260       tion/2) accept an Erlang function as a means to modify each element  of
261       a given unordered set. Such a function, called SetFun in the following,
262       can be specified as a functional object (fun), a tuple {external, Fun},
263       or an integer:
264
265         * If SetFun is specified as a fun, the fun is applied to each element
266           of the given set and the return value is assumed to be a set.
267
268         * If SetFun is specified as a tuple {external, Fun}, Fun  is  applied
269           to the external set of each element of the given set and the return
270           value is assumed to be an external set. Selecting the  elements  of
271           an  unordered  set  as external sets and assembling a new unordered
272           set from a list of external sets is in the  present  implementation
273           more  efficient than modifying each element as a set. However, this
274           optimization can only be used when the elements  of  the  unordered
275           set  are  atomic or ordered sets. It must also be the case that the
276           type of the elements matches some clause of Fun (the  type  of  the
277           created  set is the result of applying Fun to the type of the given
278           set), and that Fun does  nothing  but  selecting,  duplicating,  or
279           rearranging parts of the elements.
280
281         * Specifying  a  SetFun  as  an integer I is equivalent to specifying
282           {external, fun(X) -> element(I, X) end}, but is to be preferred, as
283           it makes it possible to handle this case even more efficiently.
284
285       Examples of SetFuns:
286
287       fun sofs:union/1
288       fun(S) -> sofs:partition(1, S) end
289       {external, fun(A) -> A end}
290       {external, fun({A,_,C}) -> {C,A} end}
291       {external, fun({_,{_,C}}) -> C end}
292       {external, fun({_,{_,{_,E}=C}}) -> {E,{E,C}} end}
293       2
294
295       The  order in which a SetFun is applied to the elements of an unordered
296       set is not specified, and can change in future versions of this module.
297
298       The execution time of the functions of this module is dominated by  the
299       time  it  takes to sort lists. When no sorting is needed, the execution
300       time is in the worst case proportional to the sum of the sizes  of  the
301       input arguments and the returned value. A few functions execute in con‐
302       stant time: from_external/2, is_empty_set/1,  is_set/1,  is_sofs_set/1,
303       to_external/1 type/1.
304
305       The  functions of this module exit the process with a badarg, bad_func‐
306       tion, or type_mismatch message when given  badly  formed  arguments  or
307       sets the types of which are not compatible.
308
309       When comparing external sets, operator ==/2 is used.
310

DATA TYPES

312       anyset() = ordset() | a_set()
313
314              Any kind of set (also included are the atomic sets).
315
316       binary_relation() = relation()
317
318              A binary relation.
319
320       external_set() = term()
321
322              An external set.
323
324       family() = a_function()
325
326              A family (of subsets).
327
328       a_function() = relation()
329
330              A function.
331
332       ordset()
333
334              An ordered set.
335
336       relation() = a_set()
337
338              An n-ary relation.
339
340       a_set()
341
342              An unordered set.
343
344       set_of_sets() = a_set()
345
346              An unordered set of unordered sets.
347
348       set_fun() =
349           integer() >= 1 |
350           {external, fun((external_set()) -> external_set())} |
351           fun((anyset()) -> anyset())
352
353              A SetFun.
354
355       spec_fun() =
356           {external, fun((external_set()) -> boolean())} |
357           fun((anyset()) -> boolean())
358
359       type() = term()
360
361              A type.
362
363       tuple_of(T)
364
365              A tuple where the elements are of type T.
366

EXPORTS

368       a_function(Tuples) -> Function
369
370       a_function(Tuples, Type) -> Function
371
372              Types:
373
374                 Function = a_function()
375                 Tuples = [tuple()]
376                 Type = type()
377
378              Creates   a   function.   a_function(F,   T)  is  equivalent  to
379              from_term(F, T) if the result is  a  function.  If  no  type  is
380              explicitly  specified,  [{atom,  atom}]  is used as the function
381              type.
382
383       canonical_relation(SetOfSets) -> BinRel
384
385              Types:
386
387                 BinRel = binary_relation()
388                 SetOfSets = set_of_sets()
389
390              Returns the binary relation containing  the  elements  (E,  Set)
391              such  that  Set  belongs  to  SetOfSets and E belongs to Set. If
392              SetOfSets is a partition of a set X and  R  is  the  equivalence
393              relation  in  X induced by SetOfSets, then the returned relation
394              is the canonical map from X onto the  equivalence  classes  with
395              respect to R.
396
397              1> Ss = sofs:from_term([[a,b],[b,c]]),
398              CR = sofs:canonical_relation(Ss),
399              sofs:to_external(CR).
400              [{a,[a,b]},{b,[a,b]},{b,[b,c]},{c,[b,c]}]
401
402       composite(Function1, Function2) -> Function3
403
404              Types:
405
406                 Function1 = Function2 = Function3 = a_function()
407
408              Returns the composite of the functions Function1 and Function2.
409
410              1> F1 = sofs:a_function([{a,1},{b,2},{c,2}]),
411              F2 = sofs:a_function([{1,x},{2,y},{3,z}]),
412              F = sofs:composite(F1, F2),
413              sofs:to_external(F).
414              [{a,x},{b,y},{c,y}]
415
416       constant_function(Set, AnySet) -> Function
417
418              Types:
419
420                 AnySet = anyset()
421                 Function = a_function()
422                 Set = a_set()
423
424              Creates the function that maps each element of set Set onto Any‐
425              Set.
426
427              1> S = sofs:set([a,b]),
428              E = sofs:from_term(1),
429              R = sofs:constant_function(S, E),
430              sofs:to_external(R).
431              [{a,1},{b,1}]
432
433       converse(BinRel1) -> BinRel2
434
435              Types:
436
437                 BinRel1 = BinRel2 = binary_relation()
438
439              Returns the converse of the binary relation BinRel1.
440
441              1> R1 = sofs:relation([{1,a},{2,b},{3,a}]),
442              R2 = sofs:converse(R1),
443              sofs:to_external(R2).
444              [{a,1},{a,3},{b,2}]
445
446       difference(Set1, Set2) -> Set3
447
448              Types:
449
450                 Set1 = Set2 = Set3 = a_set()
451
452              Returns the difference of the sets Set1 and Set2.
453
454       digraph_to_family(Graph) -> Family
455
456       digraph_to_family(Graph, Type) -> Family
457
458              Types:
459
460                 Graph = digraph:graph()
461                 Family = family()
462                 Type = type()
463
464              Creates a family from the directed graph Graph. Each vertex a of
465              Graph is represented by a pair (a, {b[1], ..., b[n]}), where the
466              b[i]:s are the out-neighbors of a.  If  no  type  is  explicitly
467              specified, [{atom, [atom]}] is used as type of the family. It is
468              assumed that Type is a valid type of the  external  set  of  the
469              family.
470
471              If  G  is a directed graph, it holds that the vertices and edges
472              of  G  are  the  same  as  the  vertices  and  edges   of   fam‐
473              ily_to_digraph(digraph_to_family(G)).
474
475       domain(BinRel) -> Set
476
477              Types:
478
479                 BinRel = binary_relation()
480                 Set = a_set()
481
482              Returns the domain of the binary relation BinRel.
483
484              1> R = sofs:relation([{1,a},{1,b},{2,b},{2,c}]),
485              S = sofs:domain(R),
486              sofs:to_external(S).
487              [1,2]
488
489       drestriction(BinRel1, Set) -> BinRel2
490
491              Types:
492
493                 BinRel1 = BinRel2 = binary_relation()
494                 Set = a_set()
495
496              Returns  the  difference between the binary relation BinRel1 and
497              the restriction of BinRel1 to Set.
498
499              1> R1 = sofs:relation([{1,a},{2,b},{3,c}]),
500              S = sofs:set([2,4,6]),
501              R2 = sofs:drestriction(R1, S),
502              sofs:to_external(R2).
503              [{1,a},{3,c}]
504
505              drestriction(R, S) is equivalent to difference(R, restriction(R,
506              S)).
507
508       drestriction(SetFun, Set1, Set2) -> Set3
509
510              Types:
511
512                 SetFun = set_fun()
513                 Set1 = Set2 = Set3 = a_set()
514
515              Returns  a  subset of Set1 containing those elements that do not
516              give an element in Set2 as the result of applying SetFun.
517
518              1> SetFun = {external, fun({_A,B,C}) -> {B,C} end},
519              R1 = sofs:relation([{a,aa,1},{b,bb,2},{c,cc,3}]),
520              R2 = sofs:relation([{bb,2},{cc,3},{dd,4}]),
521              R3 = sofs:drestriction(SetFun, R1, R2),
522              sofs:to_external(R3).
523              [{a,aa,1}]
524
525              drestriction(F, S1, S2) is equivalent to difference(S1, restric‐
526              tion(F, S1, S2)).
527
528       empty_set() -> Set
529
530              Types:
531
532                 Set = a_set()
533
534              Returns  the  untyped  empty  set.  empty_set() is equivalent to
535              from_term([], ['_']).
536
537       extension(BinRel1, Set, AnySet) -> BinRel2
538
539              Types:
540
541                 AnySet = anyset()
542                 BinRel1 = BinRel2 = binary_relation()
543                 Set = a_set()
544
545              Returns the extension of BinRel1 such that for each element E in
546              Set  that does not belong to the domain of BinRel1, BinRel2 con‐
547              tains the pair (E, AnySet).
548
549              1> S = sofs:set([b,c]),
550              A = sofs:empty_set(),
551              R = sofs:family([{a,[1,2]},{b,[3]}]),
552              X = sofs:extension(R, S, A),
553              sofs:to_external(X).
554              [{a,[1,2]},{b,[3]},{c,[]}]
555
556       family(Tuples) -> Family
557
558       family(Tuples, Type) -> Family
559
560              Types:
561
562                 Family = family()
563                 Tuples = [tuple()]
564                 Type = type()
565
566              Creates a family of  subsets.  family(F,  T)  is  equivalent  to
567              from_term(F, T) if the result is a family. If no type is explic‐
568              itly specified, [{atom, [atom]}] is used as the family type.
569
570       family_difference(Family1, Family2) -> Family3
571
572              Types:
573
574                 Family1 = Family2 = Family3 = family()
575
576              If Family1 and Family2 are families, then Family3 is the  family
577              such  that  the  index set is equal to the index set of Family1,
578              and Family3[i] is the difference  between  Family1[i]  and  Fam‐
579              ily2[i] if Family2 maps i, otherwise Family1[i].
580
581              1> F1 = sofs:family([{a,[1,2]},{b,[3,4]}]),
582              F2 = sofs:family([{b,[4,5]},{c,[6,7]}]),
583              F3 = sofs:family_difference(F1, F2),
584              sofs:to_external(F3).
585              [{a,[1,2]},{b,[3]}]
586
587       family_domain(Family1) -> Family2
588
589              Types:
590
591                 Family1 = Family2 = family()
592
593              If  Family1  is a family and Family1[i] is a binary relation for
594              every i in the index set of Family1, then Family2 is the  family
595              with  the  same index set as Family1 such that Family2[i] is the
596              domain of Family1[i].
597
598              1> FR = sofs:from_term([{a,[{1,a},{2,b},{3,c}]},{b,[]},{c,[{4,d},{5,e}]}]),
599              F = sofs:family_domain(FR),
600              sofs:to_external(F).
601              [{a,[1,2,3]},{b,[]},{c,[4,5]}]
602
603       family_field(Family1) -> Family2
604
605              Types:
606
607                 Family1 = Family2 = family()
608
609              If Family1 is a family and Family1[i] is a binary  relation  for
610              every  i in the index set of Family1, then Family2 is the family
611              with the same index set as Family1 such that Family2[i]  is  the
612              field of Family1[i].
613
614              1> FR = sofs:from_term([{a,[{1,a},{2,b},{3,c}]},{b,[]},{c,[{4,d},{5,e}]}]),
615              F = sofs:family_field(FR),
616              sofs:to_external(F).
617              [{a,[1,2,3,a,b,c]},{b,[]},{c,[4,5,d,e]}]
618
619              family_field(Family1)   is   equivalent   to   family_union(fam‐
620              ily_domain(Family1), family_range(Family1)).
621
622       family_intersection(Family1) -> Family2
623
624              Types:
625
626                 Family1 = Family2 = family()
627
628              If Family1 is a family and Family1[i] is a set of sets for every
629              i  in  the index set of Family1, then Family2 is the family with
630              the same index set as Family1 such that Family2[i] is the inter‐
631              section of Family1[i].
632
633              If Family1[i] is an empty set for some i, the process exits with
634              a badarg message.
635
636              1> F1 = sofs:from_term([{a,[[1,2,3],[2,3,4]]},{b,[[x,y,z],[x,y]]}]),
637              F2 = sofs:family_intersection(F1),
638              sofs:to_external(F2).
639              [{a,[2,3]},{b,[x,y]}]
640
641       family_intersection(Family1, Family2) -> Family3
642
643              Types:
644
645                 Family1 = Family2 = Family3 = family()
646
647              If Family1 and Family2 are families, then Family3 is the  family
648              such  that  the  index  set is the intersection of Family1:s and
649              Family2:s index sets, and Family3[i] is the intersection of Fam‐
650              ily1[i] and Family2[i].
651
652              1> F1 = sofs:family([{a,[1,2]},{b,[3,4]},{c,[5,6]}]),
653              F2 = sofs:family([{b,[4,5]},{c,[7,8]},{d,[9,10]}]),
654              F3 = sofs:family_intersection(F1, F2),
655              sofs:to_external(F3).
656              [{b,[4]},{c,[]}]
657
658       family_projection(SetFun, Family1) -> Family2
659
660              Types:
661
662                 SetFun = set_fun()
663                 Family1 = Family2 = family()
664
665              If Family1 is a family, then Family2 is the family with the same
666              index set as Family1 such that Family2[i] is the result of call‐
667              ing SetFun with Family1[i] as argument.
668
669              1> F1 = sofs:from_term([{a,[[1,2],[2,3]]},{b,[[]]}]),
670              F2 = sofs:family_projection(fun sofs:union/1, F1),
671              sofs:to_external(F2).
672              [{a,[1,2,3]},{b,[]}]
673
674       family_range(Family1) -> Family2
675
676              Types:
677
678                 Family1 = Family2 = family()
679
680              If  Family1  is a family and Family1[i] is a binary relation for
681              every i in the index set of Family1, then Family2 is the  family
682              with  the  same index set as Family1 such that Family2[i] is the
683              range of Family1[i].
684
685              1> FR = sofs:from_term([{a,[{1,a},{2,b},{3,c}]},{b,[]},{c,[{4,d},{5,e}]}]),
686              F = sofs:family_range(FR),
687              sofs:to_external(F).
688              [{a,[a,b,c]},{b,[]},{c,[d,e]}]
689
690       family_specification(Fun, Family1) -> Family2
691
692              Types:
693
694                 Fun = spec_fun()
695                 Family1 = Family2 = family()
696
697              If Family1 is a family, then Family2 is the restriction of  Fam‐
698              ily1  to those elements i of the index set for which Fun applied
699              to Family1[i] returns true. If Fun is a tuple {external,  Fun2},
700              then  Fun2  is applied to the external set of Family1[i], other‐
701              wise Fun is applied to Family1[i].
702
703              1> F1 = sofs:family([{a,[1,2,3]},{b,[1,2]},{c,[1]}]),
704              SpecFun = fun(S) -> sofs:no_elements(S) =:= 2 end,
705              F2 = sofs:family_specification(SpecFun, F1),
706              sofs:to_external(F2).
707              [{b,[1,2]}]
708
709       family_to_digraph(Family) -> Graph
710
711       family_to_digraph(Family, GraphType) -> Graph
712
713              Types:
714
715                 Graph = digraph:graph()
716                 Family = family()
717                 GraphType = [digraph:d_type()]
718
719              Creates a directed graph from family Family. For each  pair  (a,
720              {b[1],  ...,  b[n]}) of Family, vertex a and the edges (a, b[i])
721              for 1 <= i <= n are added to a newly created directed graph.
722
723              If no graph type is specified, digraph:new/0 is used for  creat‐
724              ing  the  directed graph, otherwise argument GraphType is passed
725              on as second argument to digraph:new/1.
726
727              It F is a family, it holds that F is a subset of digraph_to_fam‐
728              ily(family_to_digraph(F),    type(F)).    Equality    holds   if
729              union_of_family(F) is a subset of domain(F).
730
731              Creating a cycle in an acyclic graph exits the  process  with  a
732              cyclic message.
733
734       family_to_relation(Family) -> BinRel
735
736              Types:
737
738                 Family = family()
739                 BinRel = binary_relation()
740
741              If  Family  is a family, then BinRel is the binary relation con‐
742              taining all pairs (i, x) such that i belongs to the index set of
743              Family and x belongs to Family[i].
744
745              1> F = sofs:family([{a,[]}, {b,[1]}, {c,[2,3]}]),
746              R = sofs:family_to_relation(F),
747              sofs:to_external(R).
748              [{b,1},{c,2},{c,3}]
749
750       family_union(Family1) -> Family2
751
752              Types:
753
754                 Family1 = Family2 = family()
755
756              If  Family1 is a family and Family1[i] is a set of sets for each
757              i in the index set of Family1, then Family2 is the  family  with
758              the  same index set as Family1 such that Family2[i] is the union
759              of Family1[i].
760
761              1> F1 = sofs:from_term([{a,[[1,2],[2,3]]},{b,[[]]}]),
762              F2 = sofs:family_union(F1),
763              sofs:to_external(F2).
764              [{a,[1,2,3]},{b,[]}]
765
766              family_union(F)   is   equivalent    to    family_projection(fun
767              sofs:union/1, F).
768
769       family_union(Family1, Family2) -> Family3
770
771              Types:
772
773                 Family1 = Family2 = Family3 = family()
774
775              If  Family1 and Family2 are families, then Family3 is the family
776              such that the index set is the union of Family1:s and  Family2:s
777              index  sets,  and Family3[i] is the union of Family1[i] and Fam‐
778              ily2[i] if both map i, otherwise Family1[i] or Family2[i].
779
780              1> F1 = sofs:family([{a,[1,2]},{b,[3,4]},{c,[5,6]}]),
781              F2 = sofs:family([{b,[4,5]},{c,[7,8]},{d,[9,10]}]),
782              F3 = sofs:family_union(F1, F2),
783              sofs:to_external(F3).
784              [{a,[1,2]},{b,[3,4,5]},{c,[5,6,7,8]},{d,[9,10]}]
785
786       field(BinRel) -> Set
787
788              Types:
789
790                 BinRel = binary_relation()
791                 Set = a_set()
792
793              Returns the field of the binary relation BinRel.
794
795              1> R = sofs:relation([{1,a},{1,b},{2,b},{2,c}]),
796              S = sofs:field(R),
797              sofs:to_external(S).
798              [1,2,a,b,c]
799
800              field(R) is equivalent to union(domain(R), range(R)).
801
802       from_external(ExternalSet, Type) -> AnySet
803
804              Types:
805
806                 ExternalSet = external_set()
807                 AnySet = anyset()
808                 Type = type()
809
810              Creates a set from the external set  ExternalSet  and  the  type
811              Type. It is assumed that Type is a valid type of ExternalSet.
812
813       from_sets(ListOfSets) -> Set
814
815              Types:
816
817                 Set = a_set()
818                 ListOfSets = [anyset()]
819
820              Returns  the  unordered  set containing the sets of list ListOf‐
821              Sets.
822
823              1> S1 = sofs:relation([{a,1},{b,2}]),
824              S2 = sofs:relation([{x,3},{y,4}]),
825              S = sofs:from_sets([S1,S2]),
826              sofs:to_external(S).
827              [[{a,1},{b,2}],[{x,3},{y,4}]]
828
829       from_sets(TupleOfSets) -> Ordset
830
831              Types:
832
833                 Ordset = ordset()
834                 TupleOfSets = tuple_of(anyset())
835
836              Returns the ordered set containing the  sets  of  the  non-empty
837              tuple TupleOfSets.
838
839       from_term(Term) -> AnySet
840
841       from_term(Term, Type) -> AnySet
842
843              Types:
844
845                 AnySet = anyset()
846                 Term = term()
847                 Type = type()
848
849              Creates  an  element  of  Sets  by traversing term Term, sorting
850              lists, removing duplicates, and deriving or  verifying  a  valid
851              type  for  the so obtained external set. An explicitly specified
852              type Type can be used to limit the depth of  the  traversal;  an
853              atomic type stops the traversal, as shown by the following exam‐
854              ple where "foo" and {"foo"} are left unmodified:
855
856              1> S = sofs:from_term([{{"foo"},[1,1]},{"foo",[2,2]}], [{atom,[atom]}]),
857              sofs:to_external(S).
858              [{{"foo"},[1]},{"foo",[2]}]
859
860              from_term can be used for creating atomic or ordered  sets.  The
861              only  purpose  of such a set is that of later building unordered
862              sets, as all functions in this module that do  anything  operate
863              on  unordered sets. Creating unordered sets from a collection of
864              ordered sets can be the way to go if the ordered  sets  are  big
865              and  one  does not want to waste heap by rebuilding the elements
866              of the unordered set. The following example shows that a set can
867              be built "layer by layer":
868
869              1> A = sofs:from_term(a),
870              S = sofs:set([1,2,3]),
871              P1 = sofs:from_sets({A,S}),
872              P2 = sofs:from_term({b,[6,5,4]}),
873              Ss = sofs:from_sets([P1,P2]),
874              sofs:to_external(Ss).
875              [{a,[1,2,3]},{b,[4,5,6]}]
876
877              Other   functions  that  create  sets  are  from_external/2  and
878              from_sets/1. Special cases of  from_term/2  are  a_function/1,2,
879              empty_set/0, family/1,2, relation/1,2, and set/1,2.
880
881       image(BinRel, Set1) -> Set2
882
883              Types:
884
885                 BinRel = binary_relation()
886                 Set1 = Set2 = a_set()
887
888              Returns the image of set Set1 under the binary relation BinRel.
889
890              1> R = sofs:relation([{1,a},{2,b},{2,c},{3,d}]),
891              S1 = sofs:set([1,2]),
892              S2 = sofs:image(R, S1),
893              sofs:to_external(S2).
894              [a,b,c]
895
896       intersection(SetOfSets) -> Set
897
898              Types:
899
900                 Set = a_set()
901                 SetOfSets = set_of_sets()
902
903              Returns the intersection of the set of sets SetOfSets.
904
905              Intersecting  an  empty  set  of  sets  exits the process with a
906              badarg message.
907
908       intersection(Set1, Set2) -> Set3
909
910              Types:
911
912                 Set1 = Set2 = Set3 = a_set()
913
914              Returns the intersection of Set1 and Set2.
915
916       intersection_of_family(Family) -> Set
917
918              Types:
919
920                 Family = family()
921                 Set = a_set()
922
923              Returns the intersection of family Family.
924
925              Intersecting an empty family exits the  process  with  a  badarg
926              message.
927
928              1> F = sofs:family([{a,[0,2,4]},{b,[0,1,2]},{c,[2,3]}]),
929              S = sofs:intersection_of_family(F),
930              sofs:to_external(S).
931              [2]
932
933       inverse(Function1) -> Function2
934
935              Types:
936
937                 Function1 = Function2 = a_function()
938
939              Returns the inverse of function Function1.
940
941              1> R1 = sofs:relation([{1,a},{2,b},{3,c}]),
942              R2 = sofs:inverse(R1),
943              sofs:to_external(R2).
944              [{a,1},{b,2},{c,3}]
945
946       inverse_image(BinRel, Set1) -> Set2
947
948              Types:
949
950                 BinRel = binary_relation()
951                 Set1 = Set2 = a_set()
952
953              Returns the inverse image of Set1 under the binary relation Bin‐
954              Rel.
955
956              1> R = sofs:relation([{1,a},{2,b},{2,c},{3,d}]),
957              S1 = sofs:set([c,d,e]),
958              S2 = sofs:inverse_image(R, S1),
959              sofs:to_external(S2).
960              [2,3]
961
962       is_a_function(BinRel) -> Bool
963
964              Types:
965
966                 Bool = boolean()
967                 BinRel = binary_relation()
968
969              Returns true if the binary relation BinRel is a function or  the
970              untyped empty set, otherwise false.
971
972       is_disjoint(Set1, Set2) -> Bool
973
974              Types:
975
976                 Bool = boolean()
977                 Set1 = Set2 = a_set()
978
979              Returns true if Set1 and Set2 are disjoint, otherwise false.
980
981       is_empty_set(AnySet) -> Bool
982
983              Types:
984
985                 AnySet = anyset()
986                 Bool = boolean()
987
988              Returns  true  if  AnySet  is  an empty unordered set, otherwise
989              false.
990
991       is_equal(AnySet1, AnySet2) -> Bool
992
993              Types:
994
995                 AnySet1 = AnySet2 = anyset()
996                 Bool = boolean()
997
998              Returns true if AnySet1 and AnySet2 are equal, otherwise  false.
999              The  following  example  shows  that ==/2 is used when comparing
1000              sets for equality:
1001
1002              1> S1 = sofs:set([1.0]),
1003              S2 = sofs:set([1]),
1004              sofs:is_equal(S1, S2).
1005              true
1006
1007       is_set(AnySet) -> Bool
1008
1009              Types:
1010
1011                 AnySet = anyset()
1012                 Bool = boolean()
1013
1014              Returns true if AnySet is an unordered set, and false if  AnySet
1015              is an ordered set or an atomic set.
1016
1017       is_sofs_set(Term) -> Bool
1018
1019              Types:
1020
1021                 Bool = boolean()
1022                 Term = term()
1023
1024              Returns  true if Term is an unordered set, an ordered set, or an
1025              atomic set, otherwise false.
1026
1027       is_subset(Set1, Set2) -> Bool
1028
1029              Types:
1030
1031                 Bool = boolean()
1032                 Set1 = Set2 = a_set()
1033
1034              Returns true if Set1 is a subset of Set2, otherwise false.
1035
1036       is_type(Term) -> Bool
1037
1038              Types:
1039
1040                 Bool = boolean()
1041                 Term = term()
1042
1043              Returns true if term Term is a type.
1044
1045       join(Relation1, I, Relation2, J) -> Relation3
1046
1047              Types:
1048
1049                 Relation1 = Relation2 = Relation3 = relation()
1050                 I = J = integer() >= 1
1051
1052              Returns the natural join of the relations  Relation1  and  Rela‐
1053              tion2 on coordinates I and J.
1054
1055              1> R1 = sofs:relation([{a,x,1},{b,y,2}]),
1056              R2 = sofs:relation([{1,f,g},{1,h,i},{2,3,4}]),
1057              J = sofs:join(R1, 3, R2, 1),
1058              sofs:to_external(J).
1059              [{a,x,1,f,g},{a,x,1,h,i},{b,y,2,3,4}]
1060
1061       multiple_relative_product(TupleOfBinRels, BinRel1) -> BinRel2
1062
1063              Types:
1064
1065                 TupleOfBinRels = tuple_of(BinRel)
1066                 BinRel = BinRel1 = BinRel2 = binary_relation()
1067
1068              If  TupleOfBinRels  is  a  non-empty  tuple {R[1], ..., R[n]} of
1069              binary relations and BinRel1 is a binary relation, then  BinRel2
1070              is  the multiple relative product of the ordered set (R[i], ...,
1071              R[n]) and BinRel1.
1072
1073              1> Ri = sofs:relation([{a,1},{b,2},{c,3}]),
1074              R = sofs:relation([{a,b},{b,c},{c,a}]),
1075              MP = sofs:multiple_relative_product({Ri, Ri}, R),
1076              sofs:to_external(sofs:range(MP)).
1077              [{1,2},{2,3},{3,1}]
1078
1079       no_elements(ASet) -> NoElements
1080
1081              Types:
1082
1083                 ASet = a_set() | ordset()
1084                 NoElements = integer() >= 0
1085
1086              Returns the number of elements of the ordered or  unordered  set
1087              ASet.
1088
1089       partition(SetOfSets) -> Partition
1090
1091              Types:
1092
1093                 SetOfSets = set_of_sets()
1094                 Partition = a_set()
1095
1096              Returns  the partition of the union of the set of sets SetOfSets
1097              such that two elements are considered equal if  they  belong  to
1098              the same elements of SetOfSets.
1099
1100              1> Sets1 = sofs:from_term([[a,b,c],[d,e,f],[g,h,i]]),
1101              Sets2 = sofs:from_term([[b,c,d],[e,f,g],[h,i,j]]),
1102              P = sofs:partition(sofs:union(Sets1, Sets2)),
1103              sofs:to_external(P).
1104              [[a],[b,c],[d],[e,f],[g],[h,i],[j]]
1105
1106       partition(SetFun, Set) -> Partition
1107
1108              Types:
1109
1110                 SetFun = set_fun()
1111                 Partition = Set = a_set()
1112
1113              Returns  the partition of Set such that two elements are consid‐
1114              ered equal if the results of applying SetFun are equal.
1115
1116              1> Ss = sofs:from_term([[a],[b],[c,d],[e,f]]),
1117              SetFun = fun(S) -> sofs:from_term(sofs:no_elements(S)) end,
1118              P = sofs:partition(SetFun, Ss),
1119              sofs:to_external(P).
1120              [[[a],[b]],[[c,d],[e,f]]]
1121
1122       partition(SetFun, Set1, Set2) -> {Set3, Set4}
1123
1124              Types:
1125
1126                 SetFun = set_fun()
1127                 Set1 = Set2 = Set3 = Set4 = a_set()
1128
1129              Returns a pair of sets that, regarded  as  constituting  a  set,
1130              forms  a  partition of Set1. If the result of applying SetFun to
1131              an element of Set1 gives an element in Set2, the element belongs
1132              to Set3, otherwise the element belongs to Set4.
1133
1134              1> R1 = sofs:relation([{1,a},{2,b},{3,c}]),
1135              S = sofs:set([2,4,6]),
1136              {R2,R3} = sofs:partition(1, R1, S),
1137              {sofs:to_external(R2),sofs:to_external(R3)}.
1138              {[{2,b}],[{1,a},{3,c}]}
1139
1140              partition(F,  S1,  S2) is equivalent to {restriction(F, S1, S2),
1141              drestriction(F, S1, S2)}.
1142
1143       partition_family(SetFun, Set) -> Family
1144
1145              Types:
1146
1147                 Family = family()
1148                 SetFun = set_fun()
1149                 Set = a_set()
1150
1151              Returns family Family where the indexed set is  a  partition  of
1152              Set  such  that two elements are considered equal if the results
1153              of applying SetFun are the same value i. This  i  is  the  index
1154              that Family maps onto the equivalence class.
1155
1156              1> S = sofs:relation([{a,a,a,a},{a,a,b,b},{a,b,b,b}]),
1157              SetFun = {external, fun({A,_,C,_}) -> {A,C} end},
1158              F = sofs:partition_family(SetFun, S),
1159              sofs:to_external(F).
1160              [{{a,a},[{a,a,a,a}]},{{a,b},[{a,a,b,b},{a,b,b,b}]}]
1161
1162       product(TupleOfSets) -> Relation
1163
1164              Types:
1165
1166                 Relation = relation()
1167                 TupleOfSets = tuple_of(a_set())
1168
1169              Returns  the  Cartesian  product  of the non-empty tuple of sets
1170              TupleOfSets. If (x[1], ..., x[n]) is an  element  of  the  n-ary
1171              relation Relation, then x[i] is drawn from element i of TupleOf‐
1172              Sets.
1173
1174              1> S1 = sofs:set([a,b]),
1175              S2 = sofs:set([1,2]),
1176              S3 = sofs:set([x,y]),
1177              P3 = sofs:product({S1,S2,S3}),
1178              sofs:to_external(P3).
1179              [{a,1,x},{a,1,y},{a,2,x},{a,2,y},{b,1,x},{b,1,y},{b,2,x},{b,2,y}]
1180
1181       product(Set1, Set2) -> BinRel
1182
1183              Types:
1184
1185                 BinRel = binary_relation()
1186                 Set1 = Set2 = a_set()
1187
1188              Returns the Cartesian product of Set1 and Set2.
1189
1190              1> S1 = sofs:set([1,2]),
1191              S2 = sofs:set([a,b]),
1192              R = sofs:product(S1, S2),
1193              sofs:to_external(R).
1194              [{1,a},{1,b},{2,a},{2,b}]
1195
1196              product(S1, S2) is equivalent to product({S1, S2}).
1197
1198       projection(SetFun, Set1) -> Set2
1199
1200              Types:
1201
1202                 SetFun = set_fun()
1203                 Set1 = Set2 = a_set()
1204
1205              Returns the set created by substituting each element of Set1  by
1206              the result of applying SetFun to the element.
1207
1208              If  SetFun  is  a number i >= 1 and Set1 is a relation, then the
1209              returned set is the projection of Set1 onto coordinate i.
1210
1211              1> S1 = sofs:from_term([{1,a},{2,b},{3,a}]),
1212              S2 = sofs:projection(2, S1),
1213              sofs:to_external(S2).
1214              [a,b]
1215
1216       range(BinRel) -> Set
1217
1218              Types:
1219
1220                 BinRel = binary_relation()
1221                 Set = a_set()
1222
1223              Returns the range of the binary relation BinRel.
1224
1225              1> R = sofs:relation([{1,a},{1,b},{2,b},{2,c}]),
1226              S = sofs:range(R),
1227              sofs:to_external(S).
1228              [a,b,c]
1229
1230       relation(Tuples) -> Relation
1231
1232       relation(Tuples, Type) -> Relation
1233
1234              Types:
1235
1236                 N = integer()
1237                 Type = N | type()
1238                 Relation = relation()
1239                 Tuples = [tuple()]
1240
1241              Creates a relation. relation(R, T) is equivalent to from_term(R,
1242              T),  if  T is a type and the result is a relation. If Type is an
1243              integer N, then [{atom, ..., atom}]), where the tuple size is N,
1244              is used as type of the relation. If no type is explicitly speci‐
1245              fied, the size of the first tuple of Tuples is used if there  is
1246              such a tuple. relation([]) is equivalent to relation([], 2).
1247
1248       relation_to_family(BinRel) -> Family
1249
1250              Types:
1251
1252                 Family = family()
1253                 BinRel = binary_relation()
1254
1255              Returns  family  Family  such that the index set is equal to the
1256              domain of the binary relation BinRel, and Family[i] is the image
1257              of the set of i under BinRel.
1258
1259              1> R = sofs:relation([{b,1},{c,2},{c,3}]),
1260              F = sofs:relation_to_family(R),
1261              sofs:to_external(F).
1262              [{b,[1]},{c,[2,3]}]
1263
1264       relative_product(ListOfBinRels) -> BinRel2
1265
1266       relative_product(ListOfBinRels, BinRel1) -> BinRel2
1267
1268              Types:
1269
1270                 ListOfBinRels = [BinRel, ...]
1271                 BinRel = BinRel1 = BinRel2 = binary_relation()
1272
1273              If ListOfBinRels is a non-empty list [R[1], ..., R[n]] of binary
1274              relations and BinRel1 is a binary relation, then BinRel2 is  the
1275              relative  product  of the ordered set (R[i], ..., R[n]) and Bin‐
1276              Rel1.
1277
1278              If BinRel1 is omitted, the relation of equality between the ele‐
1279              ments of the Cartesian product of the ranges of R[i], range R[1]
1280              x ... x range R[n], is used  instead  (intuitively,  nothing  is
1281              "lost").
1282
1283              1> TR = sofs:relation([{1,a},{1,aa},{2,b}]),
1284              R1 = sofs:relation([{1,u},{2,v},{3,c}]),
1285              R2 = sofs:relative_product([TR, R1]),
1286              sofs:to_external(R2).
1287              [{1,{a,u}},{1,{aa,u}},{2,{b,v}}]
1288
1289              Notice  that  relative_product([R1], R2) is different from rela‐
1290              tive_product(R1, R2); the list of one element is not  identified
1291              with the element itself.
1292
1293       relative_product(BinRel1, BinRel2) -> BinRel3
1294
1295              Types:
1296
1297                 BinRel1 = BinRel2 = BinRel3 = binary_relation()
1298
1299              Returns the relative product of the binary relations BinRel1 and
1300              BinRel2.
1301
1302       relative_product1(BinRel1, BinRel2) -> BinRel3
1303
1304              Types:
1305
1306                 BinRel1 = BinRel2 = BinRel3 = binary_relation()
1307
1308              Returns the relative product of the converse of the binary rela‐
1309              tion BinRel1 and the binary relation BinRel2.
1310
1311              1> R1 = sofs:relation([{1,a},{1,aa},{2,b}]),
1312              R2 = sofs:relation([{1,u},{2,v},{3,c}]),
1313              R3 = sofs:relative_product1(R1, R2),
1314              sofs:to_external(R3).
1315              [{a,u},{aa,u},{b,v}]
1316
1317              relative_product1(R1, R2) is equivalent to relative_product(con‐
1318              verse(R1), R2).
1319
1320       restriction(BinRel1, Set) -> BinRel2
1321
1322              Types:
1323
1324                 BinRel1 = BinRel2 = binary_relation()
1325                 Set = a_set()
1326
1327              Returns the restriction of the binary relation BinRel1 to Set.
1328
1329              1> R1 = sofs:relation([{1,a},{2,b},{3,c}]),
1330              S = sofs:set([1,2,4]),
1331              R2 = sofs:restriction(R1, S),
1332              sofs:to_external(R2).
1333              [{1,a},{2,b}]
1334
1335       restriction(SetFun, Set1, Set2) -> Set3
1336
1337              Types:
1338
1339                 SetFun = set_fun()
1340                 Set1 = Set2 = Set3 = a_set()
1341
1342              Returns a subset of Set1 containing those elements that gives an
1343              element in Set2 as the result of applying SetFun.
1344
1345              1> S1 = sofs:relation([{1,a},{2,b},{3,c}]),
1346              S2 = sofs:set([b,c,d]),
1347              S3 = sofs:restriction(2, S1, S2),
1348              sofs:to_external(S3).
1349              [{2,b},{3,c}]
1350
1351       set(Terms) -> Set
1352
1353       set(Terms, Type) -> Set
1354
1355              Types:
1356
1357                 Set = a_set()
1358                 Terms = [term()]
1359                 Type = type()
1360
1361              Creates   an   unordered   set.   set(L,  T)  is  equivalent  to
1362              from_term(L, T), if the result is an unordered set. If  no  type
1363              is explicitly specified, [atom] is used as the set type.
1364
1365       specification(Fun, Set1) -> Set2
1366
1367              Types:
1368
1369                 Fun = spec_fun()
1370                 Set1 = Set2 = a_set()
1371
1372              Returns  the  set containing every element of Set1 for which Fun
1373              returns true. If Fun  is  a  tuple  {external,  Fun2},  Fun2  is
1374              applied  to  the  external set of each element, otherwise Fun is
1375              applied to each element.
1376
1377              1> R1 = sofs:relation([{a,1},{b,2}]),
1378              R2 = sofs:relation([{x,1},{x,2},{y,3}]),
1379              S1 = sofs:from_sets([R1,R2]),
1380              S2 = sofs:specification(fun sofs:is_a_function/1, S1),
1381              sofs:to_external(S2).
1382              [[{a,1},{b,2}]]
1383
1384       strict_relation(BinRel1) -> BinRel2
1385
1386              Types:
1387
1388                 BinRel1 = BinRel2 = binary_relation()
1389
1390              Returns the strict relation corresponding to the binary relation
1391              BinRel1.
1392
1393              1> R1 = sofs:relation([{1,1},{1,2},{2,1},{2,2}]),
1394              R2 = sofs:strict_relation(R1),
1395              sofs:to_external(R2).
1396              [{1,2},{2,1}]
1397
1398       substitution(SetFun, Set1) -> Set2
1399
1400              Types:
1401
1402                 SetFun = set_fun()
1403                 Set1 = Set2 = a_set()
1404
1405              Returns a function, the domain of which is Set1. The value of an
1406              element of the domain is the result of applying  SetFun  to  the
1407              element.
1408
1409              1> L = [{a,1},{b,2}].
1410              [{a,1},{b,2}]
1411              2> sofs:to_external(sofs:projection(1,sofs:relation(L))).
1412              [a,b]
1413              3> sofs:to_external(sofs:substitution(1,sofs:relation(L))).
1414              [{{a,1},a},{{b,2},b}]
1415              4> SetFun = {external, fun({A,_}=E) -> {E,A} end},
1416              sofs:to_external(sofs:projection(SetFun,sofs:relation(L))).
1417              [{{a,1},a},{{b,2},b}]
1418
1419              The relation of equality between the elements of {a,b,c}:
1420
1421              1> I = sofs:substitution(fun(A) -> A end, sofs:set([a,b,c])),
1422              sofs:to_external(I).
1423              [{a,a},{b,b},{c,c}]
1424
1425              Let SetOfSets be a set of sets and BinRel a binary relation. The
1426              function that maps each element Set of SetOfSets onto the  image
1427              of Set under BinRel is returned by the following function:
1428
1429              images(SetOfSets, BinRel) ->
1430                 Fun = fun(Set) -> sofs:image(BinRel, Set) end,
1431                 sofs:substitution(Fun, SetOfSets).
1432
1433              External  unordered  sets  are  represented as sorted lists. So,
1434              creating the image of a set under a relation R can traverse  all
1435              elements of R (to that comes the sorting of results, the image).
1436              In image/2, BinRel is traversed once for each element of  SetOf‐
1437              Sets,  which can take too long. The following efficient function
1438              can be used instead under the assumption that the image of  each
1439              element of SetOfSets under BinRel is non-empty:
1440
1441              images2(SetOfSets, BinRel) ->
1442                 CR = sofs:canonical_relation(SetOfSets),
1443                 R = sofs:relative_product1(CR, BinRel),
1444                 sofs:relation_to_family(R).
1445
1446       symdiff(Set1, Set2) -> Set3
1447
1448              Types:
1449
1450                 Set1 = Set2 = Set3 = a_set()
1451
1452              Returns  the  symmetric  difference (or the Boolean sum) of Set1
1453              and Set2.
1454
1455              1> S1 = sofs:set([1,2,3]),
1456              S2 = sofs:set([2,3,4]),
1457              P = sofs:symdiff(S1, S2),
1458              sofs:to_external(P).
1459              [1,4]
1460
1461       symmetric_partition(Set1, Set2) -> {Set3, Set4, Set5}
1462
1463              Types:
1464
1465                 Set1 = Set2 = Set3 = Set4 = Set5 = a_set()
1466
1467              Returns a triple of sets:
1468
1469                * Set3 contains the elements of Set1 that  do  not  belong  to
1470                  Set2.
1471
1472                * Set4 contains the elements of Set1 that belong to Set2.
1473
1474                * Set5  contains  the  elements  of Set2 that do not belong to
1475                  Set1.
1476
1477       to_external(AnySet) -> ExternalSet
1478
1479              Types:
1480
1481                 ExternalSet = external_set()
1482                 AnySet = anyset()
1483
1484              Returns the external set of an  atomic,  ordered,  or  unordered
1485              set.
1486
1487       to_sets(ASet) -> Sets
1488
1489              Types:
1490
1491                 ASet = a_set() | ordset()
1492                 Sets = tuple_of(AnySet) | [AnySet]
1493                 AnySet = anyset()
1494
1495              Returns the elements of the ordered set ASet as a tuple of sets,
1496              and the elements of the unordered set ASet as a sorted  list  of
1497              sets without duplicates.
1498
1499       type(AnySet) -> Type
1500
1501              Types:
1502
1503                 AnySet = anyset()
1504                 Type = type()
1505
1506              Returns the type of an atomic, ordered, or unordered set.
1507
1508       union(SetOfSets) -> Set
1509
1510              Types:
1511
1512                 Set = a_set()
1513                 SetOfSets = set_of_sets()
1514
1515              Returns the union of the set of sets SetOfSets.
1516
1517       union(Set1, Set2) -> Set3
1518
1519              Types:
1520
1521                 Set1 = Set2 = Set3 = a_set()
1522
1523              Returns the union of Set1 and Set2.
1524
1525       union_of_family(Family) -> Set
1526
1527              Types:
1528
1529                 Family = family()
1530                 Set = a_set()
1531
1532              Returns the union of family Family.
1533
1534              1> F = sofs:family([{a,[0,2,4]},{b,[0,1,2]},{c,[2,3]}]),
1535              S = sofs:union_of_family(F),
1536              sofs:to_external(S).
1537              [0,1,2,3,4]
1538
1539       weak_relation(BinRel1) -> BinRel2
1540
1541              Types:
1542
1543                 BinRel1 = BinRel2 = binary_relation()
1544
1545              Returns  a  subset S of the weak relation W corresponding to the
1546              binary relation BinRel1. Let F be the field of BinRel1. The sub‐
1547              set  S is defined so that x S y if x W y for some x in F and for
1548              some y in F.
1549
1550              1> R1 = sofs:relation([{1,1},{1,2},{3,1}]),
1551              R2 = sofs:weak_relation(R1),
1552              sofs:to_external(R2).
1553              [{1,1},{1,2},{2,2},{3,1},{3,3}]
1554

SEE ALSO

1556       dict(3), digraph(3), orddict(3), ordsets(3), sets(3)
1557
1558
1559
1560Ericsson AB                       stdlib 3.10                          sofs(3)
Impressum