Über unsMediaKontaktImpressum
Andre Schütz 08. Januar 2020

Herangehensweisen und Konzepte der Funktionalen Programmierung mit Scala

Die Funktionale Programmierung ist ein deklaratives Programmierparadigma, bei dem die Beschreibung der Problemstellung im Vordergrund steht. Dabei geht es weniger darum, wie die konkrete Implementierung aussieht, als vielmehr um eine korrekte Spezifizierung dessen. Funktionen bilden das Kernstück der Funktionalen Programmierung. Diese werden miteinander verknüpft, als Parameter übergeben oder als Rückgabewert einer Funktion konstruiert. Dabei sollen keine Seiteneffekte auftreten und stets das gleiche Ergebnis bei den selben Ausgangswerten auftreten.

Da im funktionalen Stil die Funktionen auch gerne aus einer mathematischen Sichtweise betrachtet und spezifiziert werden, hat dies für die Beweisführung einen großen Vorteil. Durch das Vermeiden von Seiteneffekten findet keine unbedachte oder unbeabsichtigte Beeinflussung innerhalb der Funktionen statt. Rein die definierten Eingabewerte und der vorgegebene Rückgabewert bestimmen, welche Implementierung im späteren Verlauf angestrebt wird. Daher kann man davon ausgehen, dass eine Funktion stets den gleichen Rückgabewert liefert, wenn sie die identischen Eingabewerte bekommt.

Dieser Beitrag beinhaltet Kernpunkte der Funktionalen Programmierung. Dazu zählen u. a. Pure-Funktionen, Currying, Higher Order Functions, Folding, Implicits und der Gebrauch von Halbgruppen, Monoiden und Funktoren. Die Beispiele sind in der Programmiersprache Scala geschrieben.

Herausforderungen beim Umstieg von anderen Programmiersprachen

Kommt man eher aus den imperativen Programmiersprachen, kann es am Anfang schon eine Umstellung sein, eine seiteneffektfreie Form des Codes zu erreichen. Im imperativen Stil werden interne Zustände oftmals gekapselt und versteckt gehalten. Sich von dieser Art der Implementierung zu lösen bedarf meist ein wenig Zeit und Code Refactoring, nachdem die ersten Versuche unternommen wurden.

Auch das Verinnerlichen der mathematischen Theorien und Modelle, welche hinter der Funktionalen Programmierung stehen, ist am Anfang eher ein wenig einschüchternd. Teilweise werden viele Code-Beispiele und Spezifikationen in einer mathematischen Schreibweise gegeben oder mit den mathematischen Symbolen versehen. Daher ist es vorteilhaft, wenn man sich parallel zum Erlernen der jeweiligen Funktionalen Programmiersprache auch mit den Grundlagen der Kategorientheorie auseinandersetzt. Dazu zählen unter anderem Halbgruppen, Monoide, Funktoren oder Monaden. Genau vor diesen Herausforderungen standen wir, als wir unseren Fokus primär auf die Funktionale Programmierung legten.

Immutable und mutable – Datenstrukturen

Variablen können auf unterschiedliche Weise definiert werden. Auf der einen Seite geht es darum, ob die Datenstruktur selbst veränderbar ist und auf der anderen Seite, ob die Variable, welche die Datenstruktur darstellt, neu zugewiesen werden kann.

In diesem Zusammenhang gibt es die folgenden Definitionen für Variablen:

  • val: eine Variable, die nicht neu zugewiesen werden kann.
  • var: eine Variable, die neu zugewiesen werden kann, also veränderbar ist.

Bei den Datenstrukturen gibt es zwei unterschiedliche Typen. Sie unterteilen sich in:

  • immutable: Datenstrukturen, die selbst nicht verändert werden können.
  • mutable: Datenstrukturen, die veränderbar sind.

Zudem können die Variablentypen und die Datenstrukturtypen miteinander kombiniert werden. Dazu einige Beispiele, für häufig vorkommende Kombinationen.

