Warum "iteriert" das Prelude nicht den Knoten?

Question

Warum ist wie

iterate :: (a -> a) -> a -> [a] 
iterate f x = xs where xs = x : map f xs 

im Prelude nicht iterate definiert?

Answer 1

Das Binden des Knotens scheint die Freigabe nicht zu erhöhen.

Contrast mit:

cycle xs = let x = xs ++ x in x 

die Knoten hier Bindung hat den Effekt, eine kreisförmige verkettete Liste in einem Speicher zu schaffen. x ist ein eigener Schwanz. Es gibt einen echten Gewinn.

Ihre vorgeschlagene Implementierung erhöht die Freigabe nicht gegenüber der naiven Implementierung. Und dafür gibt es keine Möglichkeit - es gibt keine gemeinsame Struktur in so etwas wie iterate (+1) 0.

Answer 2

Die Prelude-Definition, die ich unten zur Verdeutlichung mit einschließe, benötigt keinen Overhead, um die Karte aufzurufen.

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

Just for fun, ich habe ein kleines schnelles Programm testen Sie Ihre iterate vs der Prelude - nur zur normalen Form zu reduzieren take 100000000 $ iterate (+1) 0 (Dies ist eine Liste von Int s). Ich lief nur 5 Tests, aber Ihre Version lief für 7.833 (max 7.873 min 7.667) während der Prelude war 7.519 (max 7.591 min 7.477). Ich vermute, der Zeitunterschied ist der Overhead von map, der angerufen wird.

Der zweite Grund ist einfach: Lesbarkeit.

Answer 3

In Ihrer Version gibt es keine Knotenbindung, es wird lediglich ein Zeiger auf der erzeugten Liste gehalten, um den Eingabewert für die nächste Iteration zu finden. Dies bedeutet, dass jede Listenzelle nicht gc-ediert werden kann, bis die nächste Zelle erzeugt ist.

dagegen die Version des Prelude verwendet iterate ‚s Aufrufrahmen für das, und da es nur einmal gebraucht wird, könnte ein guter Compiler wiederverwenden, dass ein Rahmen und mutiert den Wert darin, für mehr optimierten Betrieb insgesamt (und die Liste der Zellen sind in diesem Fall unabhängig voneinander).