Fragen zur Funktionalen Programmierung

1. Was zeichnet eine funktionale Sprache aus?
Nur Ausdrücke keine Anweisungen, insbesondere keine Zuweisung, damit keine Seiteneffekte.

2. Wie ist das Ausführungsmodell einer funktionalen Sprache?
Werte ein Ausdruck zu einem Ergebnis aus.

3. Verzichten alle funktionale Sprachen auf Anweisungen?
Nein, von den bekannten Sprachen sind nur Haskell und Clean komplett ohne Anweisungen.

4. Welche funktionalen Sprachen gibt es?
F#, Haskell, Clean, ML, Lips, Scheme, Erlang, Miranda, Scala, Java 8

5. Was ersetzt Kontrollstrukturen (Schleifen) in funktionalen Sprachen?
Rekursion.

6. Muss dann nicht alles immer mit Rekursion programiert werden?
Ja, aber man definiert higher-order Funktionen, die z.B. eine Art Schleife ersetzen und durch Funktionen als Argument parametisiert werden.

7. Beispiel dazu?
Fold auch Reduce genannt.

8. Ist Rekursion nicht schlecht wegen wachsenden Stack?
Im allgemeinen ja, aber bestimmte Rekursionen kann der Compiler wegoptimieren. Tail-Call Optimization.

9. Was ist eigentlich so gut daran, dass es keine Seiteneffekte gibt?
Ein Ausdruck hat eindeutiges Ergebnis, egal vom Kontext. Hilft bei Beweisen über Programme und Optimierungen. Nennt man referentielle Transparenz.

10. Wonach kann man funktionale Sprachen klassifizieren?

11. Was bedeutet lazy evaluation?
Nicht-strikte Auswertung mit Sharing als Graph. Graph-rewriting, Graph-Ersetzung.

12. Und was ist non-strict?
Erst Funktionsdefinition expandieren und Argumente einsetzen (substituieren), statt erst die Arguente auszuwerten.

13. Was ist Haskell?
Ein Mathematiker: Haskell B. Curry.

14. Ja schon, aber was noch?
Eine lazy evaluierte, statisch getypte, rein funktionale Programmiersprache. Erstmals von einem Komitee 1992 definiert.

15. Wie sieht ein Haskell Projekt aus?
Einzelne Module, die Funktionalität exportieren.

16. Wie sieht ein Haskell Modul aus?
Funktions- und Datendefinitionen.

17. Wie Datendefinitionen aus?
data für algebraische Typen, type für Typsynonyme, newtype so dazwischen.

18. Was ist ein algebraischer Typ?
Eine Definition von Konstruktoren für einen neuen Typ.

19. Wie wird ein algebraischer Typ genannt, der nur Konstruktoren ohne Parameter hat?
Aufzählung.

20. Wie nennt man es, wenn ein Typ mehrere Konstruktoren hat?
Summentyp.

21. Was realisiert ein Konstruktor mit mehreren Parametern?
Einen Produkttypen.

22. Wie programmiert man Funktionen mit algebraischen Datentypen als Parameter?
Pattern matching. (Syntaktischer Zucker für Fallunterscheidung über case-Ausdrücke)

23. Was ist schlecht an Pattern-Matching?
Softwaretechnisch bei der Evolution von Programmen. Wenn ein Konstruktor ein zusätzlichen Parameter bekommt, müssen alle Pattern angepasst werden. Argumente der Konstruktoren haben keinen Namen sondern Reihenfolge ist relevant.

24. Was kann man gegen diese Nachteile tun?
Record-Syntax mit benamten Argumenten.

25. Wozu sind Typsynonyme sinnvoll?
Macht Programm lesbarer. Statt den Typ [Char] oder seinem Synonym String, kann man für spezielle Anwendungen einen anderen Namen dieses Typs wählen.

26. Kann man in Haskell Funktionen überladen.
Allgemein nein. Und gar nicht über die Anzahl der Parameter. Aber es gibt Typklassen, die ein wenig Java-Interfaces entsprechen. Keine ad-hoc Überladung.

27. Was gibt es so für Standard Typklassen?
Show, Eq, Ord, Num, Read, Monad, Functor