// (1) This variable cannot be changed or re-assigned
val immutable: Int = 1

// (2) This variable can be re-assigned (overwritten)
// 	  But - we normally don't wan't that
var mutable: Int = 1
mutable = 2

// (3) Variable can not be re-assigned, but data structure can be changed
val mutableMap: scala.collection.mutable.Map[Int, String] =
  scala.collection.mutable.Map(1 -> "foo")
val changedmutableMap: scala.collection.mutable.Map[Int, String] =
  mutableMap.addOne((4, "pi"))

// (4) JUST DON'T do that !!!
var mutableSeq: scala.collection.mutable.Seq[String] =
  scala.collection.mutable.Seq("NO NO NO")

 

Abb. 3 kann helfen, die  feinen Unterschiede besser zu behalten. Sich der Besonderheiten und Eigenschaften von unterschiedlichen Variablentypen und Datenstrukturen bewusst zu sein, kann dabei helfen, Fehler zur Kompilier- und Ausführungszeit zu vermeiden.

Seiteneffekte vermeiden

Von einem Seiteneffekt wird gesprochen, wenn man einen Zustand außerhalb der eigenen lokalen Umgebung verändert. Das kann dann mitunter dazu führen, dass sich Rückgabewerte einer Funktion ändern, selbst wenn die übergebenen Parameterwerte gleich geblieben sind. Dadurch verliert die Funktion ihre deterministische Zuverlässigkeit und das Testen wird umso schwerer.

Zu den Seiteneffekten innerhalb einer Funktion gehören u. a.:

  • Das Verändern einer globalen Variablen.
  • IO vom System oder an das System.
  • Veränderung einer mutable Variablen, welche als Funktionsparameter übergeben wurde.

Im folgenden Beispiel werden innerhalb der Methode mehrere Seiteneffekte vor dem eigentlichen Rückgabewert produziert.

var changeMe = "FOO"

/**
 * This function returns the calculation of the provided function
 * with the given parameter. BUT – it contains two side-effects by
 * adapting a global variable and printing to STDOUT.
 *
 * @param a Variable of type A
 * @param f Function that returns a value of type B
 * @return Value of type B
 */
def mySideEffectGlobal(a: A, f: A => B ) : B = {
  changeMe = "BAR"
  println(s"SIDE_EFFECT changed global value: $changeMe")
  f(a)
}

Ein seiteneffektfreier Programmierstil erleichtert uns das Testen und die Wartbarkeit des Codes. Darüber hinaus bestehen keine Abhängigkeiten gegenüber internen und meist versteckten Zuständen und ein Refactoring der Codebasis ist zudem leichter durchführbar.

Polymorphismus und Currying

Polymorphismus wird genutzt, um generischen und damit wiederverwendbaren Code zu erstellen. Die Parameter und Funktionsdefinitionen erhalten dann keine konkreten Typdefinitionen und werden mit generischen Platzhaltern spezifiziert. So kann zum Beispiel eine List[T] einen beliebigen Typ T enthalten und daher für diverse Datentypen genutzt werden. Ebenso ist die Implementierung einer Funktion, welche eine generische Typenbezeichnung hat, für jeden Typ identisch.

Das folgende Beispiel definiert eine polymorphe Funktion, die anschließend für zwei konkrete Anwendungsfälle mit den erforderlichen Typen genutzt werden kann.

/**
 * Polymorphic function that dropped one element from
 * the provided list of elements.
 *
 * @param list  List of type A.
 * @tparam A    Type of the list.
 * @return List with one less element of type A.
 */
def dropOne[A](list: List[A]): List[A] = {
  list.drop(1)
}

dropOne[String](List[String]("1", "2", "3"))

dropOne[Int](List[Int](1, 2, 3))

Eine weitere häufig genutzte Technik ist Currying. Hierbei erfolgt eine Aufsplittung der Parameterliste in mehrere Parameterlisten. Dadurch ist es möglich, weniger Parameter an die Funktion zu übergeben, als diese definiert. Wir erhalten dann eine neue Funktion, welche die ausstehenden Parameter erwartet.

