Lớp loại Haskell cho Hàng đợi

Question

Có ai đã viết một loại lớp Haskell (hoặc có sự kết hợp của các loại lớp) mô tả hàng đợi FIFO.

Data.Collection.Sequence có vẻ quá mạnh, nhưng mặt khác Data.Collection.Unfoldable có vẻ quá yếu (do đơn hàng không được xác định).

Tôi chỉ muốn không làm lại tác phẩm của người khác.

Answer 1

Nó thực sự không quá khó (và một bài tập thú vị) để cuộn hàng đợi FIFO của riêng bạn trong Haskell. Tôi có thể đánh giá cao mong muốn của bạn để sử dụng một typeclass tiêu chuẩn cho việc này, và đó là gần như chắc chắn những gì bạn nên làm. Nhưng tôi mới biết về điều này tuần trước, và tôi quá vui mừng không viết về nó. Đây là một lớp xếp hàng đơn giản, cho phép bạn kiểm tra xem hàng đợi có trống hay không, để lấy phần tử đầu tiên từ phần đầu của hàng đợi (và trả về phần còn lại của hàng đợi) và chèn một phần tử mới vào hàng đợi .

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

Cách đơn giản nhất để làm cho một hàng đợi FIFO đang sử dụng một danh sách:

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] 

Tuy nhiên, đây là khủng khiếp không hiệu quả. Nếu hàng đợi hiện có các yếu tố n, thì việc chèn phần tử mới sẽ mất thời gian O (n). Nếu bạn muốn chèn các phần tử m vào hàng đợi trống, sẽ mất thời gian O (m). Chúng ta có thể tạo một hàng đợi chèn và lấy các phần tử trong thời gian O (1) (hay ít nhất là thời gian phân bổ O (1))?

Bí quyết là để lưu trữ các mặt trước và sau của hàng đợi trong danh sách riêng biệt, với sự trở lại của hàng đợi được lưu trữ trong ngược lại:

data Fifo a = F [a] [a] 

instance Queue Fifo where 

Hàng đợi rỗng nếu cả hai phía trước và phía sau là sản phẩm nào:

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

Để chèn phần tử mới vào danh sách, chúng tôi chỉ đưa nó vào hàng đợi sau, mất khoảng thời gian O (1).

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

Bắt một yếu tố từ phía trước của hàng đợi là dễ dàng khi có những yếu tố chờ đợi ở đó (và chúng ta ném ra một lỗi nếu hàng đợi rỗng)

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

Cuối cùng, nếu không có yếu tố chờ đợi ở phía trước của hàng đợi, sau đó chúng tôi đảo ngược mặt sau của hàng đợi và đặt nó ở phía trước. Mặc dù điều này mất O (n) thời gian, chúng tôi chỉ phải làm điều đó một lần cho mỗi yếu tố, vì vậy get của chúng tôi hoạt động trung bình ra O (1) thời gian:

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

Ở đó bạn có nó - khấu hao O (1) Hàng đợi FIFO trong một ngôn ngữ chức năng.

---

Edit: Efie hỏi về O khấu hao (1) thực hiện trong các ý kiến. Đối số cho thời gian cố định được phân bổ là khá đơn giản.

Xem xét chuỗi các yêu cầu n chèn vào hàng đợi trống, theo sau là n truy xuất. Số lần chèn mất thời gian n. Trong lần truy xuất đầu tiên, mặt trước của hàng đợi trống, vì vậy chúng tôi phải đảo ngược mặt sau của hàng đợi, cũng mất thời gian n, cộng với 1 để truy lục phần tử. cuối cùng, n tiếp theo - 1 khả năng tìm lại mất thời gian 1 mỗi, vì vậy tổng thời gian là

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

Chúng tôi đã làm Tổng cộng 2 n cuộc gọi, do đó, thời gian khấu hao là 3 n/2 n = 3/2, là O (1). Các đối số tương tự hoạt động không có vấn đề làm thế nào các cuộc gọi đến ins và get được xen kẽ - trong hai cuộc gọi, mỗi yếu tố được cons'ed một lần, di chuyển một lần và de-cons'ed một lần.

Answer 2

Phụ thuộc vào những hoạt động bạn muốn có. Các gói queuelike và dequeue có các lớp loại cho hàng đợi.