dequeue Funktion aus einer Liste in Haskell

Question

So habe ich den folgenden Code:

module Queue where 

class Queue t 
    where 
    enqueue :: t a -> a -> t a 
    dequeue :: t a -> Maybe (t a, a)  

--und:

module DataQueue where 

import Queue 
data DQueue a = Empty | Enqueue a (DQueue a) 
    deriving (Eq, Show, Read) 

instance Queue DQueue 
    where 
    enqueue (Empty) s = Enqueue s (Empty) 
    enqueue (Enqueue v ss) s = Enqueue s (Enqueue v ss) 

    dequeue Empty = Nothing 
    dequeue (Enqueue a (ss)) = Just(ss) 

ich ein Element einer Liste (Enqueue) hinzufügen, der gut arbeitet. Außerdem entferne ich ein Element der Liste mit der Auszugsfunktion. Irgendwie bekomme ich einen Fehler für die letzte Zeile meiner Auszugsfunktion. Es sagt:

"Couldn't match expected type (DQueue a, a) with actual type DQueue a "

Ich verstehe wirklich nicht, wie man dieses Problem löst.

Answer 1

Blick auf die Art Signatur für dequeue:

dequeue :: t a -> Maybe (t a, a) 

... und vergleichen Sie es zu dem, was Sie zurückkommen tatsächlich in dieser Zeile:

dequeue (Enqueue a (ss)) = Just(ss) 

Die Typen stimmen nicht überein. Kannst du es jetzt reparieren?

---

Lösungsweg

Die Art der dequeuet a -> Maybe (t a, a) ist, das heißt, es ein Argument des Typs nimmt t a und sollte einen Wert vom Typ Maybe (t a, a) zurückzukehren.

Brechen wir diesen Typ ab, beginnen wir mit dem äußersten "Ding": Maybe (das "Ding" ist als Typkonstruktor bekannt). Was auch immer wir zurückgeben, muss entweder Nothing oder Just <some value> sein. Was in die Just geht ist, was ist "innerhalb der Maybe", in diesem Fall ein Wert des Typs (t a, a), die ein Tupel (Paar) von t a und a ist.

Überprüfen Sie nun, was Ihr Code sagte:

dequeue (Enqueue a (ss)) = Just(ss) 

Der Rückgabewert Just(ss) kann als Just ss geschrieben werden. Lassen Sie uns den Typ des ss bestimmen. Da wir definieren:

data DQueue a = Empty | Enqueue a (DQueue a) 
            ^^^^^^^^^^ <-- ss is of this type 

Die Art der ss ist daher DQueue a. So ist der Typ von Just ss: Maybe (DQueue a).

Nun müssen wir Maybe (t a, a) zurückgeben. In unserem Beispiel der Queue Klasse ist die tDQueue so der Typ mehr zurück ist speziell: Maybe (DQueue a, a), aber wir haben derzeit Maybe (DQueue a) (erinnern ss ist ein DQueue a, so Just ss ist Maybe (DQueue a)).

Um das zu beheben, sollten wir statt Just (some pair) zurückgeben. Das Paar hängt davon ab, wie wir uns verhalten wollen. Wenn es wie ein Stapel ist, der das letzte eingereihte Ergebnis anzeigt, kann es Just (ss, a) sein. Andernfalls sehen Sie sich die andere Antwort an, in der erläutert wird, wie sie implementiert wird.

Answer 2

Basierend auf Ihrer Klasse Queue muss Ihre dequeue-Funktion die Warteschlange zurückgeben, nachdem das Element entfernt wurde. Es soll wohl als

dequeue Empty = Nothing 
dequeue (Enqueue a Empty) = Just (Empty, a) 
dequeue (Enqueue a (ss)) = do 
    (next, v) <- dequeue ss 
    return (Enqueue a next, v) 

Diese Definition definiert werden, vorausgesetzt, dass Sie die Dinge am Anfang der Liste und Ausreihen sie vom Ende Schlange stehen.

Das dritte dequeue Spiel rekursiv dequeue ruft zum Ende der Liste zu gehen, wo sie den Listenwert nehmen (siehe das zweite dequeue Spiel), dann baut es wieder die Enqueue Liste mit all aber dem letzten Elemente .

Das obige Beispiel nutzt die Maybe Monade und do Syntax. Man könnte es als Folgenden ausgedrückt werden, wenn das mehr Sinn macht:

dequeue (Enqueue a ss) = 
    case dequeue ss of 
    Just (next, v) -> Just (Enqueue a next, v) 
    Nothing -> Nothing