Typ klasy Haskella dla kolejki

Question

Czy ktoś napisał klasę typu Haskell (lub istnieje kombinacja klas typów) opisującą kolejkę FIFO.

Data.Collection.Sequence wydaje się zbyt silny, ale z drugiej strony Data.Collection.Unfoldable wydaje się zbyt słaby (ponieważ kolejność nie jest zdefiniowana).

Chciałem tylko nie przerobić czyjejś pracy.

Answer 1

To naprawdę nie jest zbyt trudne (i ciekawe ćwiczenie), aby przetasować własną kolejkę FIFO w Haskell. Mogę docenić twoją chęć użycia standardowej czcionki do tego i prawie na pewno powinieneś to zrobić. Ale właśnie dowiedziałem się o tym w zeszłym tygodniu i jestem zbyt podekscytowany, aby o tym nie pisać.

Oto prosta klasa kolejki, która pozwala sprawdzić, czy kolejka jest pusta, aby pobrać pierwszy element z nagłówka kolejki (i zwrócić resztę kolejki) oraz wstawić nowy element do kolejki .

class Queue q where 
    empty :: q a -> Bool 
    get :: q a -> (a, q a) 
    ins :: a -> q a -> q a 

Najprostszym sposobem na kolejkę FIFO jest na podstawie listy:

instance Queue [] where 
    empty = null 

    get []  = error "Can't retrieve elements from an empty list" 
    get (x:xs) = (x, xs) 

    ins x xs = xs ++ [x] 

Jest to jednak strasznie niewydajne. Jeśli kolejka ma obecnie elementy n, wstawienie nowego elementu zajmuje czas O (n). Jeśli chcesz wstawić elementy m do pustej kolejki, która zajmie czas O (m). Czy możemy utworzyć kolejkę, która wstawia i pobiera elementy w czasie O (1) (lub co najmniej O (1) czas amortyzacji)?

Trick jest przechowywanie w przód i z powrotem w kolejce w oddzielnych wykazów z tyłu kolejki przechowywane w odwrotnej kolejności:

data Fifo a = F [a] [a] 

instance Queue Fifo where 

kolejka jest pusty, gdy zarówno z przodu i z tyłu są puste:

empty (F xs ys) = null xs && null ys 

Aby włożyć nowy element do wykazu, po prostu cons go na kolejki tyłu, co odbywa o (1) razem.

ins y (F xs ys) = F xs (y:ys) 

Uzyskiwanie elementu z przodu kolejki jest łatwe, gdy istnieją elementy czekają tam (i rzucamy błąd, jeśli kolejka jest pusta)

get (F []  []) = error "Can't retrieve elements from an empty queue" 
    get (F (x:xs) ys) = (x, F xs ys) 

Wreszcie, jeśli nie istnieją żadne elementy czekając z przodu kolejki, a następnie odwracamy tył kolejki i umieszczamy ją z przodu. Chociaż ta zajmuje O (n) czas, musimy tylko zrobić to raz dla każdego elementu, więc nasz get eksploatacji średnie spośród O (1) Czas:

get (F [] ys) = get (F (reverse ys) []) 

Nie masz go - amortyzowane O (1) Kolejki FIFO w języku funkcjonalnym.

---

Edit: EFIE zapytany o zamortyzowanego O (1) wydajność w komentarzach. Argument dotyczący amortyzacji stałego czasu jest dość prosty.

Rozważmy sekwencję n insercji do pustego w kolejce, a następnie n pobraniami. Wstawienia wymagają czasu: n . Przy pierwszym pobieraniu przód kolejki jest pusty, więc musimy odwrócić tył kolejki, co również zajmuje czas n, plus 1, aby pobrać element. Na koniec, kolejne n - 1 wyszukiwań czasu, 1 każde, więc całkowity czas jest

n + n + 1 + n - 1 = 3 n

Dokonaliśmy 2 n połączeń, więc amortyzowany czas wynosi 3 /2n = 3/2, czyli O (1). Ten sam argument działa niezależnie od tego, jak połączenia są przeplatane - w dwóch połączeniach każdy element jest jednokrotny, raz przeno- szony i jednorazowo odrzucony.

Answer 2

Zależy od operacji, które chcesz wykonać. Pakiety queuelike i dequeue mają klasy typów dla kolejek.