priority-queue

A priority queue for Elm.

A priority queue is an

abstract data type which is like a regular queue or stack data structure, but where additionally each element has a "priority" associated with it. In a priority queue, an element with high priority is served before an element with low priority.

The implementation we provide here is based on Okasaki's leftist heaps. See Purely Functional Data Structures for more information.

Installation

Install HAN-ASD-DT/priority-queue with the following command

elm install HAN-ASD-DT/priority-queue

Usage

The documentation for the priority-queue package can be found online. Below you can read a how a PriorityQueue can be used.

Let's say that for a artistic painting application you are maintaining a queue of rectangles to paint. The rectangles come in over a port and you want to paint larger, i.e. rectangles with a larger area, first. A priority queue helps in this scenario.

To create a queue you could use the PriorityQueue.empty function. It accepts a Priority, i.e. a function that assigns priority to elements. Note that lower values corresponds to higher priority. Think of the priority as the time you would be willing to wait before you would like to process the element.

We assume that there is a type alias Rectangle and a corresponding area function that returns the (integer) area of a rectangle.

queue: PriorityQueue Rectangle
queue =
    let
        priority =
            area >> negate
    in
    empty priority

Here area is composed with negate to ensure that larger areas have a higher priority.

Inserting a rectangle into a queue is done with the insert function. Given a rectangle and a queue the following code creates a new queue which contains the provided rectangle.

nextQueue = insert rectangle queue

Notice that it is not necessary to repeat the Priority. The queue already knows how to tell the priority for a rectangle.

When it is time to draw a rectangle head could provide you with one.

case head queue of
    Nothing ->
        Cmd.none
    
    Just rectangle ->
        draw rectangle 

The tail function returns a priority queue of the remaining elements.