Sunday, July 29, 2007

Programming in Haskell (durch die C#-Brille gesehen)

Während des letzten Monats habe ich das Buch 'Programming in Haskell' durchgearbeitet. Es hat mir einen guten Einblick in die Welt der funktionalen Programmierung ermöglicht. Obwohl ich mir nicht die Zeit nahm jedes Beispiel und jede Übung bis ins letzte Detail zu verstehen, habe ich doch einige Konzepte verstanden welche meine Arbeit als Softwareentwickler in Zukunft beeinflussen werden. Folgende Punkte waren für mich neu und haben mich beeindruckt:

Abstraktion auf Ebene von einzelnen Funktionen und Operationen
Folgender C#-Code berechnet die laufende Summe über einen Array von Integers:
 public static int[] GetLaufendeSumme(int[] values)
{
int[] summierung = new int[values.Count()];
int sum = 0;
for( int i=0; i<values.Count(); i++ )
{
sum = values[i] + sum;
summierung[i] = sum;
}
return summierung;
}

In Haskell habe ich nun mit Hilfe der Funktion foldl folgende Lösung gefunden:

getLaufendeSumme :: [Int]->[Int]
getLaufendeSumme = foldl (
\summen wert -> case summen of
[] -> [wert]
otherwise -> summen++[wert + last summen] ) []


Da foldl das Iterieren und Berechnen von neuen Werten aufgrund der iterierten Werten abstrahiert ist der Haskellcode im Vergleich zum C#-Beispiel ausdruckstärker. foldl ist somit ein Pattern welches in ähnlichen Situation wieder angewendet werden kann. Im Gegensatz zu einer for-Schleife in C# ist mit foldl die Absicht und das Funktionieren des Codes klar.

Lazy Evaluation
Mit Layz Evaluation sorgt der Intepreter dafür, dass ein Ausdruck erst dann ausgewertet wird wenn der Wert des Ausdrucks benötigt wird. Bei Haskell werden alle Ausdrücke standardmässig mit 'Lazy Evaluation' aufgelöst. Nur Dank dieser Technik ist es möglich mit unendlichen Listen zu arbeiten. Im folgenden Bespiel definiert die Funktion fibs alle Fibonacci-Zahlen. Mit der Funktion fibGT kann dann die erste Fibonacci-Zahl, welche grösser als ein bestimmter Wert ist, gefunden werden.
fibs :: [Integer]
fibs = [0,1]++[ a+b (a,b) <- zip fibs (tail fibs) ]

fibGT :: Integer -> Integer
fibGT n = head (dropWhile (\a->a<n) fibs)

Bei C# werden standardmässig alle Ausdrücke sofort evaluiert und das Arbeiten mit z.B unendlichen Listen ist nur durch die explitzite Verwendung eines Iterators (IEnumerable, IEnumerator, etc.) möglich.

Pattern Matching
'Pattern Matching' hilft dabei, eine Funktion für verschiedene Fälle getrennt zu implementieren. So entscheidet der Haskell-Interpreter aufgrund der Argumente welche Funktionsimplementation für den aktuellen Fall herbeigezogen werden muss. So sind zum Bespiel folgende Funktionsdefinitionen für sumInt und sumInt2 gleichwertig:

sumInt :: [Integer] -> Integer
sumInt (n:ms) = n + sumInt ms
sumInt [] = 0

sumInt2 :: [Integer] -> Integer
sumInt2 ns = if ns == [] then 0
else (head ns) + sumInt2 (tail ns)

Während in der Funktion sumInt für den Fall '(n:ms)' und den Fall '[]' zwei Implementationen gemacht wurden, wird in der Funktion sumInt2 alles innerhalb einer Implementation mit Hilfe von if-Entscheidungen behandelt.



Induktives Denken

Folgender Haskell-Code berechnet die Fibonacci-Zahlen (0,1,1,2,3,5,8,13,21...)


fibs :: [Integer]
fibs = [0,1]++[ a+b (a,b) <- zip fibs (tail fibs) ]

Mich fasziniert an dieser Lösung, dass der Code nicht 'imperativ' als Anweisung verstanden werden kann. Der Haskell-Code oben lässt mich folgendes denken:
  1. fibs liefert mir alle Fibonacci-Zahlen
  2. Die Fibonacci-Zahlen beginnen mit 0 und 1
  3. Die weiteren Zahlen berechne ich indem ich die Fibonacci-Reihe mit der um eins verschobenen Fibonacci-Reihe pro Zahl kombinieren und pro Kombination die Zahlen zusammenzähle.

Für mich ist diese Denkweise ungewohnt, da die Definition der Funktion fibs davon ausgeht dass fibs (bereits) die korrekten Fibonacci-Zahlen zurückliefert. Auch hat die Funktion deklarativen Charakter. Es werden nämlich nur die Berechnungsregeln beschrieben. Wie und wann welche Berechnung erfolgt ist nicht ersichtlich.