frosch03.de/posts/2013-02-11-NatTuple

In dem folgenden Zeilen, zeige ich eine neue/andere Variante von Tupeln auf. Die Tupel die in Haskell vom Hause aus mitgeliefert werden, passen nicht perfekt auf meine Bedürfnisse.

Ein Tupel ist ein Begriff der aus der Mathematik kommt und dort ein mathematisches Objekt beschreibt, dass einige Eigenschaften besitzt. Ein Tupel ist dort ein geordnetes Paar das aus zwei anderen Komponenten besteht.

Eigentlich ist der Begriff Tupel nicht ganz korrekt. Im Englischen wird von "single", "double", "triple", "quadruple", "quintuple" oder "sextuple" gesprochen. Dabei ist das Tupel das Suffix ab einem fünfer Konglomerat. In Informatikerkreisen wird dieses Suffix aber völlig anders verstanden; hier bezeichnet ein Tupel ein zweier Konglomerat. Um den Zusammenschluss von 3, 4 oder n Komponenten zu bezeichnen wird sich der n-Tupel Schreibweise bedient.

Von den Eigenschaften her haben Tupel einige Gemeinsamkeiten mit Listen, unterscheiden sich jedoch auch von diesen. Eine Liste stellt eine potentiell unendliche Datenstruktur dar, ein Tupel hat (quasi schon durch seinen Namen gegeben) eine feste Anzahl von Bestandteilen. Listen können in sich nur Elemente eines Typs aufnehmen, wohingegen Tupel völlig unterschiedliche Komponenten halten können. Und auch was den Zugriff auf einzelne Elemente angeht unterscheiden sich beide Datenstrukturen. Wo bei einer Liste mindestens eine lineare Zugriffszeit für ein beliebiges Element angegeben werden muss, ist der Zugriff innerhalb eines Tupels immer konstant.

Zusammengefasst heißt dies: Listen: * unendlich * heterogen * lineare Zugriffszeit

Tupel: * endlich * homogen * konstante Zugriffszeit

In meinem Einsatzbereich habe ich es nun häufig mit mehrstelligen 8-Tupeln oder 16-Tupeln zu tun. Diese Tupel beinhalten jetzt schon nur einen Datentyp und dies lässt sich voraussichtlich auch in Zukunft so weiterführen.

Eine häufige Aufgabe ist, dass innerhalb der Tupel zwei Daten miteinander getauscht werden müssen. Beispielsweise muss der erste Wert mit dem 7ten vertauscht werden:

{% highlight haskell %} (1, 2, 3, 4, 5, 6, 7, 8)

(7, 2, 3, 4, 5, 6, 1, 8)

{% endhighlight %}

Diese Form des "umtupelns" wird häufig benötigt. Dabei sollten nach Möglichkeit nur wenige generische Funktionen beteiligt sein. Mit dem Tupel-Typ von Haskell ist dies allerdings nicht möglich. Genauer wird sogar für jeden Zugriff auf ein Element mit einer anderen Position eine neue Funktion benötigt.

Für das 7te und das erste Element sehen die Zugriffsfunktionen so aus:

{% highlight haskell %} (/, /, /, /, /, /, x7, \_) -> x7)

\(x1, _, _, _, _, _, _,  _) -> x1)

{% endhighlight %}

Da nicht abzusehen ist wie groß die Tupel werden und auch nicht, wie diese verarbeitet werden, ist der Tupel-Typ Haskells nur wenig Zielführend.

In der Vergangenheit wurden viele Tupel einer gewissen Form verwendet. Dabei handelt es sich um Tupel, bei denen der eigentlich verwendete Wert mit einem weiteren Tupel verbunden wurde. Diese Tupel sehen beispielsweise so aus:

{% highlight haskell %} (True, (False, (True, False))) {% endhighlight %}

Hier ist es möglich, mit fst und snd sich "durch" das Tupel "hindurch" zu bewegen. Dieser Datentyp gibt schon einen Hinweis darauf, wie die Lösung aussehen könnte.

Im Prinzip ist es notwendig, dass es eine Möglichkeit gibt, an eine bestimmte Stelle in einem Tupel zu navigieren. Außerdem ist es notwendig, dass ein 3-Tupel und ein 8-Tupel beide den selben Datentyp besitzen.

Um dies zu ermöglichen wird ein Tupel