/**
 * Display the sum of the two provided numbers and make a 
 * nice string of it.
 *
 * @param s
tringA Prefix string
 * @param stringB Middle string
 * @param stringC Suffix string
 * @param numA    First numerical value
 * @param numB    Second numerical value
 * @return String with the sum.
 */
def sumAndAppend(stringA: String, stringB: String, stringC: String)(numA: Int, numB: Int): String =
  s"$stringA $numA $stringB $numB $stringC ${numA + numB}"

// We get a new function that expects two integer values
val newFunc: (Int, Int) => String =
	appendAndSumCurried("Sum of", "and", "is:")

NewFunc(3, 3) // Sum of 3 and 3 is: 6

Häufige Anwendungsfälle für das Currying sind:

  • Mehrfaches Verwenden einer Funktion mit gleichen Anfangsparametern aber unterschiedlichen Restparametern.
  • Übergabe von Parametern, wenn sie im Programmverlauf zur Verfügung stehen, ohne sich bereits genutzte Parameter merken zu müssen.

Higher Order Functions

Bei der rein funktionalen Programmierung unter Berücksichtigung von puren (seiteneffektfreien) Funktionen ist es von Vorteil, wenn man diesen auch andere Funktionen übergeben kann. Daher können auch Funktionen selbst als Werte angesehen und einer Variablen zugewiesen werden. Dadurch können sie in Datenstrukturen gespeichert werden, als ein Argument einer Parameterliste entgegen genommen werden und das Ergebnis einer Funktion als Rückgabewert sein. Ist in der Parameterliste eine Funktion als Parameter angegeben, wird diese Funktion auch als Higher Order Function (HOF) bezeichnet.

/**
 * Method that accepts an integer value and another function (f) that
 * executes a check onto that integer. (HOF)
 *
 * @param i The provided integer value.
 * @param f The provided function that executes a check.
 * @return `true` if the check was successful, `false` otherwise.
 */
def check(i: Int)(f: Int => Boolean): Boolean = f(i)

/**
 * Method that checks if the provided integer value is even.
 *
 * @param i Provided integer value.
 * @return `true` if the value is even, `false` otherwise.
 */
def isEven(i: Int): Boolean = i % 2 == 0

check(2)(isEven) // true

Als häufige Konvention hat sich ergeben, dass als Parameternamen die Buchstaben f, g oder h genutzt werden, sollte es sich um eine Funktion handeln, die an eine HOF übergeben wird.

Pattern Matching – Vorteile von Typisierung

Beim Pattern Matching kann man auch von einer Art Eintauchen in eine Datenstruktur sprechen. Die Datenstruktur oder der Datenwert wird einer Typprüfung unterzogen, um ein definiertes Pattern zu treffen. Dabei wird die Typprüfung mit dem Wort match eingeleitet. Im Körper werden dann eine Reihe von cases definiert, die jeweils einem konkreten Pattern entsprechen. Wird ein Pattern getroffen, gibt das match den Ausdruck, welcher auf der rechten Seite des Pattern steht, zurück.

Mit dem Pattern Matching lassen sich Grunddatentypen, selbst erstellte Datentypen und komplexe Datenstrukturen vergleichen.

Das folgende Beispiel ist eine Hilfsfunktion, welche ein Pattern Matching auf Grunddatentypen durchführt. Das Any in der Parameterliste wurde für das Beispiel gewählt und sollte, wenn möglich, durch einen selbst erstellten Datentyp ersetzt werden.

/**
 * Simple pattern matching helper that identifies basic data types.
 * !!! Please use_never `Any` if possible. Create concrete data type.
 *
 * @param s Provided data type
 */
def generalMatch(s: Any): Unit = s match {
  case Some(value)  =>  println(s"Optional value of: $value.")
  case None         =>  println("Found a None.")
  case (v1, v2)     =>  println(s"Pair or Tuple of : $v1 and $v2.")
  case l1 :: l2     =>  println(s"List of: $l1 (head) and $l2 (tail).")
  case _            =>  println(s"Found everything else: $s.")
}

