• Entwicklung/Architektur
  • Methoden
  • Programmiersprachen
• Betrieb
  • Datenbanken
  • Server
  • IT-Security
  • Speicher
  • Netzwerke
  • Virtualisierung
  • Verfügbarkeit
  • Künstliche Intelligenz
• Management und Recht
  • Projektmanagement
  • Digitalisierung
  • IT-Recht
  • IT-Selbständige
• Aktuelles
• Termine
• IT-Jobs

☰

• Entwicklung/Architektur
• Betrieb
• Management und Recht
• News
• IT-Jobs
• Newsletter

Andre Schütz 08. Januar 2020

Herangehensweisen und Konzepte der Funktionalen Programmierung mit Scala

Herausforderungen beim Umstieg von anderen Programmiersprachen

Polymorphismus und Currying

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

Folding

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]

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