Vorlesung: Praxis der Funktionalen Programmierung


Map für Bäume, class Functor

Eine besonders einfache Klasse von rekursiven Funktionen auf Bäumen sind die, welche einen Baum gleicher Struktur herstellen, und dabei nur Schlüsselwerte ändern (Quelltext). Hausaufgabe: schreibe tmap als tfold.

Die Funktion tmap hat vieles mit map auf Listen gemein. Die Gemeinsamkeiten fassen wir zu einer Konstruktorklasse zusammen: jeder Typkonstruktor c, der eine Funktion fmap :: (a -> b) -> (c a -> c b) besitzt, die bestimmte Eigenschaften erfüllt, heißt Funktor. (Das hat auch tatsächlich eine kategorientheoretische Bedeutung. Weil wir hier aber keine Theorievorlesung ...) Die Eigenschaften sind

fmap id         = id
fmap f . fmap g = fmap (f . g)
Diese können wir auch bei Programmtransformationen benutzen. Wahrscheinlich ist fmap (f . g) effizienter als fmap f . fmap g, weil wir keine Liste mit Zwischenergebnissen aufbauen müssen. Aus softwaretechnischen Gründen ist fmap f . fmap g jedoch vorzuziehen (die Wirkungen von f und g sollen getrennt augeschrieben werden).

best viewed with any browser


http://www.informatik.uni-leipzig.de/~joe/ mailto:joe@informatik.uni-leipzig.de