generalMatch(Option(1))
generalMatch(None)
generalMatch(("2", 1))
generalMatch(List(1, 2, 3))

Das zweite Beispiel zeigt eine Hilfsmethode, welche einen selbst erstellten Datentyp und dessen abgeleitete Datentypen vergleicht.

/**
 * Nonsense definition to show some different types that could be matched.
 * @param value A value that depends on the type.
 */
abstract class myTypes(value: Any)

object myTypes {

  /**
   * Integer object that also has a value of type integer.
   */
  case class IntType(value: Int = 1) extends myTypes(value)

  /**
   * String object that also has a value of type string.
   */
  case class StringType(value: String = "foo") extends myTypes(value)

  /**
   * List object that also has a value of type list.
   */
  case class ListType(value: List[Int] = List(1,2,3)) extends  myTypes(value)

}
/**
 * Match the concrete objects of a class with different concrete types.
 *
 * @param t Information about the type and it's value.
 */
def typeMatch(t: myTypes): Unit = t match {
  case IntType(w)    => println(s"IntType with value: $w")
  case StringType(s) => println(s"StringType with value: $s")
  case ListType(l)   => println(s"ListType with value: $l")
  case _             => println("Found something else: $t")
}

typeMatch(IntType())		// IntType with value: 1
typeMatch(StringType())	// StringType with value: foo
typeMatch(ListType())		// ListType with value: List(1, 2, 3)

Die Vorteile des Pattern Matching sind unter anderem:

  • Es erhöht die Typensicherheit, da wir die überprüfte Datenstruktur auf ihren konkreten Datentyp bestimmen.
  • Es macht den Code in vielen Fällen besser lesbar und erleichtert die Wartbarkeit.

Folding

Für das Iterieren durch eine Collection, also zum Beispiel eine Liste, bieten sich die Methoden fold, foldLeft und foldRight an. Alle benötigen einen Startwert und die Collection, welche durchlaufen werden soll. Zusätzlich muss eine Funktion definiert werden, welche zwei Elemente erwartet und einen Wert zurück liefert, der vom gleichen Typ wie der Startwert ist.

Beim fold muss der Startwert vom gleichen Typ sein, wie auch die Elemente der Collection sind.

def fold[A1 >: A](z: A1)(op: (A1, A1) ⇒ A1): A1

Die Definition von fold bekommt einen Startwert z vom Typ A1 und eine Operation, die zwei Parameter vom Typ A1 erwartet und einen Rückgabewert vom Typ A1 liefert.

Sollen die Elemente der Collection von links nacht rechts durchgegangen werden, kann man foldLeft nutzen. Im Unterschied zu fold können hier die Elemente der Collection einen anderen Typ haben, als der übergebene Startwert.

def foldLeft[B](z: B)(op: (B, A) ⇒ B): B

Die Definition von foldLeft bekommt einen Startwert vom Typ B und eine Operation, welche zwei Parameter erwartet. Einer der Parameter ist vom Typ B und der andere vom Typ A. Der Rückgabewert der Operation ist wieder ein Wert vom Typ B. Dadurch ist es möglich, eine Collection zu durchlaufen, die Werte vom Typ A beinhaltet und als Einstiegswert den Startwert vom Typ B zu nutzen.

Ein foldRight funktioniert im Grunde wie das foldLeft. Der Unterschied zwischen diesen beiden ist, dass die Elemente der Collection von rechts nach links durchlaufen werden.

def foldRight[B](z: B)(op: (A, B) ⇒ B): B

Insbesondere beim Durchlaufen von Bäumen kann die Nutzung von fold-Methoden die Arbeit erleichtern.

val num = List(1, 2, 3, 4)

num.fold(0)(_ + _)
// 10

val letters = List("a", "b", "c", "d")

letters.foldLeft("")((n, e) => s"$n $e")
// a b c d

letters.foldRight("")((e, n) => s"$n $e")
// d c b a

 

Traits, Klassen und Objekte

Um eigene Datentypen zu definieren oder Schnittstellen zwischen Klassen bereitzustellen, werden in Scala Traits, Klassen und Objekte verwendet.

Ein Trait stellt ein abstraktes Interface dar, welches Felder zwischen verschiedenen Klassen definiert. Es kann auch als eine Art Schablone angesehen werden und optional zusätzliche Methodendefinitionen enthalten. Das einleitende Schlüsselwort für die Definition lautet trait und kann um ein sealed vorangestellt werden. Bei einem sealed trait müssen alle Implementierungen des Trait in der gleichen Datei erfolgen.

/**
 * A trait that just defines a title of the objects.
 */
trait Thing {
  def title: String
}

Eine Klasse kann man auch als ein Template ansehen, das definiert, welche Informationen und Eigenschaften die Objekte der Klasse aufweisen. Das Schlüsselwort class leitet eine Klassendefinition ein. Fügen wir noch ein case voran, erhalten wir eine case class, die auch ohne ein new erstellt werden kann, da sie automatisch eine apply-Methode besitzen, die sich um die Objekterstellung kümmert. Zuletzt können wir diesem Konstrukt noch ein final voran stellen, welches eine final case class definiert. Solche Klassendefinitionen lassen es nicht zu, dass abgeleitete Klassen diese verändern.

/**
 * A human person where the title is equal to the family name.
 *
 * @param title The family name of the human person.
 * @param age   The age of the person in years.
 */
final case class Human(title: String, age: Int) extends Thing

/**
 * An animal where the title is the species of the animal.
 *
 * @param title The species of the animal.
 * @param name  The name of the animal that was given by a human person.
 */
final case class Animal(title: String, name: String) extends Thing

Objekte werden mit dem Schlüsselwort object eingeleitet und erstellen einen Singelton Typ, den es nur ein einziges Mal geben darf. Man könnte das mit einer Klasse vergleichen, die eine bestimmte Instanz definiert. Objekte werden auch Module genannt und ihr Name ist auch gleichzeitig der Namespace, der importiert werden muss, wenn man auf die Methoden und Inhalte des Objektes zugreifen möchte.

Im Vergleich zu Klassen sind Objekte einfacher, aber nicht weniger nützlich und mächtig. Benennt man sie gleich einer existierenden Klasse, definiert man ein Companion-Objekt der Klasse. Dieses hat insbesondere im Bezug zum Compiler einige Besonderheiten, wie das automatische Nachschauen, ob das Companion-Objekt einen impliziten Decoder oder Encoder für die Klasse beinhaltet.

/**
 * Object singleton
 */
object Thing {
  /**
   * Method that prints the title of the Thing.
   *
   * @param t An object of the Thing class.
   */
  def printTitle(t: Thing): Unit = println(s"The title is: ${t.title}")
}

/**
 * Companion object of the Human class
 */
object Human {
  /**
   * Circe decoder for the Human class to decode JSON.
   * The compiler searches for this decoder in the companion object.
   */
  implicit val decode: Decoder[Human] = deriveDecoder[Human]

  /**
   * Circe encoder for the Human class to encode into JSON.
   * The compiler searches for this encoder in the companion object.
   */
  implicit val encode: Encoder[Human] = deriveEncoder[Human]
}

Rekursion und "tail recursive"

Rekursion ist ein zentrales Thema in der Informatik. In der Funktionalen Programmierung kann sie häufig vorkommen, da man sich weniger an iterativen Konstrukten bedient oder versucht, diese komplett zu vermeiden. Man spricht von einer Rekursion, wenn eine Methode oder Funktion sich so oft selbst wieder aufruft, bis eine Abbruchbedingung eingetreten ist. Ist die Abbruchbedingung falsch definiert oder tritt nicht ein, kann sich die Funktion theoretisch auch unendlich oft aufrufen. Nach dem Erreichen der Abbruchbedingung wird das zusammengesammelte Ergebnis zurück gegeben.

