sagen, dass ich überprüfen möchten, ob eine Liste in einer Wache in Haskell gibt es zwei Möglichkeiten leer ist:Auf leere Liste in Haskell prüfen: Ist (Längenliste == 0) oder (Liste == []) effizienter?
length list == 0list == []Welche dieser beiden logischen Tests sind effizienter? Ich bin geneigt, den Test der leeren Liste zu sagen, weil er sich auf eher einfache Konstrukte verlässt als auf die Prelude-Funktion length, aber ich bin mir nicht sicher.
length list == 0 muss die gesamte Liste durchlaufen, um ihre Länge zu erhalten, was bedeutet, dass es O (n) ist. list == [] ergibt eine Eq Einschränkung für den Elementtyp. null list läuft in konstanter Zeit und hat keine Klassenbeschränkungen.
Allerdings gibt es einen netten Trick etwas wie length list == 0 zu tun, was den Vorteil hat, dass es ohne den Umweg über die längere Liste schön zu length list1 == length list2 verallgemeinert: Sie genericLength mit einer ausreichend faulen Darstellung der natürlichen Zahlen verwenden können, so dass ein Vergleich wird nur zwingen, die kürzere der Listen zu durchlaufen.
Ein Beispiel dafür ist the Natural type zu verwenden:
import Data.Number.Natural
import Data.List (genericLength)
nats :: [Int]
nats = iterate succ 0
areThereTenNats :: Bool
areThereTenNats = genericLength nats >= (10 :: Natural)
Jede "ausreichend faule Darstellung natürlicher Zahlen" wird zwischen ineffizient und lächerlich ineffizient variieren. Außerdem muss jede alternative Lösung für das Problem des OP mindestens genau das tun, was "null" tut. –
@DerekElkins, die traditionelle Implementierung der Addition durch Mustererkennung auf das erste Argument und "parametrisch" in der zweiten wird gut funktionieren. Dennoch müssen Sie den 'genericLength'-Quellcode und den' + 'Implementierungsquellcode lesen, um dies zu überprüfen. Es ist viel offenkundig korrekter, nur Parameter zu verwenden, um 'forall a 'zu betrachten. [a] 'als eine natürliche Zahl. – dfeuer
@dfeuer Ich denke, ich hätte klarer sein müssen, dass für den Fall "== 0", obwohl es nicht schneller als "null" ist, es nicht übermäßig ineffizient sein wird. Für jeden anderen Fall ist es ein Rezept, um Müll und verschwenderische Berechnungen für etwas zu erzeugen, das zwei Zeiger parallel durchlaufen sollte, die keine Zuteilung erfordern. Es hat jedoch dieselbe asymptotische Effizienz wie der Zeiger, der jedoch läuft. Ich wollte nur darauf hinweisen, dass, wenn Sie sich Sorgen um Effizienz machen, der Wechsel zu einem "faulen natürlichen" Typ das genaue Gegenteil dessen ist, was Sie tun sollten. (Ich sage nicht, dass Cactus sagte, dass es war.) –
Wie andere, auf die beste Art und Weise angegeben haben, zu überprüfen, ob eine Liste leer ist (und nicht mehr) ist
null :: Foldable f => f a -> Bool
der verwenden Bei Typ
null :: [a] -> Bool
verwendet werden Wenn Sie überprüfen möchten, ob eine Liste leer ist, weil Sie wan t an seinen Elementen suchen sonst, Sie sollten in der Regel Muster werden unter Verwendung passender statt:
f [] = something
f (x : xs) = something using x and/or xs
Wenn Sie die Längen von zwei Listen (und nicht mehr) vergleichen wollen, ist der beste Weg ist in der Regel so etwas wie
compareLength :: [a] -> [b] -> Ordering
compareLength [] [] = EQ
compareLength [] (_ : _) = LT
compareLength (_ : _) [] = GT
compareLength (_ : xs) (_ : ys) =
compareLength xs ys
der beste Weg, um zu überprüfen, wie die Länge einer Liste auf eine bestimmte Anzahl vergleicht ist
compareToLength :: Foldable f
=> f a -> Int -> Ordering
compareToLength = foldr go (compare 0) where
go _ r n | n <= 0 = GT
| otherwise = r $! n - 1
'' compareLength = compare 'on' (() <$)' 'ist eine andere Option zum Vergleichen der Länge, wenn Sie etwas prägnanteres wollen. – semicolon
@semicolon, guter Punkt. Du könntest das sogar beantworten. 'compare (replicate n()) (() <$ xs)' ist möglicherweise auch auf diese Weise nützlich. Keines von ihnen wird so effizient sein, wie es mit der Hand gemacht wird, aber sie werden auch nicht schrecklich sein. – dfeuer
@WillNess, war das in GHCi? Ich spreche nur über optimierten Code. – dfeuer
Sie überprüfen können, ob Ihre Liste in konstanter Zeit mitleer ist, die einen booleschen Wert zurückgibt.
Prelude> null []
True
Prelude> null [1]
False
Prelude> null ""
True
Prelude> null "Test"
False
Ja, aber was fügt diese Antwort zu [dfeuer's] hinzu (https://stackoverflow.com/a/36481943/745903)? – leftaroundabout
1 ist linear in der Länge der Liste (offensichtlich), während 2 konstante Zeit ist. Aber 2 hat den Nachteil, eine'Eq'-Einschränkung zu verlangen, wenn Sie sie nicht wirklich brauchen. Suchen Sie nach einer leeren Liste mit 'null' oder einfach nach Mustererkennung. – user2407038
das Problem ist Mustererkennung funktioniert nicht, wenn Sie die Gleichheit mit anderen vordefinierten Listen vergleichen wollen –
Auch danke und das macht eine Menge Sinn. Könnten Sie mehr über null herausfinden? –