Mengenbeschreibungen

Eine Menge ist eine Ansammlung von Elementen, typischerweise einer bestimmten Art, die in irgendeinem Behälter (engl. Container oder Collection) untergebracht sind. Das unterscheidet sich insofern von einer mathematischen Menge, weil zunächst Elemente auch mehrfach vorkommen können. In der Regel erlaubt der Kontext eine Unterscheidung zwischen den beiden, so dass es eigentlich nicht zu Verwechslungen kommen kann.

Der konkrete Typ des Behälters entscheidet darüber, welche Eigenschaften die Elemente haben, ob beispielsweise sie paarweise verschieden, geordnet oder sortiert sind. Die Elemente können entweder explizit aufgelistet werden oder auch algorithmisch erzeugt werden. Dabei stehen zumindest theoretisch auch unbegrenzte Mengen zur Verfügung, aus denen eine begrenzte Anzahl von Elementen ausgefiltert wird.

Literale

Ungeachtet dessen können die wichtigsten dieser Behälter über Literale dargestellt werden. Dabei entscheidet die Klammerung eindeutig über die Eigenschaft des Behälters.

Literal	Beschreibung	geordnet	eindeutig	homogen	Typ
(1, 2, 2, 3)	Tupel	ja	nein	nein	Tuple
{1, 2, 3}	Menge	nein	ja	ja	Set
{1 ↦ ‘a’, 2 ↦ ‘b’}	Abbildung	nein	ja	ja	Map
⦃1, 2, 2, 3⦄	Beutel	nein	nein	ja	Bag
⟨1, 2, 2, 3⟩	Liste	ja	nein	ja	List
[1, 2, 2, 3]	Reihung	ja	nein	ja	Array
[1 2 3]	Vektor	ja	nein	ja	Vector
[1 2; 4 5]	Matrix	ja	nein	ja	Matrix

Einzig die Menge (Set) und die Abbildung (Map) enthalten Elemente, die paarweise verschieden sind. Darüber hinaus sind beide ungeordnet und bieten damit beeindruckende Möglichkeiten zur Lösung von Problemen.

Aufzählungen

Die einfachste Art, einen Behälter zu beschreiben, ist die Aufzählung. Dabei werden alle Elemente in den für den gewünschten Typ passenden Klammern angegeben. Dabei unterliegen die Elemente den für den Typ spezifischen Einschränkungen. Beispielsweise darf eine Menge keine (offensichtlich) gleichen Elemente enthalten.

… ⟨1, 2, 3, 3⟩ …	Eine Liste kann natürlich gleiche Elemente enthalten.
… {1, 2, 3, 3} …	↯ Eine Menge kann keine offensichtlich doppelten Elemente enthalten.
a :← 2
b :← 2
… {a, b}…	Dies ist auch bei Konstanten möglich.

Kurzschreibweise für Aufzählungen

Regelmäßige Aufzählungen der Form (a, a + Δ, a + 2‌Δ, … , b − Δ, b) können abgekürzt werden. Mit a ≤ b und Δ ≥ 0 lässt sich eine Aufzählung wie folgt beschreiben:

… {a, a + Δ, … , b} …
… {a, d, … , b} …	Δ = d − a

Fehlt die zweite Komponente, so wird Δ = 1 angenommen. Damit beschreibt diese verkürzte Schreibweise diejenigen Elementen für k ∈ ℕ für die a ≤ a + k ⋅ Δ ≤ b ist.

Grundssätzlich müssen verkürzte Aufzählungen, wenn sie nur aus Literalen bestehen, immer korrekt angegeben sein. Schon bei Angabe einer Variablen oder Konstanten entfällt diese Einschränkung.

