sehr empfehlenswert
Eine zeitgemässe Einführung in die funktionale Programmierung mit Haskell.
Der Schwerpunkt bilden die klassischen Algorithmen der Informatik, also Suchen und Sortieren. Dabei werden frühzeitig die besonderen Möglichkeiten der funktionalen Programmiersprachen geschickt eingeführt und verwendet. Hier sind vor allem Higher-Order-Function, Algebraischen Datentypen und Lazy-Evaluation zu nennen. Haskell zeigt zudem die Stärken seines ausgeklügelten Typsystems.
1 Introduction 1.1 Algorithms 1.2 Functional languages 1.3 Bibliographical notes 2 Functional programming in Haskell 2.1 About the language 2.2 Equations and functions 2.3 Basic types and constructed types 2.4 Lists 2.5 Higher-order functional programming techniques 2.6 Algebraic types and polymorphism 2.7 Arrays 2.8 Type classes and class methods 2.9 Bibliographical notes 3 The efficiency of functional programs 3.1 Reduction order 3.2 Analysing the efficiency of programs 3.3 Program transformation 3.4 Conclusion 3.5 Bibliographical notes 4 Concrete data types 4.1 Lists 4.2 Trees 4.3 Arrays 4.4 Bibliographical notes 5 Abstract data types 5.1 Introduction 5.2 Stacks 5.3 Queues 5.4 Priority queues 5.5 Sets 5.6 Tables 5.7 Binary search trees 5.8 Heaps 5.9 AVL trees 5.10 Bibliographical notes 6 Sorting 6.1 Introduction 6.2 Comparison-based sorting 6.3 Basic sorting algorithms 6.4 Tree-based sorting 6.5 Efficiency of comparison-based algorithms 6.6 Representation-based sorting 6.7 Bibliographical notes 7 Graph algorithms 7.1 Definitions and terminology 7.2 The graph ADT 7.3 Depth-first and breadth-first search 7.4 Topological sort 7.5 Minimum spanning tree 7.6 Depth-first search trees and forests 7.7 Conclusion 7.8 Bibliographical notes 8 Top-down design techniques 8.1 Divide-and-conquer 8.2 Backtracking search 8.3 Priority-first search 8.4 Greedy algorithms 8.5 Bibliographical notes 9 Dynamic programming 9.1 Introduction 9.2 The dynamic programming higher-order function 9.3 Chained matrix multiplications 9.4 Optimal binary search trees 9.5 All-pairs shortest path 9.6 The travelling salesperson 9.7 Conclusion 9.8 Bibliographical notes 10 Advanced topics 10.1 Process network 10.2 Monads 10.3 Parallel algorithms 10.4 Bibliographical notes Bibliography A Haskell implementations B Mathematical background B.1 Notation B.2 Logarithms B.3 Summation formulas B.4 Solving recurrence equations Index
Wie immer, wenn ein Engländer Coauthor ist, dann kann man es auch lesen. Es liest sich gut, ist knapp und präzis.
Die Authoren legen ihren Schwerpunkt auf intuitive und pragmatische Implementationen der klassischen Alghorithmen. Die Wahl einer funktionalen Programmiersprache zeigt zu dem die Naehe von Algorithmendesign und Formalen Korrektheitsbeweisen. Sie richten sich zum einen an Studenten aber auch den Praktiker, mit dem Ziel funktionale Techniken zu verstehen und auch zu adaptieren.
Das Buch lohnt sich -- es ist kurz, hat gute Beispiele und bringt die Vorzüge der funktionalen Programmierung klar rüber.
Vor allem gefallen mir der Einsatz der Funktionen höherer Ordung mit Lazy-Evaluation (und algebraischen Datentypen), die enorm mächtige Abstraktionen mit nur wenigen Zeilen Code erlauben. Genau diese Konzepte hat Paul Graham im Sinne, wenn er über die Unzulänglichkeiten der OO-Sprachen schreibt.
Wer wirklich schwierige Algorithmen zu bauen hat, der sollte sich mit funktionaler Programmierung beschäftigen. Hier kann man wirklich ausführbaren Pseudocode schreiben.
Mein einziger Kritikpunkt ist, dass das Monad-Konzept nur sehr kurz und auch nur ziemlich am Ende angesprochen wird. Hier hätte ich mir 10 Seiten mehr gewünscht.
Fethi Rabhi, Guy Lapalme
1999, Addison-Wesley, ISBN 0-201-59604-0, 235 Seiten
Amazon: http://www.amazon.de/exec/obidos/ASIN/0201596040
Verlag: http://www.iro.umontreal.ca/~lapalme/Algorithms-functional.html
Eine schöne grafische Gegenüberstellung verschiedener Sortierverfahren findet sich auf dieser Seite: http://vision.bc.edu/~dmartin/teaching/sorting/anim-html/all.html Nett anzusehen, da animiert!
Functional Programming, Haskell, Algorithms
24-Aug-2003