In meinem vorherigen Artikel habe ich die Berechnung zum Entsparen von investiertem Vermögen hergeleitet und einen kleinen Rechner demonstriert. Dabei ist mir aufgefallen, dass sich bei hohen Jahreszahlen eine kleine Verzögerung bemerkbar gemacht hat. Die Ursache der Verzögerung liegt in meiner Umsetzung der Formel $$\sum_{k=1}^{m-1}\frac{1}{\prod_{t=1}^{k}w_t}.$$

Wie im oben erwähnten Artikel genauer beschrieben, bezeichnet $w_t$ den relativen Kurswert im Monat $t$ und $m$ die Gesamtzahl der Monate. Als Anfänger der funktionalen Programmierung habe ich bisher vornehmlich map, filter und reduce eingesetzt. Um die Formel mit den eben genannten Funktionen in der funktionalen Sprache Elm zu implementieren, habe ich das Produkt im Nenner für jeden Summanden vollständig berechnet, wie ab Zeile 4 des folgenden Schnipsels zu sehen ist.

nMonths = List.length relativePrices
inversePartialProduct k = 
    1 / (List.take k relativePrices |> List.product)
inverseProducts = 
    List.map 
        inversePartialProduct
        (List.range 1 (nMonths - 1))

Des Nachvollziehens wegen sei der gewillte Leser ermutigt, in die folgende Version des Tools 399 als Anzahl der Jahre einzugeben.

Die Laufzeitkomplexität ist also unnötigerweise quadratisch. In imperativer Programmierung würde ich den Nenner aus dem vorherigen Summanden in einer Veränderlichen zwischengespeichert haben. Die Veränderliche könnte dann für den aktuellen Summanden durch Multiplikation mit dem relevanten relativen Kurswert zum richtigen Nenner mutiert*Mutationen und Mutanten im biologischen Kontext, wie wir sie als Corona gepeinigte Generation aus den Medien kennen, implizieren eine zufällige Veränderung. Bei der Veränderung von Veränderlichen redet man gerade im Englischen auch in der Programmierung von Mutierbarkeit. Die Veränderung, auch wenn es ihr gestattet ist, muss aber nicht zufällig sein. werden. Derartige Zustandsänderungen sind in funktionaler Programmierung nicht möglich. Zustände sind immer konstant. Erfreulicherweise gibt es eine im doppelten Sinne funktionale Antwort auf mein Problem. In der Suchmaschine meines Misstrauens habe ich nach der Berechnung von Folgen von Partialsummen in funktionaler Programmierung gesucht. Dadurch bin ich über die Funktion scanl aus der funktionalen Programmiersprache Haskell gestolpert. Diese bildet eine Liste auf partielle Reduktionen ab. Das heißt, mit scanl lässt sich $$(w_1,\dots,w_m)\mapsto (\prod_{k=1}^1 w_k, \dots, \prod_{k=1}^m w_k)$$ effizient*Da es sich bei `scanl` um eine Funktion der Standardbibliothek handelt, habe ich ihr effiziente Umsetzung unterstellt. umsetzen. Volltreffer! Warum stellt Elms Standardbibliothek eine solche Funktion nicht bereit? Es hat sich herausgestellt, dass auch Elm diese Funktion früher bereitgestellt hat, sie aber komischerweise verbannt worden ist. Jedenfalls gibt es zum Glück eine Implementierung von scanl in der Elm-Bibiliothek List.Extra. Der neue Schnipsel

nMonths = List.length relativePrices
inverseProducts =
    List.take (nMonths - 1) relativePrices
        |> List.Extra.scanl1 (*)
        |> List.map (\partialProduct -> 1 / partialProduct)

ist in der Tat deutlich effizienter, was auf eine gute Implementierung scanls*Wir rufen hier zwar `scanl1` auf, das im Gegensatz zu `scanl` die Reduktionen ohne extra Startwert durchführt. Aber `scanl1` verwendet seinerseits wahrscheinlich das allgemeinere `scanl`. mit linearer Laufzeit in der Bibliothek List.Extra hinweist. Den Rechner habe ich auf einer Extraseite persistiert.