Unendliche Listen

• entstehen aus nicht-terminierenden Berechnungen (die Listen erzeugen),
• sind nützliches Zwischenergebnis zur Komposition von Teilberechnungen,
• sind praktikabel wegen lazy evaluation: unendliche Liste wird nicht komplett erzeugt, sondern nur soweit Bedarf besteht (es ist nützlich, sich vorzustellen, eine solche Liste sei tatsächlich vorhanden - vgl. Mathematik: z.B. {x < 100 | x N} obwohl man immer nur endliche Anfangsstücke braucht!)

Beispiel: Wiederholung ohne Ende:

 iterate :: (a->a)->a->[a]

iterate f x = x : (iterate f (f x))

also: [x, f x, f(f x), ...]

 Main> iterate (+2) 1

[1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, ...

1537, 1539, 1541, 1543, 1545, 1547, 1549, Interrupted!     -Control C

Main> take 5 (iterate (+2) 1)

[1, 3, 5, 7, 9]

(120 reductions, 209 cells)

Main> take 1 (drop 99 (iterate (+2) 1))

[199]

(1324 reductions, 1933 cells)

Main> take 10 [1..]

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

(239 reductions, 437 cells)

Main> take 10 [1,3..]

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

(224 reductions, 415 cells)

dabei Kurzformen wie:

Analyse:
take 2 (iterate (+2) 1)
take 2 (1 : iterate (+2) (1+2))
1 : (take 1 (iterate (+2) (1+2)))
1 : (take 1 (iterate (+2) 3))
1 : (take 1 (3 : (iterate (+2) (3+2)))
1 : 3 : (take 0 (iterate (+2) (3+2)))
1 : 3 : []