Implementierung nehmen foldr mit

Dies ist meine take Version mit foldr:Implementierung nehmen foldr mit

myTake n list = foldr step [] list 
       where step x y | (length y) < n = x : y 
           | otherwise = y 

main = do print $ myTake 2 [1,2,3,4]

Der Ausgang ist nicht, was ich erwarten:

[3,4]

Ich habe dann versucht, durch debuggen die Länge y in sich einfügen und das Ergebnis war:

[3,2,1,0]

Ich verstehe es nicht Warum werden die Längen in absteigender Reihenfolge eingefügt? Vielleicht etwas Offensichtliches, das ich vermisst habe?

Quelle

2013-04-08 badmaash

oder in Worten ist der Grund, dass '' y' in Schritt xy' genannt von 'foldr' steht ** nicht ** für *" Rest noch der Liste zu sein verarbeitet "*, ** aber ** für *" Ergebnis der Verarbeitung des Rests der Liste "*. Ihre Funktion sagt also: "Wenn die Länge des verarbeiteten Rests der Liste bereits" n "oder mehr ist, fügen Sie ihr nichts vor, sondern fügen Sie das aktuelle Element" * "voran. –

Wenn Sie take mit foldr implementieren möchten, müssen Sie das Durchlaufen der Liste von links nach rechts simulieren. Der Punkt ist, die Faltfunktion von einem zusätzlichen Argument abhängig zu machen, das die gewünschte Logik codiert und nicht nur vom gefalteten Ende der Liste abhängt.

take :: Int -> [a] -> [a] 
take n xs = foldr step (const []) xs n 
    where 
    step x g 0 = [] 
    step x g n = x:g (n-1)

Hier foldr gibt eine Funktion, die ein numerisches Argument nimmt und durchläuft die Liste von aus es erforderlich, die Menge unter links nach rechts. Dies funktioniert auch auf unendlichen Listen aufgrund von Faulheit. Sobald das zusätzliche Argument Null erreicht, wird foldr eine leere Liste kurzschließen und zurückgeben.

Quelle

2013-04-08 13:59:08 is7s

Visualization of <code>foldr</code>

foldr wird die Funktion step ausgehend von den * letzten Elemente ** an. Das heißt,

foldr step [] [1,2,3,4] == 1 `step` (2 `step` (3 `step` (4 `step` []))) 
         == 1 `step` (2 `step` (3 `step` (4:[]))) 
         == 1 `step` (2 `step (3:4:[])) -- length y == 2 here 
         == 1 `step` (3:4:[]) 
         == 3:4:[] 
         == [3, 4]

Die Längen „eingefügt“ in absteigender Reihenfolge, weil : ist ein Voranstellen Betrieb. Die längeren Längen werden am Anfang der Liste hinzugefügt.

_{(Bild genommen von http://en.wikipedia.org/wiki/Fold_%28higher-order_function%29)}

*: Der Einfachheit halber nehmen wir jeden Betrieb streng ist, die step Umsetzung in OPs wahr ist.

Quelle

2013-04-08 13:20:03 kennytm

"foldr" wendet die Funktion "step" an, ausgehend von den * letzten Elementen *. " Diese Aussage ist bestenfalls im Angesicht einer faulen Bewertung sehr irreführend. Haskell wertet Ihren zweiten Baum tatsächlich von links nach rechts aus, und wenn die "step" -Funktion bei ihrem zweiten Argument nicht strikt ist, kann sie die Berechnung vorzeitig abbrechen. Das einfachste Beispiel dafür ist 'safeHead = foldr (\ x _ -> Just x) Nothing'. –

Ich sollte hinzufügen, dass Ihre Sequenz von Evaluierungsschritten von inneren Funktionsanwendungen zu äußeren geht, was die * entgegengesetzte * Reihenfolge von dem ist, was Haskell tut. Der äußerste "Schritt" wird zuerst ausgewertet, der erste mit "1". Wenn 'step' sein zweites Argument nicht benötigt, endet die Berechnung dort, bevor der Rest der Elemente der Liste betrachtet wird. Wenn 'Schritt x _ = Nur x', dann 'foldr Schritt Nothing [1,2,3,4] == Schritt 1 (foldr Schritt Nothing [2,3,4]) == Nur 1'. –

@sacundim Aber der "Schritt" von der Frage ist streng in seinem zweiten Argument, so in diesem Fall hat 'fold' keine andere Wahl als vom Ende der Liste nach vorne zu arbeiten und den äußersten' Schritt' zu bewerten, Zuerst müssen die inneren 'Schritte' ausgewertet werden. Die Antwort würde davon profitieren, klarzustellen, dass es sich um eine spezielle Situation handelt, aber die Beschreibung ist für den gegebenen Code korrekt. –

Die anderen Antworten machen es viel zu kompliziert, weil sie zu sehr mit der Vorstellung verbunden sind, dass foldr "von rechts nach links" funktioniert. Es gibt einen Sinn, in dem es das tut, aber Haskell ist eine faule Sprache, also wird eine "von rechts nach links" -Berechnung, die einen Lazy-Fold-Schritt verwendet, tatsächlich von links nach rechts ausgeführt, wenn das Ergebnis konsumiert wird.

Studie dieser Code:

take :: Int -> [a] -> [a] 
take n xs = foldr step [] (tagFrom 1 xs) 
    where step (a, i) rest 
       | i > n  = [] 
       | otherwise = a:rest 

tagFrom :: Enum i => i -> [a] -> [(a, i)] 
tagFrom i xs = zip xs [i..]

Quelle

2013-04-08 17:18:57

Antwort

Verwandte Themen