Inhaltsverzeichnis[Anzeigen]

 

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.
right 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
    the-challenge-of-effects.jpg

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
  • right 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

    PureImpure
    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 right 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
    • right In Haskell kann jeder Aufruf von f(10) durch den Optimierer ersetzt werden, ohne das Verhalten des Programmes zu ändern.

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";

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]
  • Python
    • Map mit list comprehension
      >>> [ x*x for x in range(1,11)]
      [1, 4, 9, 16, 25, 36, 49, 64, 81, 100]
  • 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);

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

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;

      }

Abonniere den Newsletter (+ pdf Päckchen)

Beiträge-Archiv

Sourcecode

Neuste Kommentare