assert {1, … , 10}	= {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
assert {1, 2, … , 10}	= {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}

assert {1, 3, … , 10}	= {1, 3, 5, 7, 9}	↯ Ende muss passend sein.
N := 10
assert {1, 3, … , N}	= {1, 3, 5, 7, 9}	Ende muss nicht (mehr) passend sein.
assert {1, 3, … , 9}	= {1, 3, 5, 7, 9}	Ende ist passend.
N′ := 1
assert {1, … , N′}	= {1}
assert {1, 3, … , N′}	= {1}
N″ := 0
assert {1, … , N″}	= {}
assert {1, 3, … , N″}	= {}
assert {N″, N″ + 2, 9}	= {0, 2, 4, 6, 8}

Kurzschreibweise mit absteigender Reihenfolge

Die Kurzschreibweise gilt auch für absteigende Folgen, wenn der zweite Teil explizit angegeben und das daraus resultierende Δ < 0 ist.

assert {10, 9, … , 1} = {1, … , 10}

assert ⟨10, 9, … , 1⟩ = ⟨10, 9, 8, 7, 6, 5, 4, 3, 2, 1⟩

N := 10

assert {10, 9, … , N} = {10}

Kombinierte Aufzählungen

Alle obigen Methoden können kombiniert werden, wenn sie durch ein Semikolon getrennt aneinandergereiht werden. In dem Fall sind auch bei der Angabe von Literalen Doubletten möglich, wenn sich diese nicht auf andere Weise „trivial“ darstellen lassen.

assert (

{1, …, 5; 7, 9, … , 13; 14, 17; 18, … , 21}

{1, 2, 3, 4, 5, 9, 11, 13, 14, 17, 18, 19, 20, 21}

}

assert (

{2, 4, … , 20; 3, 6, … 18}	Alle Vielfachen von 2 und 3 kleiner oder gleich 20.
=
{2, 3, 4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20}

)

Kurzschreibweise bei Aufzählungstypen

Sind Aufzählungstypen geordnet, so kann auch bei diesen die abkürzende Schreibweise genutzt werden.

Weekdays ≡ ⟦ordered⟧ {Monday, Tuesday, Wednesday, Thursday, Friday, Saturday, Sunday}

workdays :← {Monday, … , Friday}

assert workdays = {Monday, Tuesday, Wednesday, Thursday, Friday}

Unbegrenzte Aufzählungen

Wird keine Grenze angegeben, so sind die erzeugten Behälter beliebig groß. Das bedeutet, dass diese ohne eine nachträgliche Begrenzung entweder zu einem Überlauf führen oder irgendwann der Speicher nicht mehr ausreicht. Bei deren Verwendung muss man also entsprechend Vorsicht walten lassen.

assert {1, …} = {1, 2, …}

assert {1, 3, …} = {1; 3, 6, …}

assert {10, 9, …} = {10, 9, …, 0; −1, −2, …}

Besondere Beachtung verdienen unbegrenzte Aufzählungen, die in beide Richtungen unbegrenzt sind. Das ist allerdings nur für mengenartige Behälter, die keine wohldefinierte Ordnung haben, sinnvoll. Damit kann der Wunsch zum Ausdruck gebracht werden, dass die Elemente eher alternierend durchlaufen werden sollen.

{…, −1, 0, 1, …}	Etwa 0, −1, 1, −2, 2, −3, 3, …
{…, k − 2, k, k + 2, …}	Etwa k, k − 2, k + 2, k − 4, k + 4, …
{…, k − Δ, k, k + Δ, …}	Etwa k, k − Δ, k + Δ, k − 2 ⋅ Δ, k + 2 ⋅ Δ, …

Die Formulierung ist hier besonders schwammig, weil bei den mengenartigen Behältern auf keinen Fall von einer definierten Ordnung ausgegangen werden darf. Es können nämlich weder Annahmen darüber gemacht werden, wie sich eine Menge bei mehrmaligem Durchlaufen verhält, noch darüber, wie sie sich nach dem nächsten Programmstart verhalten wird.

Generatoren

Die Behälter lassen sich nach Belieben durch geeignete Abbildungsvorschriften auffüllen, wobei die von, … , bis-Notation die einfachste ist. Die Elemente können durch zwei Teile beschrieben werden: Das auf den Laufvariaben basierende Ergebnis und eine Liste von Laufvariablen mit optionalen Bedingungen.

{ℰ(x₁, x₂, … , x􊈮) ∣ x₁ ∈ C₁, 𝓅(x₁); x₂ ∈ C₂, 𝓅(x₁, x₂); … ; x􊈮 ∈ C􊈮, 𝓅(x₁, x₂, … , x􊈮)}

Dabei können nicht nur die Bedingungen von voranstehenden Laufvariablen abhängig sein, sondern auch die Behälter von ebendiesen.

{ℰ(x₁, x₂, … , x􊈮) ∣

x₁ ∈ C₁, 𝓅(x₁);

x₂ ∈ C₂(x₁), 𝓅(x₁, x₂);

… ,

x􊈮 ∈ C􊈮(x₁, x₂, … , x􊈮₋₁), 𝓅(x₁, x₂, … , x􊈮)

}

Die Semikolons können genutzt werden, um die Gruppen deutlicher voneinander zu trennen.

M := {1, … , 10}

assert ∣{(x, y, z) ∣ x ∈ M, y ∈ M, z ∈ M, x² + y² = z²}∣ = 2

assert ∣⟨(x, y, z) ∣ x ∈ M, y ∈ M, z ∈ M, x² + y² = z²⟩∣ = 4

assert {x² ∣ x ∈ {1, 2, 5, 10}} = {1, 4, 25, 100}	Set
assert {x ↦ x² ∣ x ∈ {1, … , 4}} = {1 ↦ 1, 2 ↦ 4, 3 ↦ 9, 4 ↦ 16}	Map
assert ⟨2‌n + 1 ∣ x ∈ ⟨1, … , 5⟩⟩ = ⟨3, 5, 7, 9, 11⟩	List
assert {2‌n + 1 ∣ x ∈ {1, … , 5}} = {3, 5, 7, 9, 11}	List

Liste der Kundennummern derjenigen Kunden, deren Standort im 9er Postleitzahlenbereich

liegen, die Lieferadresse ihrer Bestellungen aber außerhalb dieses Bereichs liegen.

⟨c.id ∣

c ∈ customers, c.address.plz ∈ {90000, … , 99999};

o ∈ orders, o.customer_id = c.id; o.address.plz ∉ {90000, … , 99999}

⟩

Wie oben, nur dass hier die Bestellnummern statt der Kundennummern geliefert werden.

⟨o.id ∣

c ∈ customers, c.address.plz ∈ {90000, … , 99999};

o ∈ orders, o.customer_id = c.id; o.address.plz ∉ {90000, … , 99999}

⟩

Alle Bestellungen der gegebenen Kunden, deren Bestellwert über 1000 € liegt.

⟨o ∣

c ∈ customers

o ∈ orders, o.customer_id = c.id;

o.amount > 1000.00

⟩

Vereinfachungen und Transformationen

Gelegentlich liegt das Ergebnis nicht in dem gewünschten Behälter vor, etwa die Liste nicht als Menge, die keine paarweisen, gleichen Elemente mehr enthalten würde. Natürlich kann mit den gegebenen Mitteln eine solche Umformung stattfinden.

list :← ⟨1, 2, 2, 3, 3, 3, 4, 4, 4, 4⟩

set :← {x ∣ x ∈ list}

assert set = {1, 2, 3, 4}

list ← ⟨x ∣ x ∈ set⟩

assert list.sort() = ⟨1, 2, 3, 4⟩

In diesem speziellen Fall geht es aber auch einfacher, indem die Abbildungsvorschrift für die Elemente weggelassen wird.

list :← ⟨1, 2, 2, 3, 3, 3, 4, 4, 4, 4⟩

set :← {x ∈ list}

assert set = {1, 2, 3, 4}

list ← ⟨x ∈ set⟩

assert list.sort() = ⟨1, 2, 3, 4⟩

Diese abkürzende Schreibweise ist auch deswegen von Vorteil, weil auf diese Weise im Idealfall die eine Darreichungsform in eine andere umgewandelt werden kann, ohne dass ein Kopieren der Elemente erforderlich ist. Beispielsweise kann jeder Beutel (Bag) ohne großen Aufwand in eine Menge umgewandelt werden (Set), indem die Häufigkeiten der einzelnen Elemente ignoriert werden.

Umgekehrt kann diese Notation einfach erweitert werden, um zu verdeutlichen, was genau von Interesse ist und welche Elemente gefiltert werden sollen. Das ist oftmals einfacher, wenn nach Elementen gesucht wird, die nicht einer bestimmten Eigenschaften genügen.

S := {1, … , 1000}

Alle Zahlen d, deren Quadrat sich nicht als Summe dreier Quadratzahlen darstellen lässt.

result_set :← {d ∈ S ∣ a ∈ S, b ∈ S, c ∈ S, a² + b² + c² ≠ d²}

assert result_set = {1, 2, 4, 5, 8, 10, 16, 20, 32, 40, 64, 80, 128, 160, 256, 320, 512, 640}

Erweiterung des Skopus

Mit Hilfe der where-Klausel kann der Skopus einzelner Teilausdrücke erweitert werden. Die where-Anweisung wird dabei naturgemäß nur ein einziges Mal zu beginn der zugeordneten Iteration durchlaufen.

N := 1000

S := {1, … , N}

Alle Zahlen d, deren Quadrat sich nicht als Summe dreier Quadratzahlen darstellen lässt.

result_set :← {d ∈ S ∣ a ∈ S, b ∈ S, c ∈ S, a² + b² + c² ≠ d²}

Leichte Verbesserung durch Reduktion der Indexbereiche (was sehr hilfreich ist)

mit Speicherung von Zwischenergebnissen (was in der Regel nicht nötig ist, hier aber

zu Demonstrationszwecken gemacht wird).

result_set :← {d ∈ {1, … , N} ∣

a ∈ {1, … , N} where s_d := d²,

b ∈ {a, … , N} where s_a := a²,

c ∈ {b, … , N} where s_ab := s_a + b²,

s_ab + c² ≠ s_d

}

assert result_set = {1, 2, 4, 5, 8, 10, 16, 20, 32, 40, 64, 80, 128, 160, 256, 320, 512, 640}

Die where-Klausel wird also einmalig vor Ausführung der Iteration über die Menge ausgewertet und steht so jedem der Elemente unverändert zur Verfügung.

Beliebiges Element

Eine besondere Rolle spielt die arb-Funktion, die ja wahllos (engl. arbitrary) ein Element liefert. Wird diese im Zusammenhang mit Generatoren angegeben, so lässt sich die Suche nach den Elementen verkürzen. Dabei ist insofern Vorsicht geboten, weil eine leere Menge unweigerlich zu einer Ausnahme führt.

solutions := {{3, 4, 5}, {6, 8, 10}}

S :← {1, … , 10}

assert arb({{a, b, c} ∣ x ∈ S, y ∈ S, z ∈ S, x² + y² = z²}) ∈ solutions

S :← {1, … , 4}

assert arb({{a, b, c} ∣ x ∈ S, y ∈ S, z ∈ S, x² + y² = z²}) throws NoSuchElement

Typisierung

Bei allen bisherigen Beispielen hat der Übersetzer den tatsächlichen Typ aus den gegebenen Informationen abgeleitet. Das gilt nicht nur für die einzelnen Laufvariablen oder die resultierenden Elemente, sondern auch für den Behälter selbst. Gelegentlich ist es aber wünschenswert den Typ explizit anzugeben. Dies kann dann durch Angabe des Typs geschehen.

M := {1, 2, 3}
M′ := {x : ℕ₃₂ ∣ x ∈ M}	Set⟦ℕ₃₂⟧

Im Falle einer Transformation der resultierenden Elemente kann wenn nötig der Typ als Präfix angegeben werden.

M := {1, 2, 3}
M′ := {2‌x − 1 : ℕ₃₂ ∣ x ∈ M}	Set⟦ℕ₃₂⟧

Bei einer Abbildung gibt es zwei Möglichkeiten.

{(x : ℕ₃₂) ↦ x²	∣ x ∈ {1, … , 4}}	Map⟦ℕ₃₂, ℕ₃₂⟧
{(x : ℕ₃₂) ↦ isEven(x)	∣ x ∈ {1, … , 4}}	Map⟦ℕ₃₂, 𝔹⟧
{x ↦ x² : (ℕ₃₂, ℕ₆₄)	∣ x ∈ {1, … , 4}}	Map⟦ℕ₃₂, ℕ₆₄⟧

Den Typ des Behälters zu ändern ist nicht ganz so einfach, weil es in den meisten Fällen nicht nötig. Nichtsdestoweniger können aus den Literalen schon zur Übersetzungszeit Behälter passenden Typs erzeugt werden, wenn diese statische Konstruktoren für die entsprechenden Typen anbieten. Zu diesen Typen gehören beispielsweise StaticRangeSet, StaticOrderedSet, StaticBitSet und StaticSet, die über geeignete Schnittstellen verfügen, so dass sie leicht in den gewünschten Typ konvertiert werden können.