28. Was ist Monad?
Eine Typklasse mit drei Funktionen: return, >>= (bind), >> (then). Diese sollen so implementiert werden, dass sie die monadischen Gesetze erfüllen.

29. Wozu ist die Typklasse Monad gut?
Um in dem lazy Auswertungskontext von Haskell trotzdem eine Sequentialisierung zu erreichen. Insbesondere bei IO Funktionen. (Seiteneffekte kapseln.)

30. Weitere Beispiele für Monadenanwendungen?
State-Monade, Zustand durchreichen, Parser als spezialisierter Zustand, Fehlerbehandlung mit Maybe.

31. Was sind Parserkombinatoren?
Funktionen höherer Ordnung zum programmieren von Parsern: Sequenz, Alternative und ein map, zum Verändern des Ergebnisses.

32. Inwiefern hat die Typklasse Monad eine besondere Bedeutung in Haskell?
Eigene Syntax existiert, die DO-Notation.

33. Wie übersetzt die Do-Notation auf monadische Funktionen?
do
   akt1
   akt2
wird zu akt1 >> akt2.
do
    x <- akt1
    akt2 x
wird zu akt1 >>= \x -> (akt2 x)

34. Gibt es noch mehr Typklassen mit eigener Syntax?
Ja, zum Aufzählungen [1,3,..] und sogar Zahlenliteralen für alle Num Typen.

35. Was ist Currying.
Alle Funktionen sind eigentlich nur einstellig (also haben nur einen Parameter). Wenn man denkt man hat eine Funktion mit zwei Parametern, dann ist es eine Funktion mit einem Parameter, die eine Funktion als Ergebnis hat. (f x y) = ((f x) y)

36. Wer hat's erfunden?
Schoenfinkel.

37. Wie kann man jenseits des Pattern-Matching Fallunterscheidungen in Haskell programmieren?
Guards für die Unterscheidung nach bool'schen Ausdrücken.

38. Kann man Guards und Pattern-Matching mischen?
Ja. Erst wird nach einem passenden Pattern gesucht, dann nach einem passenden Guard.

39. Was ist otherwise?
Einfach nur ein anderer Name für True.

40. Was ist Boolean?
Algebraischer Enum Type: data Boolean = True|False

41. Wie macht man lokale Definitionen?
where oder let.

42. Können lokale Definitionen Variablen aus dem Kontext verwenden.
Ja. Das widerspricht aber nicht der referenziellen Transparenz.

43. Wie gehen anonyme Funktionen?
Mit Lambda-Ausdrücken,z.B. \x->x*x

44. Was ist der Lambda-Kalkül?
Ein Modell für mechanisches Berechnungen, um den Begriff der Berechenbarkeit zu definieren. Definiert als eine Art Termersetzungssystem.

45. Wie sieht die Syntax aus?
Strukturell induktiv definiert. Basisfall sind Variablen. Rekursive Fälle sind: Lambda-Abstraktion und Anwendung.

46. Was ist die Rekuktionsregel?
beta-Reduktion. Anwendung von Lamda-Abstraktion auf einen Argument. Substituiere lambda-gebundene Variable durch das Argument.

47. Was ist eine Normalform?
Ein Ausdruck, in dem nicht mehr die beta-Reduktion angewendet werden kann.

48. Was kann man bezüglich der Normalform im Lambda-Kalkül sagen.
Sie ist eindeutig, sprich egal welcher Rechenweg gewählt wird, es führt immer nur zu einer festen Normalform, einem eindeutigen Ergebnis.

49. Woran liegt das?
An der Konfluenz. Es gibt keinen falschen Rechenweg, der in eine Sackgasse führt.

50. Was kann im Lambda-Kalkül aber beim Versuch die Normalform zu errechnen passieren?
Das die Berechnung nicht terminiert.

51. Kann es passieren, dass die Berechnung nicht terminiert, obwohl es eine Normalform gibt?
Ja. Durch ungeschickte Wahl des reduzierbaren Ausdrucks.

52. Kann man das verhindern?
Ja! Durch normal-order reduction. Nehme immer den reduzierbaren Ausdruck, der als erster beginnt. Das entspricht non-strict Auswertung. Erst das Äußere auswerten. Im Gegensatz zu applicative order, reduziere den Ausdruck der als erster endet, sprich den ersten inneren. Entspricht der strikten Auswertung.