Rekursion und und unendliche Listen

Bachelor Parallele und funktionale Programmierung
1

Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.

2

Rekursion und und unendliche Listen
Hi ich hab da mal ne frage zu den tollen unendliche Listen. Und zwar hab ich folgendes “Programm”

eins x = 1:x
rek f xs = rek f ( f xs)

Die Intention ist das wenn ich rek eins [] eine unendliche Liste mit einsern dabei rauskommt ( ja es geht einfacher aber ich will es mit Rekursion machen oder geht das gar nicht Rekursion und unendliche Liste??)

Dabei soll eins jeweils 1 eine an eine Liste anhängen und rek soll das Rekursiv immer wieder für einer Liste machen.

Leider bekomm ich immer folgenden Error: ERROR - Garbage collection fails to reclaim sufficient space

Weiss jemand wie ich das anders machen kann bzw was ich falsch mach?

Danke!

3

Öhm, läuft eine “unendliche Liste” nicht auf eine Endlosschleife raus?

4

Probiers doch mal mit

eins = 1:eins

Ergibt:

Main> take 10 eins
[1,1,1,1,1,1,1,1,1,1]
5

nein tut sie nicht, Haskell kann auf Grund der Lazy Evaluation quasi mit „unendlichen“ Listen arbeiten

nun zur eigentlichen Frage, das Problem ist, dass die Rekursion die die unendliche Liste aufbaut an der „falschen“ Stelle ist, so wie es jens gesagt hat, geht es zum Beispiel, noch allgemeiner geht es zB so:

rek2 f x = (f x): (rek f x)
Main> take 10 (rek2 (+2) 1)
[3,3,3,3,3,3,3,3,3,3]

der rekursive Aufruf darf quasi nicht das äußerste sein, am einfachsten ist es sich die Ausdrücke auszuwerten:

rek' eins [] = rek' eins (eins []) = rek' eins (eins (eins [])) = rek' eins (eins (eins (eins []))) = rek' ...

dabei ensteht keine Liste sondern einfach nur ein seeehr rekursiver Aufruf wenn du aber zB folgendes betrachtest:

rek2 (+2) 1 = ((+2) 1) : rek (+2) 1 = ((+2) 1) : (((+2) 1) : rek (+2) 1) = ...

hier ist der rekursive Aufruf nur im tail und nicht schon weiter vorne (ich hoffe das hilft etwas)

6

Aha, das heißt das nächste Element wird erst berechnet, wenn es gebraucht wird?

7

ja dass heisst es!!

Also erst mal danke für die Hilfe!

Aber wie mache ich dann jetzt so eine Rekursion wenn ich für die Berechnung eines Elements immer z.b das letzte Element in der Liste brauche um z.b [1,2,3,4,…] auszurechnen?

8

Ich weiß jetzt nicht, wie es in der allgemeinen Form von Frozy aussehen würde, aber um deine [1,2,3,…]-Liste per Rekursion zu erzeugen würde ich folgendes machen:

zaehlen = zaehlen' 0
zaehlen' x = y:(zaehlen' y) where y = x+1

Oder z.B. um die Fibonacci-Zahlen zu erzeugen:

fibonacci = 1:1:fibonacci' 1 1
fibonacci' x y = a:(fibonacci' y a) where a = x+y
9

du schleppst den letzten Wert quasi immer mit, Beispiel natürliche Zahlen bzw. Fibonacci:

nat x = x : nat (x+1)
fib x y = x : fib y (x+y)
10

Ah danke habt mir sehr geholfen! :wink: