Queue.dcl 714 Bytes
Newer Older
1
definition module Data.Queue
Camil Staps's avatar
Camil Staps committed
2

3
/**
Camil Staps's avatar
Camil Staps committed
4 5 6 7
 * This module provides a straightforward FIFO queue.
 * It is implemented using two list based on Chris Okasaki's example in Purely
 * Functional Data Structures.
 */
8 9 10 11 12 13 14

from Data.Maybe import :: Maybe
from StdOverloaded import class length

:: Queue a = Queue [a] [a]

/**
Camil Staps's avatar
Camil Staps committed
15 16
 * Create an empty queue
 */
17 18 19
newQueue :: Queue a

/**
Camil Staps's avatar
Camil Staps committed
20 21 22
 * Test if the queue is empty
 * @type (Queue a) -> Bool
 */
23 24 25 26 27 28 29
empty q :== case q of 
        Queue [] [] -> True
        _           -> False

instance length Queue

/**
Camil Staps's avatar
Camil Staps committed
30 31
 * Add an element to the queue
 */
32 33 34
enqueue :: a (Queue a) -> Queue a

/**
Camil Staps's avatar
Camil Staps committed
35 36
 * Take an element from the queue (if the queue is not empty)
 */
37
dequeue :: (Queue a) -> (!Maybe a,!Queue a)