Entfernen Sie Elemente in der Liste mit einer Liste von Int (Haskell)

Question

Ich schreibe Funktion, die eine Liste von Int, eine Liste des allgemeinen Typs a nehmen und entfernen Sie alle Elemente, die Index in der Liste von Int.

Zum Beispiel: removeEl [1,3,4] [1,2,3,4,5,6] Rückkehr [1,3,6] oder removeEl [1,2] "Firefox" Rückkehr "Fefox"

Hier ist mein Versuch:

removeEl :: [Int] -> [a] -> [a] 
removeEl [] xs = [] 
removeEl ns [] = [] 
removeEl (n:ns) (x:xs) | n == 0 = removeEl ns xs 
         | n > 0 = x:removeEl (n-1) xs 

Ich weiß, (n-1) ist ein Int, nicht [Int] so ist es nicht. Muss ich eine Hilfsfunktion schreiben, um zu verwenden?

Answer 1

Sie müssen eine neue Liste übergeben, aber jedes Element in dieser Liste muss dekrementiert werden, da Sie die Positionen jedes Elements des zweiten Arguments verschoben haben. Dies gilt unabhängig davon, ob Sie das Kopfelement tatsächlich entfernt haben oder nicht.

removeEl (n:ns) (x:xs) | n == 0 = removeEl (map pred ns) xs 
         | n > 0 = x:removeEl (map pred (n:ns)) xs 

Es gibt eine Menge Möglichkeiten, dies zu Refactoring, aber nichts, was ich mit fühlt sich wesentlich einfacher gespielt habe.

Auch Ihre erste Basisfall ist falsch:

remove [] xs = xs 

(Beachten Sie dies nur, wenn das funktioniert: keine Elemente in der Indexliste, Sie alles, nicht nichts zurückkehren wollen erstes Argument ist monoton steigend)

---

Sie können auch die explizite Rekursion mit einer Liste Verständnis vermeiden.

removeEl ns xs = [x | (n,x) <- zip [0..] xs, not(n `elem` ns)] 

Answer 2

Ich glaube, Ihr Algorithmus ist O(n*m), wo n die Anzahl der Elemente in der Liste enthalten ist und m ist die Anzahl der Indizes zu entfernen. Es hat auch die unglückliche Anforderung, dass die Liste der Indizes bestellt werden muss. Hier ist eine ~O(n*log(m)) Lösung, die nicht erfordert, dass die Indizes geordnet werden.

Und das könnte ein bisschen verbessert werden, indem Sie eine Hash-Karte verwenden.