Unerwartetes Ergebnis beim Umkehren einer Liste

8

Ich brauche eine Erklärung für das unerwartete Ergebnis des unten stehenden Codes, anscheinend aufgrund eines Fehlers.

%Vor%

Liegt das an einem Bug?

    
TommyQ 14.11.2011, 03:41
quelle

5 Antworten

17

Wenn Sie ein völlig unerwartetes Ergebnis erhalten, insbesondere mit einer relativ einfachen Funktion wie dieser, kann es hilfreich sein, die Logik von Hand zu verfolgen. Lass uns sehen, was hier passiert:

%Vor%

Sie können sehen, wohin das geht. Das Problem ist einfach; Sie kehren nur den falschen Teil der Liste im rekursiven Schritt um. Anstatt den Schwanz umzukehren, wie Sie es jetzt tun, wollen Sie alles außer dem letzten Element umkehren. Sie könnten es also in etwa folgendermaßen überarbeiten:

%Vor%

was zurückgibt, was Sie erwarten würden: reverse' [1,91,99,20,1,6,5,2,8,0] = [0,8,2,5,6,1,20,99,91,1]

    
Jeff Burka 14.11.2011 03:58
quelle
11

Da andere bereits auf den Fehler hingewiesen haben, möchte ich Ihnen eine nützliche und elegante Technik zeigen, die oft in solchen Fällen angewendet werden kann und oft zu effizienten Algorithmen führt: Verwenden Sie einen Akkumulator.

%Vor%

Sie haben also eine Unterfunktion mit einem zusätzlichen Argument (dem "Akkumulator"), das sammelt, was Sie bereits haben. Offensichtlich müssen Sie im Basisfall dieses Ergebnis zurückgeben, weil Sie fertig sind. Der rekursive Fall ist hier sehr einfach: Es ist, als hätte man einen Stapel Platten, die man nacheinander von oben nimmt und einen neuen Stapel bildet, indem man einen nach dem anderen oben hinzufügt. Dieser resultierende Stapel wird umgekehrt, genau wie wir ihn brauchen.

Beachten Sie, dass Sie diese Umkehrung für einige andere Anwendungen dieser Technik nicht wünschen, die durch Einfügen eines reverse im Basisfall behoben werden kann.

    
Landei 14.11.2011 07:50
quelle
6

Die minimale Korrektur Ihres ursprünglichen Codes ist wohl

%Vor%

d. Sie haben die Unterelemente Ihrer Liste in falscher Reihenfolge kombiniert.

Dies ist natürlich immer noch ein quadratischer Algorithmus. Sie erhalten eine iterative Version, indem Sie zuerst

beobachten %Vor%

und dann gruppieren und halten so gebildete Zwischenergebnisse in einem separaten Akkumulator Argument, wie in einer früheren Antwort darauf hingewiesen wurde:

%Vor%

Nachdem Sie Ihr Arbeitspferd gefunden haben, richten Sie es mit einer geeigneten Schnittstelle ein,

%Vor%

(plus einige Randfälle).

    
Will Ness 14.11.2011 10:24
quelle
2

Beim Spielen mit Data.Monoid habe ich die folgende alternative, leicht rubin-goldbergische Lösung gefunden:

%Vor%     
Landei 02.05.2012 09:50
quelle
0
%Vor%     
neoplay 24.10.2013 17:03
quelle

Tags und Links