Haskell größte Nummer aus einer Liste löschen

Question

Ich versuche herauszufinden, wie man eine rekursive Funktion erstellt, die das größte Element in der Liste findet und es löscht und dann die Liste zurückgibt. Dies ist, was ich bis jetzt habe, aber das Problem ist, dass jedes Mal, wenn ich es leite, die Liste ohne irgendwelche der Werte zurückgibt, die x zugewiesen sind.

deleteMax :: (Ord a) => [a] -> [a] 
deleteMax [] = [] 
deleteMax [x] = [] 
deleteMax (x:y:xs) 
    |x == y = y: deleteMax xs 
    |x >= y = y: deleteMax xs 
    |x < y = x: deleteMax xs 

Answer 1

Dies ist Sie nicht Ihre Antwort

So ein Anfänger und als solche würde die einfache Lösung wie „Wie finde ich das größte Element in einer Liste“, gefolgt von „Wie kann ich entferne (eines der) größten Elemente in der Liste ". Dies ist nicht diese Antwort, aber ich vermeide einen langen Kommentar und gebe dir auch etwas, auf das du in 3 Monaten zurückkommst.

The Lazy Way

Eine Lösung, die @ N · m. und ich habe mich in Kommentaren geärgert, soll den Knoten knüpfen (Googleable Begriff). Bei dieser Methode benötigen Sie nur einen logischen Durchlauf über die Liste. In diesem Fall ist es im Grunde genommen ein Trick, den Pass zu verbergen, der die Ergebnisliste konstruiert.

Die Idee ist, dass Sie während des Durchlaufs der Liste beide Aufgaben von 1 durchführen. Berechnen Sie das maximale Element und 2. Vergleichen Sie mit dem maximalen Element und konstruieren Sie die Liste. Es gibt hier nichts, die eine Monade erfordert aber es kann als ein Teil eines Staates Monade am einfachsten zu sehen sein:

deleteMaxState :: (Ord a) => [a] -> [a] 
deleteMaxState []  = [] 

Zunächst behandeln wir die Basis Fälle so haben wir einen Kandidaten ‚Maximum‘ (x) für unsere rekursive Operation .

deleteMaxState xs@(fstElem:_) = 
    let (r,(m,_)) = runState (go xs) (fstElem, notMax m) 
     notMax mx v = if (mx > v) then (v:) else id 
     go [] = return [] 
     go (x:xs) = 
      do (curr,f) <- get 
       when (x > curr) (put (x,f)) 
       f x <$> go xs 
    in r 

Im loopwe Spur zwei Werte der ersten, curr, ist der größte beobachtete Wert von diesem Punkt in unserem Durchlauf der Liste. Der zweite Wert, f, ist der Trick - es ist (eine Funktion einschließlich) der Maximalwert, der der Berechnung nach zur Verfügung gestellt wird, die Traversierung abgeschlossen hat.

Die Magie ist alles hier:

(r,(m,_)) = runState (go xs) (fstElem, m) 

Das linke Element des Ergebnisses Zustand (m,_) unsere laufenden Maximum war. Sobald die Traversierung beendet ist, verwenden wir diesen Wert - es wird das richtige Element (fstElem, m) und stellt somit das Maximum der gesamten Liste dar.

Wir können f verwenden, um Thunks zu erstellen, die Teile der Liste bevölkern oder einfach als Inline-Konstrukte unsere Liste als einen Haufen unbewerteter cons Berechnungen erstellen.

diese ein zu machen Jota einfacher, können wir die Funktion höherer Ordnung f und haben nur eine Nummer (ungetestet) entfernen:

deleteMaxState xs@(fstElem:_) = 
    let (r,(m,_)) = runState (go xs) (fstElem, m) 
     go [] = return [] 
     go (x:xs) = 
      do (curr,theMax) <- get 
       when (x > curr) (put (x,theMax)) 
       ((if x >= theMax then Nothing else Just x) :) <$> go xs 
    in catMaybes r 

Jetzt können wir den zweiten Durchgang ziemlich explizit nicht nur als unevaluierten Set sehen von "etwas Berechnung, die Maximum miteinbezieht, entsprach dem Ergebnis" aber als ein tatsächlicher Durchlauf über catMaybes.

Das Verknüpfen des Knotens ermöglicht es dem Programmierer, eine logische Traversierung zu schreiben. Dies kann nett sein, da es nur eine Musterübereinstimmung und einen rekursiven Aufruf pro Konstruktor der Listenelemente erfordert, jedoch auf Kosten der Begründung der Bewertungsreihenfolge.