Haskell List Komplexität

Question

Entschuldigung, wenn diese Frage bereits gestellt wurde, habe ich es nicht gefunden. Und Entschuldigung für mein schlechtes Englisch.

Ich lerne Haskell und versuche, Listen zu verwenden. Ich habe eine Funktion geschrieben, die eine Liste nach einem bestimmten Muster transformiert, ich kann nicht überprüfen, ob es jetzt funktioniert, aber ich denke schon.

Diese Funktion ist kein Schwanz Anruffunktion, so denke ich, es schrecklich sein wird, diese Funktion mit einer großen Liste zu berechnen:

transform :: [Int] -> [Int] 
transform list = case list of 
    (1:0:1:[]) -> [1,1,1,1] 
    (1:1:[]) -> [1,0,1] 
    [1]   -> [1,1] 
    (1:0:1:0:s) -> 1:1:1:1: (transform s) 
    (1:1:0:s) -> 1:0:1: (transform s) 
    (1:0:s)  -> 1:1: (transform s) 
    (0:s)  -> 0: (transform s) 

Also habe ich über eine andere Funktion gedacht, das wäre „besser“:

transform = reverse . aux [] 
    where 
    aux buff (1:0:[1]) = (1:1:1:1:buff) 
    aux buff (1:[1])  = (1:0:1:buff) 
    aux buff [1]   = (1:1:buff) 
    aux buff (1:0:1:0:s) = aux (1:1:1:1:buff) s 
    aux buff (1:1:0:s) = aux (1:0:1:buff) s 
    aux buff (1:0:s)  = aux (1:1:buff) s 
    aux buff (0:s)  = aux (0:buff) s 

Das Problem ist, dass ich nicht weiß, wie es kompiliert und wenn ich falsch mit der zweiten Funktion bin. Kannst du mir erklären, wie Listen funktionieren? Ist es besser, am Ende die Liste zu verwenden (++) oder die Liste umzukehren?

Vielen Dank im Voraus für Ihre Antworten

Answer 1

Die erste Funktion ist völlig in Ordnung und meiner Meinung nach besser, den zweiten.

Der Grund ist Faulheit. Wenn Sie in Ihrem Code einen Ausdruck transform someList haben, wird die resultierende Liste nicht ausgewertet, es sei denn, Sie fordern es. Insbesondere wird die Liste nur so weit ausgewertet, wie es benötigt wird; print $ take 10 $ transform xs wird weniger Arbeit als print $ take 20 $ transform xs tun.

In einer strengen Sprache transform würde in der Tat den Stack belasten, da es die gesamte Liste (in einer nicht-tail-rekursiven Weise) vor der Rückgabe etwas von Nutzen zu bewerten hätte. In Haskell transform (0:xs) ergibt 0 : transform xs ein brauchbares Teilergebnis. Wir können den Kopf dieses Ergebnisses untersuchen, ohne den Schwanz zu berühren. Es besteht auch keine Gefahr eines Stack-Überlaufs: Zu jeder Zeit gibt es höchstens einen unbewerteten Thunk (wie im vorherigen Beispiel transform xs) im Ende der Liste. Wenn Sie mehr Elemente anfordern, wird der Thunk einfach weiter zurück geschoben, und der Stack-Frame des vorherigen Thunks kann als Müll gesammelt werden.

Wenn wir die Liste immer vollständig auswerten, dann sollte die Leistung der beiden Funktionen ähnlich sein, oder selbst dann könnte die Lazy-Version etwas schneller sein, weil es keine Umkehrung oder die zusätzlichen ++ -s gibt. Indem wir zur zweiten Funktion wechseln, verlieren wir Faulheit und gewinnen keine zusätzliche Leistung.

Answer 2

Ihre erste Version sieht mir viel besser . Es ist in Ordnung, dass es nicht tail-rekursiv ist: Sie wollen nicht, dass es tail-rekursiv ist, Sie wollen, dass es faul ist. Die zweite Version kann nicht einmal ein einzelnes Element erzeugen, ohne die gesamte Eingabeliste zu bearbeiten, denn um reverse das Ergebnis aux zu erhalten, muss die Gesamtheit der aux bekannt sein. Allerdings

take 10 . transform $ cycle [1,0,0,1,1,1] 

würde mit Ihrer ersten Definition von transform gut funktionieren, weil man nur so viel von der Liste verbrauchen, wie Sie benötigen, um eine Entscheidung zu treffen.

Beachten Sie jedoch, dass (1:0:1:[]) nur [1,0,1] ist.