Haskell-Intensivkurs: Ein kompakter Einstieg in die by Marco Block, Adrian Neumann

Show description

Mit dem Algorithmus von Eratosthenes lassen sich Primzahlen kleiner oder gleich einer vorgegebenen Obergrenze erzeugen. Für unser folgendes Beispiel sollen alle Primzahlen bis 40 erzeugt werden. Dazu notieren wir uns zunächst alle Elemente von 2 bis 40 in einer Liste. Die 2 als erstes Element der Liste stellt eine Primzahl dar (s. Abb. 2). Die grauen Zahlen sind noch Primzahlkandidaten. Wir können die 2 als Primzahl markieren und streichen alle Vielfachen von 2 aus der restlichen Liste. Abb. 2 Die oberste Abbildung zeigt die Startliste, bei der die 2 als kleinste Primzahl definiert ist.

Da der (:)-Operator eine Liste in zwei Teile zerlegt, lässt sich auch die restliche Liste ohne das erste Element als Funktion angeben: rest :: [a] -> [a] rest (_:xs ) = xs Das Pattern (_:xs) bedeutet: Ignoriere den Kopf der Liste und nenne den Rest xs. Der Datentyp des Rückgabewerts xs ist demzufolge nicht a, sondern eine Liste vom Typ a. 1 Listen 53 Hugs > rest " hallo " " allo " Hugs > rest [] Program error : pattern match failure: rest [] Für den Rest einer leeren Liste gibt es kein Pattern, daher liefert Hugs einen Fehler.

3 Kaskadenförmige Rekursion Es gelten die gleichen Bedingungen wie bei der linearen Rekursion, mit folgender Ausnahme: Sollten mehrere Funktionsaufrufe der Funktion f in einem Zweig vorkommen, sprechen wir von einer kaskadenförmigen oder baumartigen Rekursion. Ein typisches Beispiel für eine kaskadenförmige Rekursion ist die Definition der berühmten Fibonacci-Zahlen: f ib(0) = 0 f ib(1) = 1 f ib(n) = f ib(n − 1) + f ib(n − 2) , für n > 1 In Abb. 1 wird die Abarbeitung durch ein Beispiel deutlich.