Beispiel: Erzeugung von Primzahlen

Eratosthenes erfand die Siebmethode:
starte mit L=[2,3,4,5,...]
loop
entferne alle Vielfachen von head L aus L
end loop

wobei man als Invariante hat:
head L ist Primzahl, da von keiner kleineren Primzahl geteilt!
Also muß man unterwegs bloß alle head L ausgeben!

Die Schleife für das wiederholte Sieben läßt sich durch iterate realisieren, für das Sieben selbst definieren wir eine Funktion "`crossout"', die eine geeignete Anwendung von "`filter"' ist:

 -------------------------prime numbers






crossout::[Int]->[Int]         -elim multiples of head element

crossout (x:xs) = filter (\y->y`rem`x /= 0) xs






primeNumbers :: [Int]

primeNumbers = map head (iterate crossout [2..])






{-

Main> take 10 (crossout [2..])

[3, 5, 7, 9, 11, 13, 15, 17, 19, 21]

Main> take 10 primeNumbers

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

Main> take 1 (drop 9 primeNumbers)  - 10. Primzahl

[29]

Main> primeNumbers !! 9   -Indexierung mit (!!) beginnt mit 0

29

Main> primeNumbers !! 99

541

Main> primeNumbers !! 999






ERROR: Garbage collection fails to reclaim sufficient space

-}

[ [  2  3  4   5  ... ],
  [  3  5  7   9  ... ],
  [  5  7 11  13  ... ],
   ...
                       ]

die Primzahlen selbst kriegt man durch map head:

    +-+
[ [ |2| 3  4   5  ... ],
  [ |3| 5  7   9  ... ],
  [ |5| 7 11  13  ... ],
   ...
    +-+                ]