Haskell - Cua (1) P80618

Statement

thehtml

Volem representar cues de forma que millorem l’eficiència conjunta de les operacions d’afegir i d’avançar. Per això, implementem la cua amb dues llistes tals que si concatenem la primera amb la revessada de la segona tenim els elements de la cua en l’ordre de sortida. Usant com a constructor Queue, un exemple de cua seria

cua = Queue [2,8,5] [4,7]

que representa la cua on el primer és el 2 i segueix amb 8, 5, 7 i 4.

D’aquesta manera, l’operació d’afegir en una cua es fa posant el nou element per davant de la segona llista (que és menys costós que afegir-lo al final d’una llista).

D’altra banda, l’operació d’avançar es fa treient el primer de la primera llista, si en té, i sinó, passant els de la segona llista cap a la primera (en l’ordre correcte) i agafant el primer tot deixant la resta.

Implementeu cues genèriques utilitzant la definició de dades i les operacions següents:
data Queue a = Queue [a] [a] deriving (Show) create :: Queue a push :: a -> Queue a -> Queue a pop :: Queue a -> Queue a top :: Queue a -> a empty :: Queue a -> Bool
Definiu la igualtat de cues de manera que dues cues siguin iguals si i només si tenen els mateixos elements en el mateix ordre de sortida. Per a fer- ho, indiqueu que les cues són una instàcia de la classe Eq on (==) és l’operació d’igualtat que heu de definir:
instance Eq a => Eq (Queue a) where ...
Fixeu-vos que cal que el tipus dels elements de la cua també siguin de la classe Eq.

Puntuació

Cada apartat puntua 50 punts.

Public test cases

Input

let c = push 3 (push 2 (push 1 create))
c
top c
pop c
empty $ pop c
empty $ pop $ pop $ c
empty $ pop $ pop $ pop c

Output

Queue [] [3,2,1]
1
Queue [2,3] []
False
False
True

Input

let c1 = push 4 (pop (push 3 (push 2 (push 1 create))))
let c2 = push 4 (push 3 (push 2 create))
c1
c2
c1 == c2

Output

Queue [2,3] [4]
Queue [] [4,3,2]
True

Information

Author: Jordi Petit
Language: Catalan
Other languages: English
Official solutions: Haskell
User solutions: Haskell