Das folgende Beispiel definiert eine rekursive Funktion, welche durch die Elemente einer Liste wandert und diese aufsummiert.

/**
 * Go recursively through the list of entries and summarize them.
 *
 * @param values The list of entries.
 * @return The sum of the entries of the list.
 */
def sumRecursive(values : List[Int]) : Int = {
  values match {
    case Nil => 0
    case l: List[Int] => l.head + sumRecursive(l.tail)
  }
}

Die Funktion sumRecursive ruft sich im zweiten Pattern des Pattern Matching wiederholt auf, wenn es weiterhin eine Liste vorfindet. Tritt das erste Pattern ein – eine leere Liste – ist dies gleichbedeutend mit der Abbruchbedingung.

Neben der einfachen Rekursion gibt es noch Tail recursive. Der Unterschied hierbei ist, dass der rekursive Selbstaufruf am Ende der Funktion stattfinden muss. Im vorherigen Beispiel ist das nicht der Fall, da zusätzlich zum rekursiven Aufruf auch noch eine Summierung stattfindet. Hat man eine Tail-recursive-Funktion kann man die Annotation @tailrec vor die Funktionsdefinition schreiben. Solche Funktionen verwenden den eigenen Stack Frame immer wieder und werden vom Compiler zusätzlich optimiert. Dadurch verbrauchen sie weniger Speicher und werden zudem auch schneller.

/**
 * Go recursively through the list and make it tailrec
 *
 * @param values The list of entries.
 * @return The sum of the entries of the list.
 */
@tailrec
def sumRecursiveTailrec(values : List[Int], sum: Int = 0) : Int = {
  values match {
    case Nil => sum
    case l: List[Int] => sumRecursiveTailrec(l.tail, sum + l.head)
  }
}

Zudem können die @tailrec-Definitionen auch innerhalb einer Methode implementiert werden.

/**
 * Recursively through entries of a list and use inner tailrec function.
 *
 * @param entries The list of entries.
 * @return The Integer result.
 */
def sumRecursiveInnerTailrec(entries: List[Int]) : Int = {
  @annotation.tailrec
  def loop(pos: Int, sum: Int) : Int = {
    if (pos == entries.length) sum
    else loop(pos + 1, sum + entries(pos))
  }
  loop(0, 0)
}

Eine rekursive Schreibweise ist nicht immer leicht zu lesen und kann unter Umständen den Code schwerer wartbar machen. Daher sollte man auch abwägen, ob eine Rekursion sinnvoll ist oder durch eine iterative Implementierung ersetzt werden kann. Es gilt: Lesbarkeit und Wartbarkeit sind vorzuziehen.

Implicits – und es ist im Scope

Funktionen oder Parameter, welche als implizit definiert sind, brauchen nicht direkt übergeben werden. Der Compiler sucht nach passenden Definitionen im aktuellen Scope und schaut, ob diese zu den erwarteten Anforderungen passen. Wenn er keine passende Definition findet, erhält man einen Compilerfehler. Mit dem Schlüsselwort implicit werden diese Funktionen oder Parameter definiert. Sie können weiterhin auch explizit (also konkret) zugewiesen werden, wenn man eine übersichtlichere Schreibweise bevorzugt. Wenn der Compiler nach einem impliziten Konstrukt sucht, schaut er zuerst in den direkten Scope, also die aktuell importierten Umgebungen. Werden hier keine gefunden, wird zudem das Companion-Objekt untersucht.

/**
 * Method that expects an implicit function for the multiplication
 * process.
 *
 * @param base  The provided integer value.
 * @param f     Multiplication method that executes the multiplication.
 * @return Result of the multiplication.
 */
def multiplier(base: Int)(implicit f: Int => Int): Int = f(base)

object implicits {

  /**
   * Implicit method.
   *
   * @return Result of the multiplication
   */
  implicit def mult3: Int => Int = _ * 3

}

// using it as anonymously defined function
val anonymousF = multiplier(2)(x => x * 2)

