inf-schule | Problemsituation

fold-Operatoren

Eine Zeichenkette aus einer Punktliste erzeugen

SVG ist eine Sprache, mit der man Vektorgrafiken beschreiben kann. SVG sieht dabei auch eine Beschreibung für Polygone vor. Teste selbst die Funktionsweise des polygon-Befehls. Beachte, dass die y-Achse in einer SVG-Darstellung nach unten zeigt.

Ziel ist es hier, aus einer Punktliste eine Zeichenkette zu erzeugen, die man als SVG-Darstellung eines Polygons verwenden kann. Hier ein Beispiel für eine solche Umwandlung.

[(20,30),(90,20),(80,40),(60,50)] -> "20,30 90,20 80,40 60,50"

Schritt 1: alle Punkte in einer Punktliste in Zeichenketten umgewandelt

[(20,30),(90,20),(80,40),(60,50)] -> ["20,30 ","90,20 ","80,40 ","60,50 "]

Beachte die zusätzlichen Leerzeichen am Ende der Zeichenketten. Die werden in Schritt 2 beim Zusammenfügen benötigt. Schritt 1 kannst du bereits selbstständig bearbeiten. In Aufgabe 1 findest du Hilfestellungen.

Schritt 2: alle Zeichenketten in einer Liste aneinanderfügen

["20,30 ","90,20 ","80,40 ","60,50 "] -> "20,30 90,20 80,40 60,50 "

Dieser Schritt lässt sich sehr gut mit einem fold-Operator umsetzen. Der hier benötigte fold-Operator wird weiter unten vorgestellt.

Schritt 3: das Leerzeichen am Ende der Zeichenkette entfernen

"20,30 90,20 80,40 60,50 " -> "20,30 90,20 80,40 60,50"

Schritt 3 dient nur dazu, das nicht benötigte Leerzeichen am Ende der Zeichenkette zu entfernen. Diesen Schritt kannst du mit der vordefinierten Funktion String.dropRight leicht erledigen.

Aufgabe 1

Hier geht es um Schritt 1: Alle Punkte in einer Punktliste werden in geeignete Zeichenketten umgewandelt.

(a) Entwickle eine Funktion stringAusTupel, die aus einem Punkt eine zugehörige Zeichenkette (mit zusätzlichem Leerzeichen am Ende) erzeugt. Ergänze hierzu die folgende Implementierung.

module Polygone exposing (..)

type alias Punkt = ( Float, Float )

punktToString: Punkt -> String
punktToString (x,y) =
    (String.fromFloat x) ++ ...

> import Polygone exposing (..)

> punktToString (20,30)
"20,30 " : String

(b) Die Funktion punktToString kannst du jetzt mit Hilfe des map-Operators nutzen, um alle Punkte einer Punktliste in Zeichenketten umzuwandeln.

module Polygone exposing (..)

type alias Punkt = ( Float, Float )
type alias Punktliste = List Punkt

punktToString: Punkt -> String
punktToString (x,y) =
    ...

punktlisteToStringliste: Punktliste -> List String
punktlisteToStringliste punktliste =
    ...

> import Polygone exposing (..)

> punktlisteToStringliste [(20,30),(90,20),(80,40),(60,50)]
["20,30 ","90,20 ","80,40 ","60,50 "]
    : List String

Zeichenketten aus einer Liste zusammenfügen

Wir betrachten das folgende Problem: Gegeben ist eine Liste aus Zeicheketten. Ziel ist es, alle diese Zeichenketten zu einer einzigen zu reduzieren. Das folgende sehr einfache Beispiel verdeutlicht die gewünschte Listenreduktion.

["a","b","c","d"] -> "abcd"

Eine solche Listenreduktion lässt sich direkt mit dem foldr-Operator durchführen.

> List.foldr (++) "" ["a","b","c","d"]
"abcd" : String

Der foldr-Operator erwartet als Übergabe eine Reduktionsfunktion (hier die Append-Funktion (++)), einen Akkumulator-Anfangswert (hier die leere Zeichenkette "") sowie die zu verarbeitende Liste (hier die Liste aus Zeichenketten ["a","b","c","d"]).

Die Funktionsweise des foldr-Operators kann man so verdeutlichen:

List.foldr (++) "" ["a","b","c","d"] ->
List.foldr (++) "d"++"" ["a","b","c"] ->
List.foldr (++) "c"++"d"++"" ["a","b"] ->
List.foldr (++) "b"++"c"++"d"++"" ["a"] ->
List.foldr (++) "a"++"b"++"c"++"d"++"" [] ->
"a"++"b"++"c"++"d"++"" ->
"abcd"

Die Reduktionsfunktion (++) wird benutzt, um ausgehend vom Akkumulator-Anfangswert "" schrittweise alle Elemente der Liste von reckts (daher fold-r) jeweils an den Akkumulator-Zwischenwert anzufügen.

Analog funktioniert der foldl-Operator:

> List.foldl (++) "" ["a","b","c","d"]
"dcba" : String

Hier wird die Reduktionsfunktion (++) schrittweise auf alle Elemente der Liste von links (daher fold-l) angewandt.

List.foldl (++) "" ["a","b","c","d"] ->
List.foldl (++) "a"++"" ["b","c","d"] ->
List.foldl (++) "b"++"a"++"" ["c","d"] ->
List.foldl (++) "c"++"b"++"a"++"" ["d"] ->
List.foldl (++) "d"++"c"++"b"++"a"++"" [] ->
"d"++"c"++"b"++"a"++"" ->
"dcba"