Ich habe mich gefragt, wie ich eine Funktion in Haskell schreiben könnte, die eine Liste von Listen in eine einzelne Liste einfügt, zum Beispiel, wenn ich eine Funktion namens
hätte interleavelists :: [[a]] -> [a]
sollte in der Lage sein, die Elemente zu verschachteln.
Beispiel: [[1,2,3] [4,5,6] [7,8]] --> [1,4,7,2,5,8,3,6] .
Die Listen können sowohl endliche als auch unendliche sein ... Kann ich foldr verwenden?
Am schnellsten schreiben Sie transpose von Data.List .
transpose wählt das erste Element jeder nicht leeren Liste seines Arguments aus und fügt sie in eine Liste ein. Danach folgt transpose s der Liste von tail s der Elemente des Arguments. concat Das Auflisten der Listen von transpose führt dazu, dass die Listen wie gewünscht verschachtelt werden. Es funktioniert, wenn einige Elementlisten unendlich sind, aber wenn die Liste der Listen selbst unendlich viele Elemente enthält, kommt sie natürlich nie über die Liste von head s hinaus. Aber die Handhabung dieses Falls ist ohnehin problematisch.
Die Verwendung von foldr zum Verschachteln der Listen ist nicht trivial. Angenommen, du hättest
interleavelists [] sollte wahrscheinlich [] ergeben, also wäre das der zero -Wert. Und
scheint natürlich, also
%Vor% Aber was, wenn das zweite Argument nicht [] ist? Dann wollen Sie die Elemente des ersten Arguments von something in unterschiedlichen Abständen in das zweite Argument einfügen. Aber in welchen Entfernungen? Wenn alle Listen dieselbe Länge haben, sind die Abstände für jede Liste konstant, dann könnten Sie die Entfernung als weiteren Parameter übergeben,
Das ist nicht sehr hübsch, und wenn die Listen nicht alle gleich lang sind, ergibt sich was wahrscheinlich nicht die gewünschte Ausgabe ist. Aber wenn die Listen alle die gleiche Länge haben, macht es den Job.
Der "Standard" (oder vielleicht, berühmte) Weg, Listen zu verschachteln, war an den schönen Tagen von SICP (und später, Reasoned Scheme),
%Vor% Es kann mit foldr ,
Dies erzeugt offensichtlich nicht das Ergebnis in der von Ihnen gewünschten Reihenfolge, aber OTOH funktioniert OK, wenn die Eingabeliste der Listen unendlich ist. Ich glaube nicht, dass es eine Möglichkeit gibt, beide Anforderungen gleichzeitig zu erfüllen, da wir nicht wissen können, ob eine Eingabeliste unendlich ist oder nicht.
Die obigen Ergebnisse sind, was die Funktion insertAtDistance von Daniels Antwort erzeugen würde, wenn sie geändert wird, um immer bei a einzufügen Entfernung von 1 anstelle von d+1 :
Wenn es mit d+1 definiert ist, erzeugt es "flaches" Interleaving, während foldr (++/) [] schiefes Interleaving erzeugt:
Tags und Links haskell list fold interleave