// using it explicitely
val explicitF = multiplier(2)(mult3)

// using it implicitely
val implicitF = multiplier(2)

Diese Art der Programmierung hat seine Vor- und Nachteile. Positiv kann man herausstellen, dass es das Schreiben von Boilerplate Code verringert, da einmal definierte Konstrukte automatisch überall hin übergeben werden. Zudem ist es möglich, auch bestehenden Datentypen neue Funktionen zuzuweisen, indem man einen Wrapper um sie herum konzipiert.

Oftmals ist es nachteilig, dass nicht immer sofort ersichtlich ist, woher die impliziten Funktionen und Parameter kommen. Teilweise müssen diverse importierte Umgebungen betrachtet werden, um die aktuell genutzte Implementierung zu finden.

Cats - Halbgruppen, Monoide und Funktoren

Die Grundlagen der Funktionalen Programmierung finden sich zu großen Teilen in den algebraischen Strukturen der Kategorientheorie. Wobei Kategorien ein mathematisches Modell von Strukturen widerspiegeln, welche durch ihre Objekte oder Elemente in wechselseitigen Beziehungen stehen. Im Grunde nutzen wir diese Strukturen jeden Tag, ohne es vielleicht zu wissen.

Eine erste einfache Struktur ist die Halbgruppe (Semigroup), die als Voraussetzung eine combine-Funktion hat.

  • combine: A o A => A

Ein combine verbindet zwei Werte eines Typs A und gibt wiederum einen Wert des gleichen Typs zurück.

import cats.instances.string._
import cats.Semigroup

//
// semigroup from cats
//
val s1: String = Semigroup[String].combine("My ", "Semigroup")
println(s1) // "My Semigroup"

val s2: Int = Semigroup[Int].combine(5, 3)
println(s2) // 8

Die Bibliothek Cats liefert für viele Strukturen schon fertige Implementationen frei Haus, so dass wir diese nicht mehr selbst zu definieren brauchen. Im obigen Beispiel nutzen wir einerseits die combine-Methode der Semigroup um zwei Zeichenketten miteinander zu verbinden. In gleicher Weise können wir combine auch für Integer-Werte nutzen, wobei diese im Gegensatz zu Zeichenketten nicht zusammengefügt sondern addiert werden.

Die darauf folgende Komplexitätsstufe stellen Monoide dar. Ein Monoid ist ein Datentyp, welcher monoidische Operationen und Gesetze beinhaltet. Wie eine Halbgruppe besitzt auch ein Monoid eine combine-Methode und zusätzlich noch ein Identitäts- oder Nullelement.

  • Combine: A o A => A
  • ident: Unit => A mit combine(ident, A) => A und combine(a, ident) => A

Das Identitätselement hat keine Auswirkung auf einen Typ A, wenn es zu dem hinzu gefügt wird. Daher führt ein combine von dem Identitätselement mit einem Wert von Typ A automatisch wieder zu dem identischen Wert A. Für Zeichenketten ist das Identitätselement (Nullelement) die leere Zeichenkette:

  • "foo" + "bar" => "foobar"
  • "" + "foo" => "foo" auch "foo" + "" => "foo"

Zudem gilt das Gesetz der Assoziativität, welche für unterschiedliche monoide Datentypen zutrifft.

  • Zeichenketten: s1 + (s2 + s3) === (s1 + s2) + s3
  • Integer: (x +y) + z === x + (y + z)
import cats.Monoid
import cats.syntax.monoid._
import cats.instances.int._
import cats.instances.string._
import cats.instances.option._

//
// monoid from cats
//
val m1: String = Monoid[String].combine("My ", "Monoid")
println(m1) // "Hi there"

val m2: String = Monoid[String].empty
println(m2) // ""

val m3: Int = Monoid[Int].combine(1, 2)
println(m3) // 3

/**
 * Generic function that accepts different types to combine them.
 *
 * @param values  The values that should be combined.
 * @param monoid  Monoid with the specified laws of the type.
 * @tparam A      Type of the provided values.
 * @return Added result.
 */
def addAll[A](values: List[A])(implicit monoid: Monoid[A]): A =
  values.foldRight(monoid.empty)(_ |+| _)

val m5: Int = addAll(List(1, 2, 3))
println(m5)		// 6

val m6: Option[Int] = addAll(List(Some(1), None, Some(2)))
println(m6)		// Some(3)

val md7: String = addAll(List("I", " am ", " a ", " sentence."))
println(md7)	// I am  a  sentence.

Haben wir es mit komplexeren Datenstrukturen zu tun, bei denen die Daten in einen weiteren Kontext verpackt sind, kommen Funktoren ins Spiel. Ein Funktor ist im Grunde ein Mapping zwischen Kategorien, z. B. A und B, wobei die Werte der Kategorien in einem Container (Kontext) gebettet sind. Darüber hinaus muss ein Funktor die folgenden Bedingungen erfüllen:

  • Einen Wert aus dem Kontext (Container) extrahieren.
  • Eine definierte Funktion auf den Wert anwenden.
  • Das Ergebnis der Funktion wieder in den Kontext (Container) einpacken.

Die Definition eines Funktor mit einem Typenkonstruktor F[_] ist folgendermaßen:

  • map: (A => B) => F[A] => F[B]

Um das anschaulicher zu erklären, kann man solch ein Konstrukt auf den Alltag übertragen. Sehen wir in einem Einkaufsladen eine Kiste mit Orangen, können wir diese nehmen und zu einer Orangenpressmaschine gehen. Dort werden die Orangen aus der Kiste herausgenommen, gepresst und Orangensaft hergestellt. Dieser wird in einer Flasche gefüllt und wiederum in die Kiste gepackt.

  • Kiste[Orangen] → F: Kiste[Orangen] => Kiste[Orangensafft] → Kiste[Orangensaft]

Wiederum gilt auch bei Funktoren das Gesetz der Assoziativität und das Vorhandensein eines Identitätselementes.

Im folgenden Beispiel demonstriert die map-Funktion anhand eines Option-Funktor, warum sich dadurch der Code verschlankt und leserlicher wird.

//
// Functor
//
// Option is a Functor; here it wraps a value of type Int
val x: Option[Int] = Some(1)
val y: Int = 2
val m: Int = 2

// adding an Int to an Option of Int and multiplying that by another
// Int without e.g. `map` looks like follows
val f1 = if(x.isDefined) Some((x.get + y) * m) else None
// wih `map`
val f2 = x.map(a => (a+y) * m)
// by using the associative law
val f3 = x.map(_ + y).map(_ * m)

Wer sich weitergehend mit den algebraischen Strukturen befassen möchte, kann sich Monaden und Applicative anschauen [1].

Fazit

Geschichtlich ist die funktionale Programmierung ein alter Hase. Ihre Grundlagen verdankt sie dem Lambda-Kalkül von Alonzo Church, der bereits 1936 dazu einen Bericht veröffentlichte [2]. Später hat insbesondere die Programmiersprache Lisp zu ihrer weiteren Verbreitung beigetragen [3]. Aufgrund dieser langen Zeit konnten sich gut durchdachte und ausgereifte Konzepte entwickeln. Diese erleichtern jedem Entwickler, selbst komplexe Aufgaben mit den zur Verfügung stehenden theoretischen Grundlagen anzugehen, leicht wartbaren Code zu schreiben und die Wiederverwendbarkeit zu erhöhen. Durch die mathematischen Grundlagen besteht zudem eine fundierte Basis, welche die Beweisbarkeit der Anwendungen erleichtert und eindeutige Ergebnisse liefert.

Autor

Andre Schütz

Andre Schütz ist Softwareentwickler und führt Beratungen und Vorträge zu einer Vielzahl von Themen rund um die Informatik, Softwareentwicklung, Prozessoptimierung durch.
>> Weiterlesen

Kommentare (0)

Neuen Kommentar schreiben