Haskell
Einstieg
Haskell ist eine general purpose language, die nach dem Logiker Haskell Curry benannt ist. Haskell erlebt gerade eine Renaissance from resarch to practical language . Initiiert wurde die Renaissance durch Sprachen wie C++, Python, Ruby, und Javascript, die zunehmend funktionale Elemente aufnehmen. Obwohl diese Sprachen nicht rein funktional sind, erlauben sie das Programmieren in einem higher order style.
Einstiegsliteratur
Kernidee
Programme bestehen aus einer Auswertung von Funktionen, die weder einen Zustand noch veränderliche Daten kennen. Funktionen sind Funktionen im mathematischen Sinn. Ihr Ergebnis hängt nur von der Eingabe ab.
Der Wert eine Funktion bleibt über den ganzen Programmverlauf gleich, so daß Funktionsaufruf durch den Wert der Funktion ersetzt werden kann (referential transparency).
Funktionen verhalten sich wie Lookup Table.
Herausforderung
- taming effects nach Simon Peyton Jones
Charakteristiken funktionaler Programmiersprachen
Allgemein
first class functions
Funktionen lassen sich
- zur Laufzeit eines Programmes erzeugen
- in Datenstrukturen speichern
- als Argument und Rückgabewert einer Funktion verwenden
- Funktionen sind Werten sehr ähnlich
- Beispiel:Dispatch table in Python
selectLam={
"+": (lambda x,y: x+y),
"-": (lambda x,y: x-y),
"*": (lambda x,y: x*y),
"/": (lambda x,y: x/y)
}
- um die Power Funktion zur Laufzeiterweitert, ergibt:
>>> selectLam["^"]=input("power: ")
power: lambda a,b: a**b
>>> for i in ("+","*","-","/","^"):
... print i + ": " , selectLam[i](3,4)
...
+: 7
*: 12
-: -1
/: 0
^: 81
>>>
Funktionen höherer Ordnung
higher order functions
Funktionen höherer Ordnung sind Funktionen, die entweder Funktionen als Argument annehmen oder als Rückgabewert liefern.
- Beispiele:
- Dekoratoren in Python
- mapFunktion in Haskell
Main> map (\x -> x*x) [1,2,3,4]
[1,4,9,16]
reine Funktionen
pure functions, expressions
- Gegenüberstellung von pure und impure aus Real World Haskell
Pure Impure Always produces the same result when given the same parameters May produce different results for the same parameters Never has side effects May have side effects Never alters state May alter the global state of the program, system, or world - Vorteile:
- Korrektheitsbeweise durchführen
- vereinfachtes Refaktoring
- unbenützte Funktionen oder Teilausdrücke können entfernt werden
- da die Ausgabe nur von der Eingabe abhängt, können die Ergebnisse zwischengespeichert werden
- da die Ausführungsreihenfolge der Funktion nicht relevant ist, können die Funktionsaufrufe umgeordnet oder auch parallel ausgeführt werden Optimierung durch den Compiler
- Beispiel:Die folgende Zusicherung gilt in Haskell, aber nicht in der imperativen Programmiersprache Python:
- Haskell:
*Main> let f10=func(10)
*Main> f10==func(10)
True - Python:
>>> f10= f(10)
>>> assert f10 ==f(10)
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
AssertionError - In Haskell kann jeder Aufruf von f(10) durch den Optimierer ersetzt werden, ohne das Verhalten des Programmes zu ändern.
- Haskell:
Rekursion anstelle von Schleifen und Zuweisungen
Variablen stehen für unveränderliche Werte und nicht für Speicherstellen, die verändert werden können.
- imperativ
>>> def fak(n):
... sum=1
... for i in range(1,n+1):
... sum = sum*i
... return sum
...
>>> fak(10)
3628800 - funktional
>>> def fak(n):
... if (n==1): return 1
... else: return n*fak(n-1)
...
>>> fak(10)
3628800 - Funktionen wie fold* in Haskell, reduce in Python oder accumulatein C++ formalisieren die Iteration durch eine Liste
- Haskell
Prelude> foldl1 (\x y->x*y) [1..10]
3628800 - Python
>>> reduce(lambda x,y:x*y,range(1,11))
3628800 - C++
for ( unsigned int i=1;i <= 10; ++i) intVec.push_back(i);
std::cout << "mult: " << std::accumulate(intVec.begin(),intVec.end(),1,_1*_2)<<"\n";
- Haskell
Verarbeitung von Listen
LISP steht für LISt Processing.
- Haskell
- map nachprogrammiert
myMap :: (t -> a) -> [t] -> [a]
myMap f [] = []
myMap f (x:xs)= f x: myMap f xs - ergibt
*Main> myMap (\x -> x*x) [1..10]
[1,4,9,16,25,36,49,64,81,100]
- map nachprogrammiert
- Python
- Map mit list comprehension
>>> [ x*x for x in range(1,11)]
[1, 4, 9, 16, 25, 36, 49, 64, 81, 100]
- Map mit list comprehension
- C++
- mit Boost::lambda
for ( unsigned int i=1;i <= 10; ++i) intVec.push_back(i);
std::transform( intVec.begin(), intVec.end(),intVec.begin(),_1*_1);
- mit Boost::lambda
Seiteneffekte
Funktionale Programmiersprachen, insbesondere Haskell, legen grossen Wert darauf, Seiteneffekte zu kontrollieren. Sie unterscheiden zwischen dem pure code und der outside world.
- Haskell: Monaden erlauben es, imperative Effekte in einem rein funktionalen Programm einzubetten.
Haskell
starke und statische Typisierung:
- While strong, static typing makes Haskell safe, type inference makes it concise.
- stark: keine implizite Typkonvertierung
- static: zur Compilezeit
- inference: Typen werden abgeleitet
Prelude> let add a b= a+b
Prelude> :type add
add :: (Num a) => a -> a -> a
Bedarfsauswertung
strict versus non-strict evaluation, outermost versus innermost evaluation, lazy evaluation
- bei der strengen Auswertung werden die Argumente vor den Funktionen ausgewertet
- Beispiel für (3 + 5)^2
- Bedarfsauswertung: (3 + 5)^2 = (3 + 5)*(3 + 5) = 8*8 = 64
- strenge Auswertung: (3 + 5)^2 = 8 ^ 2 = 8 * 8 = 64
- die feinen Unterschiede:
- Haskell:
Prelude> length([4, 3*2, 1/0])
3 - Python:
>>> len ( [ 4,3*2,1/0])
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
ZeroDivisionError: integer division or modulo by zero
- Haskell:
currying
Die Technik ist auch unter dem Namen Schönfinkeln bekannt und beschreibt die Umwandlung einer Funktion mit mehreren Argumenten func x y z in mehrere Funktionen mit je einem Argument (((func x) y) z ) (http://de.wikipedia.org/wiki/Currying).
In Haskell nimmt jede Funktion genau einArgument an. Gerne wird partielle Auswertung irrtümlich als currying bezeichnet.
- Beispiele:
- Haskell
add :: (Num a) => a -> a -> a
add a b= a+b
Prelude> add 1 2
3
Prelude> let addOne= add 1
Prelude> addOne 2
3 - Python (partielle Auswertung)
>>> from functools import partial
>>> def add(a,b): return a+b
...
>>> addOne= partial(add,1)
>>> addOne(2)
3 - C++ (partielle Auswertung)
#include <iostream>
#include <boost/bind.hpp>
#include <boost/function.hpp>
using boost::bind;
using boost::function;
int add(int a, int b){
return a+b;
};
int main(){
function<int(int)> addOne = bind(add, _1, 1);
std::cout << "1+2= " << addOne(2) << std::endl;
}
- Haskell
Weiterlesen...