큐를위한 하스켈 타입 클래스

Question

FIFO 큐를 설명하는 하스켈 타입 클래스 (또는 타입 클래스의 조합이있다)를 작성한 사람이 있는가?

Data.Collection.Sequence은 너무 강하지 만 다른 한편으로는 Data.Collection.Unfoldable이 약해 보입니다 (순서가 정의되지 않았 음).

나는 다른 사람의 작업을 다시하고 싶지 않습니다.

Answer 1

하스켈에서 FIFO 대기열을 롤업하는 것은 실제로 어렵지 않습니다. 나는 당신이 이것을 위해 표준 typeclass를 사용하고 싶어하는 것에 대해 감사 할 수있다. 그리고 그것은 당신이해야하는 거의 확실한 것이다. 그러나 저는 지난 주에 대해 배웠습니다. 나는 그것에 대해 쓰지 않기에 너무나 기쁩니다.

다음은 간단한 대기열 클래스입니다.이 클래스를 사용하면 대기열이 비어 있는지 확인할 수 있습니다. 대기열의 첫 번째 요소를 가져 와서 나머지 대기열을 반환하고 새 요소를 대기열에 삽입 할 수 있습니다 .

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

는 FIFO 큐를 확인하는 가장 간단한 방법

이 목록을 사용하고 있습니다 :

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] 

그러나,이 끔찍하게 비효율적이다. 큐에 현재 n 요소가있는 경우 새 요소를 삽입하려면 O (n) 시간이 걸립니다. 빈 큐에 m 요소를 삽입하려면 O (m) 시간이 필요합니다. O (1) 시간 (또는 최소, O (1) 상각 시간)에 요소를 삽입하고 검색하는 대기열을 만들 수 있습니까?

data Fifo a = F [a] [a] 

instance Queue Fifo where 

큐 앞뒤 양쪽 경우 비어 :

트릭 역방향에 저장되는 큐의 후면과 전면 분리 목록에 큐 다시 저장하는 것이다 비어 있음 :

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

새 요소를 목록에 삽입하려면 O (1) 시간이 소요되는 대기열에 넣으십시오. 거기에 대기 요소 (이 큐가 비어있는 경우 우리가 오류가 발생)에 요소가없는 경우,

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

마지막 때 큐의 앞쪽에서 요소를 얻기

는

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

쉽게 대기열의 앞에서 기다린 다음 대기열의 뒤를 뒤집어서 앞에 놓습니다. (O 상각 -

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

이

당신이 한 :이 O를 취했지만 (N) 시간, 우리는 그래서 우리의 GET 작업의 평균 (1) 시간 O 밖으로, 각 요소에 대해 한 번해야 1) 기능적 언어로 FIFO 대기열.

---

편집 :는 Efie는 코멘트에 상각 O (1)의 성능에 대해 물었다. 상각 된 상수 시간에 대한 논의는 매우 간단합니다.

n 빈 큐에 대한 삽입 다음에 n 검색이 이어지는 것으로 간주하십시오. 삽입은 시간이 n 걸립니다. 첫 번째 검색에서 대기열의 앞면이 비어 있으므로 대기열의 뒤를 되돌려 야합니다. 또한 n에 1을 더하여 요소를 검색합니다. 우리가 만든 1 = 3 N

- 마지막으로, 다음 N - 총 시간은

N + N + 1 + N 그래서 1 취득에서는이 시간이 1 각을 2 n 총 호출이므로 상환 시간은 3 (n/2 n = 3/2)이며 O (1)입니다. ins과 get에 대한 호출이 어떻게 인터리브되었는지에 상관없이 동일한 인수가 작동합니다. 두 번의 호출에서 각 요소는 한 번에 한 번에 한 번만 이동되고 한 번만 이동하고 한 번만 수행 할 수 있습니다.

Answer 2

원하는 작업에 따라 다릅니다. queuelike 및 dequeue 패키지에는 대기열에 대한 유형 클래스가 있습니다.