data Timed e = Value e | Wait Time data Strom e = Strom [ Timed e ]Damit wir später gut damit rechnen können, machen wir das zu einer Functor-Instanz:
instance Functor Timed where
fmap f (Value a) = Value (f a)
fmap f (Wait t) = Wait t
Die Funktion mappen wir nur auf die Ereignisse,
die Wartezeiten bleiben bestehen.
Durch Hintereinanderschalten mit dem List-Funktor
ist dann auch Strom ein Funktor.
Wenn wir einmal dabei sind, wie sieht es mit einer Monade aus? (Warum sollten wir das überhaupt wollen? Weil wir dann die do-Notation benutzen können.) Offensichtlich ist sicher das:
return :: e -> Strom e return x = [ Value x ]aber was ist das passende bind? Wir erinnern uns daran, daß wir für Listen
xs >>= f = concat (fmap f xs)hatten. Sowas geht immer, d. h. für eine Monaden-Instanz genügt es auch, wenn wir statt (>>=) das passende
concat :: m (m a) -> m aangeben. Dazu müssen wir also aus einer Zeitliste von Zeitlisten auf sinnvolle Weise eine einzige Zeitliste herstellen. Die Frage ist, was wir mit den Wartezeiten anfangen, die die einzelnen Zeitlisten voneinander trennen. Na gut, die lassen wir eben dort stehen.
Hausaufgabe: ist das wirklich eine Monade, d. h. schreiben die entsprechenden Definitionen genau auf und prüfe die Axiome.
Nun ist das zwar ein vernünftiger Ansatz, der aber noch nicht weit genug greift. Unser auszuführendes Musikprogramm ergibt nämlich nicht einen Wert :: Strom Midi_Event, denn die auszugebenden Noten sollen ja von den User-Eingaben abhängen, die wir aber zu Programmanfang noch gar nicht kennen. Würden wir als Typ aber so eine Zeitliste festlegen, folgt schon daraus, daß wir diese Werte durch keinerlei Eingaben beeinflussen können. Das sieht wie eine unbotmäßige Beschränkung durch das Haskell-Typsystem aus, aber im Gegenteil, wir sollten uns darüber freuen: das Typsystem garantiert uns hier, daß ein Wert eben ein Wert ist, und zwar immer derselbe, und von keiner Nutzeraktion abhängt. Wenn wir das wollen, müssen wir es explizit hinschreiben.
Ein Ansatz ist IO [ Timed e ], also eine Aktion, deren Wert die Liste ist. Aber das ist immer noch zu kurz gedacht. Wie wollen wir denn solch einen Wert herstellen? So:
fun = do x <- irgendeine aktion
xs <- noch ein paar aktionen
return (x : xs)
da werden aber erst alle Aktionen ausgeführt,
bevor wir auch nur das erste x sehen.
Das nützt aber nichts, ich will das x sofort ausgeben,
und danach noch weitere Eingaben behandeln.
Eine Lösung ist das:
data IOStream a = Nil | Cons (Timed a) (IO (IOStream a))Wir bauen uns hier einen Listentyp von Hand, richtig mit Cons und Nil wie in den siebziger Jahren, und die Besonderheit ist, daß der Tail (der Cdr, hieß das früher) nicht direkt dasteht, sondern dort eine IO-Aktion steht, die dann, wenn wir sie ausführen, den Schwanz der Liste ergibt. Von diesen können wir dann wieder den Car anschauen, und den Cdr durch eine Aktion ausrechnen, und so weiter.
Man muß nun für diese Art von "verzögerten" Listen die oben schon hergeleiteten Functor- und Monad-Instanzen nocheinmal aufschreiben, und dann geht es weiter wie bisher (weil wir dann die do-Notation benutzen können, und gar nicht mehr merken, in welcher Monade wir eigentlich sind).
Für die Monade brauchen wir das erwähnte concat, das bauen wir natürlich aus mehrfachem append zusammen. Die andere Grundoperation ist merge (parallel ausführen). Beider Code ergibt sich ganz von selbst. (TODO: link)
Das Wort "natürlich" eben war eventuell übertrieben, wir könnten uns, wenn wir viel Muße haben, einmal überlegen, ob sich die Zeitlisten cleverer repräsentieren lassen. Eigentlich macht man sowas nämlich mit Prioritätswarteschlangen, tatsächlich sind es Wartebäume, die eine hochgradige Parallelschaltung besser beherrschen: alle zu mergenden IOStreams stehen eben nicht in einer Liste nebeneinander, sonden in einem sinnreich balancierten Baum. Die Entfernung zur Wurzel bemißt sich nach der jeweils noch verbleibenden Wartezeit (Zeit, bis aus dem Strom ein tatsächliches Ereignis auftaucht). In der Wurzel steht also immer das direkt folgende Ereignis. Wenn wir das behandeln wollen, entfernen wir es aus der Wurzel (d. h. müssen die Kinderbäume zu einem neuen Wartebaum zusammenfassen). Nach der Behandlung müssen wir den Schwanz seiner Zeitliste (mit dem richtigen Zeitabstand) wieder in den Wartebaum einfügen. Genau dafür gibt es hoch optimierte Verfahren (z. B. Binomial-Queues). Man wird sehen, ob man das hier wirklich benötigt. Falls ja, tauschen wir eben einfach den IOStream-Datentyp aus; weiter hinten im Programm sollte sich nichts ändern, wenn wir alles schön abstrakt programmiert haben.