On this page:
2.1 Bankers Deque
Deque
deque
empty
empty?
enqueue
enqueue-front
head
last
tail
init
deque->list
map
foldl
foldr
filter
remove
andmap
ormap
build-deque
head+  tail
last+  init
2.2 Implicit Deque
Deque
deque
empty
empty?
enqueue
enqueue-front
head
last
tail
init
deque->list
map
foldl
foldr
filter
remove
andmap
ormap
build-deque
head+  tail
last+  init
2.3 Real-Time Deque
Deque
deque
empty
empty?
enqueue
enqueue-front
head
last
tail
init
deque->list
map
foldl
foldr
filter
remove
andmap
ormap
build-deque
head+  tail
last+  init
8.17

2 Deques🔗ℹ

Double ended queues (or deque) are queues where elements can be added or removed from either end. The deque data structures provided by this library implement and provide the following operations: deque, empty?, enqueue, enqueue-front, head, tail, last, init and deque->list.

    2.1 Bankers Deque

    2.2 Implicit Deque

    2.3 Real-Time Deque

2.1 Bankers Deque🔗ℹ

 (require pfds/deque/bankers) package: pfds

Bankers deques are amortized double ended deques developed using the Bankers method. They provide an amortized running time of O(1) for the operations head, tail, last, init, enqueue-front and enqueue. They use lazy evaluation and memoization to achieve the amortized running time.

syntax

(Deque A)

A banker’s deque of type A.

procedure

(deque a ...)  (Deque A)

  a : A
Function deque creates a Bankers Deque with the given inputs.

Example:
> (deque 1 2 3 4 5 6)

- : #(struct:Deque

      ((Rec

        g305889

        (U (Pairof Positive-Byte g305889) (Promiseof g305889) Null))

       Integer

       (Rec

        g305891

        (U (Pairof Positive-Byte g305891) (Promiseof g305891) Null))

       Integer))

#<Deque>

In the above example, the deque obtained will have 1 as its head element.

procedure

(empty t)  (Deque A)

  t : A
An empty deque of type t.

Examples:
> (empty Nothing)

- : (Deque Nothing)

#<Deque>

> (empty Integer)

- : (Deque Integer)

#<Deque>

procedure

(empty? dq)  Boolean

  dq : (Deque A)
Function empty? checks if the given deque is empty.

Examples:
> (empty? (empty Natural))

- : Boolean

#t

> (empty? (deque 1 2))

- : Boolean

#f

procedure

(enqueue a deq)  (Deque A)

  a : A
  deq : (Deque A)
Function enqueue takes an element and a deque and enqueues the given element in the deque.

Example:
> (enqueue 10 (deque 3 2 4))

- : #(struct:Deque

      ((Rec

        g305961

        (U (Pairof Positive-Byte g305961) (Promiseof g305961) Null))

       Integer

       (Rec

        g305963

        (U (Pairof Positive-Byte g305963) (Promiseof g305963) Null))

       Integer))

#<Deque>

In the above example, (enqueue 10 deq) adds the element 10 to (deque 3 2 4). 10 will be the last element in the deque.

procedure

(enqueue-front a deq)  (Deque A)

  a : A
  deq : (Deque A)
Function enqueue-front takes an element and a deque and puts the given element to the front of the given deque.

Example:
> (enqueue-front 10 (deque 5 6 3 4))

- : #(struct:Deque

      ((Rec

        g305982

        (U (Pairof Positive-Byte g305982) (Promiseof g305982) Null))

       Integer

       (Rec

        g305984

        (U (Pairof Positive-Byte g305984) (Promiseof g305984) Null))

       Integer))

#<Deque>

In the above example, (enqueue-front 10 (deque 5 6 3 4)) adds 10 to the front of the (deque 5 6 3 4). 10 will be the head element.

procedure

(head deq)  A

  deq : (Deque A)
Function head takes a deque and gives the first element in the deque if deque is not empty else throws an error.

Examples:
> (head (deque 5 2 3))

- : Integer [more precisely: Positive-Byte]

5

> (head (empty Integer))

head: given deque is empty

In the above example, (head (empty Integer)) throws an error since the given deque is empty.

procedure

(last deq)  A

  deq : (Deque A)
Function last takes a deque and gives the last element in the deque if deque is not empty else throws an error.

Examples:
> (last (deque 1 2 3 4 5 6))

- : Integer [more precisely: Positive-Byte]

6

> (last (empty Integer))

last: given deque is empty

In the above example, (last (empty Integer))throws an error since the given deque is empty.

procedure

(tail deq)  (Deque A)

  deq : (Deque A)
Function tail takes a deque and returns the given deque without the first element if the given deque is non empty else throws an error.

Examples:
> (tail (deque 1 2 3 4 5 6))

- : #(struct:Deque

      ((Rec

        g306076

        (U (Pairof Positive-Byte g306076) (Promiseof g306076) Null))

       Integer

       (Rec

        g306078

        (U (Pairof Positive-Byte g306078) (Promiseof g306078) Null))

       Integer))

#<Deque>

> (tail (empty Integer))

tail: given deque is empty

In the above example, (tail (deque 1 2 3 4 5 6)), removes the head of the given deque returns (deque 2 3 4 5 6).

procedure

(init deq)  (Deque A)

  deq : (Deque A)
Function init takes a deque and returns the given deque without the last element if the given deque is not empty else throws an error.

Examples:
> (init (deque 1 2 3 4 5 6))

- : #(struct:Deque

      ((Rec

        g306119

        (U (Pairof Positive-Byte g306119) (Promiseof g306119) Null))

       Integer

       (Rec

        g306121

        (U (Pairof Positive-Byte g306121) (Promiseof g306121) Null))

       Integer))

#<Deque>

> (init (empty Integer))

init: given deque is empty

In the above example, (init (deque 1 2 3 4 5 6)), removes the last element 6 and returns (deque 1 2 3 4 5).

procedure

(deque->list deq)  (Listof A)

  deq : (Deque A)
Function deque->list takes a deque and returns a list of elements. The list will have head of the given deque as its first element. If the given deque is empty, then it returns an empty list.

Examples:
> (deque->list (deque 10 2 34 4 15 6))

- : (Listof Positive-Byte)

'(10 2 34 4 15 6)

> (deque->list (empty Integer))

- : (Listof Integer)

'()

procedure

(map func deq1 deq2 ...)  (Deque A)

  func : (A B ... B -> C)
  deq1 : (Deque A)
  deq2 : (Deque B)
Function map is similar to map for lists.

Examples:
> (deque->list (map add1 (deque 1 2 3 4 5 6)))

- : (Listof Positive-Index)

'(2 3 4 5 6 7)

> (deque->list (map * (deque 1 2 3 4 5 6) (deque 1 2 3 4 5 6)))

- : (Listof Positive-Index)

'(1 4 9 16 25 36)

procedure

(foldl func init deq1 deq2 ...)  C

  func : (C A B ... B -> C)
  init : C
  deq1 : (Deque A)
  deq2 : (Deque B)
Function foldl is similar to foldl

foldl currently does not produce correct results when the given function is non-commutative.

Examples:
> (foldl + 0 (deque 1 2 3 4 5 6))

- : Integer [more precisely: Nonnegative-Integer]

21

> (foldl * 1 (deque 1 2 3 4 5 6) (deque 1 2 3 4 5 6))

- : Integer [more precisely: Positive-Integer]

518400

procedure

(foldr func init deq1 deq2 ...)  C

  func : (C A B ... B -> C)
  init : C
  deq1 : (Deque A)
  deq2 : (Deque B)
Function foldr is similar to foldr

foldr currently does not produce correct results when the given function is non-commutative.

Examples:
> (foldr + 0 (deque 1 2 3 4 5 6))

- : Integer [more precisely: Nonnegative-Integer]

21

> (foldr * 1 (deque 1 2 3 4 5 6) (deque 1 2 3 4 5 6))

- : Integer [more precisely: Positive-Integer]

518400

procedure

(filter func que)  (Deque A)

  func : (A -> Boolean)
  que : (Deque A)
Function filter is similar to filter.

Examples:
> (define que (deque 1 2 3 4 5 6))
> (deque->list (filter (λ: ([x : Integer]) (> x 5)) que))

- : (Listof Positive-Byte)

'(6)

> (deque->list (filter (λ: ([x : Integer]) (< x 5)) que))

- : (Listof Positive-Byte)

'(1 2 3 4)

> (deque->list (filter (λ: ([x : Integer]) (<= x 5)) que))

- : (Listof Positive-Byte)

'(1 2 3 4 5)

procedure

(remove func que)  (Deque A)

  func : (A -> Boolean)
  que : (Deque A)
Function remove is similar to filter but remove removes the elements which match the predicate.

Examples:
> (deque->list (remove (λ: ([x : Integer]) (> x 5))
                       (deque 1 2 3 4 5 6)))

- : (Listof Positive-Byte)

'(1 2 3 4 5)

> (deque->list (remove (λ: ([x : Integer]) (< x 5))
                       (deque 1 2 3 4 5 6)))

- : (Listof Positive-Byte)

'(5 6)

> (deque->list (remove (λ: ([x : Integer]) (<= x 5))
                       (deque 1 2 3 4 5 6)))

- : (Listof Positive-Byte)

'(6)

procedure

(andmap func deq1 deq2 ...)  Boolean

  func : (A B ... B -> Boolean)
  deq1 : (Deque A)
  deq2 : (Deque B)
Function andmap is similar to andmap.

Examples:
> (andmap even? (deque 1 2 3 4 5 6))

- : Boolean

#f

> (andmap odd? (deque 1 2 3 4 5 6))

- : Boolean

#f

> (andmap positive? (deque 1 2 3 4 5 6))

- : Boolean

#t

> (andmap negative? (deque -1 -2))

- : Boolean

#t

procedure

(ormap func deq1 deq2 ...)  Boolean

  func : (A B ... B -> Boolean)
  deq1 : (Deque A)
  deq2 : (Deque B)
Function ormap is similar to ormap.

Examples:
> (ormap even? (deque 1 2 3 4 5 6))

- : Boolean

#t

> (ormap odd? (deque 1 2 3 4 5 6))

- : Boolean

#t

> (ormap positive? (deque -1 -2 3 4 -5 6))

- : Boolean

#t

> (ormap negative? (deque 1 -2))

- : Boolean

#t

procedure

(build-deque size func)  (Deque A)

  size : Natural
  func : (Natural -> A)
Function build-deque is similar to build-list.

Examples:
> (deque->list (build-deque 5 (λ:([x : Integer]) (add1 x))))

- : (Listof Integer)

'(1 2 3 4 5)

> (deque->list (build-deque 5 (λ:([x : Integer]) (* x x))))

- : (Listof Integer)

'(0 1 4 9 16)

procedure

(head+tail deq)  (Pair A (Deque A))

  deq : (Deque A)
Function head+tail returns a pair containing the head and the tail of the given deque.

Examples:
> (head+tail (deque 1 2 3 4 5))

- : (Pairof

     Positive-Byte

     #(struct:Deque

       ((Rec

         g306793

         (U (Pairof Positive-Byte g306793) (Promiseof g306793) Null))

        Integer

        (Rec

         g306795

         (U (Pairof Positive-Byte g306795) (Promiseof g306795) Null))

        Integer)))

'(1 . #<Deque>)

> (head+tail (build-deque 5 (λ:([x : Integer]) (* x x))))

- : (Pairof

     Integer

     #(struct:Deque

       ((Rec g306819 (U (Pairof Integer g306819) (Promiseof g306819) Null))

        Integer

        (Rec g306821 (U (Pairof Integer g306821) (Promiseof g306821) Null))

        Integer)))

'(0 . #<Deque>)

> (head+tail (empty Integer))

head+tail: given deque is empty

procedure

(last+init deq)  (Pair A (Deque A))

  deq : (Deque A)
Function last+init returns a pair containing the last element and the init of the given deque.

Examples:
> (last+init (deque 1 2 3 4 5))

- : (Pairof

     Positive-Byte

     #(struct:Deque

       ((Rec

         g306862

         (U (Pairof Positive-Byte g306862) (Promiseof g306862) Null))

        Integer

        (Rec

         g306864

         (U (Pairof Positive-Byte g306864) (Promiseof g306864) Null))

        Integer)))

'(5 . #<Deque>)

> (last+init (build-deque 5 (λ:([x : Integer]) (* x x))))

- : (Pairof

     Integer

     #(struct:Deque

       ((Rec g306888 (U (Pairof Integer g306888) (Promiseof g306888) Null))

        Integer

        (Rec g306890 (U (Pairof Integer g306890) (Promiseof g306890) Null))

        Integer)))

'(16 . #<Deque>)

> (last+init (empty Integer))

last+init: given deque is empty

2.2 Implicit Deque🔗ℹ

 (require pfds/deque/implicit) package: pfds

Deques obtained by applying Implicit Recursive Slowdown. Provides amortized running time of O(1) for the operations head, tail, last, init, enqueue-front and enqueue. Implicit Recursive Slowdown combines laziness and technique called Recursive Slow-Down developed by Kaplan and Tarjan in their paper Persistant Lists with Catenation via Recursive Slow-Down.

syntax

(Deque A)

Implicit double ended queue of type A.

procedure

(deque a ...)  (Deque A)

  a : A
Function deque creates a Implicit Deque with the given inputs.

Example:
> (deque 1 2 3 4 5 6)

- : (U (Deep Positive-Byte) (Shallow Positive-Byte))

#<Deep>

In the above example, the deque obtained will have 1 as its head element.

value

empty : (Deque Nothing)

An empty deque

procedure

(empty? dq)  Boolean

  dq : (Deque A)
Function empty? checks if the given deque is empty or not.

Examples:
> (empty? (deque 1 2 3 4 5 6))

- : Boolean

#f

> (empty? empty)

- : Boolean

#t

procedure

(enqueue a deq)  (Deque A)

  a : A
  deq : (Deque A)
Function enqueue takes an element and a deque and enqueues the given element into the deque.

Example:
> (enqueue 10 (deque 1 2 3 4 5 6))

- : (U (Deep Positive-Byte) (Shallow Positive-Byte))

#<Deep>

In the above example, enqueue adds the element 10 to (deque 1 2 3 4 5 6 10).

procedure

(enqueue-front a deq)  (Deque A)

  a : A
  deq : (Deque A)
Function enqueue-front takes an element and a deque and puts the given element to the front of the given deque.

Example:
> (enqueue-front 10 (deque 5 6 3 4))

- : (U (Deep Positive-Byte) (Shallow Positive-Byte))

#<Deep>

In the above example, (enqueue-front 10 (deque 5 6 3 4)) adds 10 to the front of the (deque 5 6 3 4). 10 will be the head element.

procedure

(head deq)  A

  deq : (Deque A)
Function head takes a deque and gives the first element in the deque if deque is not empty else throws an error.

Examples:
> (head (deque 1 2 3 4 5 6))

- : Integer [more precisely: Positive-Byte]

1

> (head empty)

head: given deque is empty

procedure

(last deq)  A

  deq : (Deque A)
Function last takes a deque and gives the last element in the queue if deque is not empty else throws an error.

Examples:
> (last (deque 1 2 3 4 5 6))

- : Integer [more precisely: Positive-Byte]

6

> (last empty)

last: given deque is empty

procedure

(tail deq)  (Deque A)

  deq : (Deque A)
Function tail takes a deque and returns a deque with rest elements if its a non empty deque else throws an error.

Examples:
> (tail (deque 1 2 3 4 5 6))

- : (U (Deep Positive-Byte) (Shallow Positive-Byte))

#<Deep>

> (tail empty)

tail: given deque is empty

In the above example, (tail (deque 1 2 3 4 5 6)), removes 1 and returns (tail (deque 2 3 4 5 6)).

procedure

(init deq)  (Deque A)

  deq : (Deque A)
Function init takes a deque and returns a deque without the last element if its a non empty deque else throws an error.

Examples:
> (init (deque 1 2 3 4 5 6))

- : (U (Deep Positive-Byte) (Shallow Positive-Byte))

#<Deep>

> (init empty)

init: given deque is empty

In the above example, (init (deque 1 2 3 4 5 6)), removes the last element 6 and returns (deque 1 2 3 4 5)

procedure

(deque->list deq)  (Listof A)

  deq : (Deque A)
Function deque->list takes a deque and returns a list of elements. The list will have head of the given deque as its first element. If the given deque is empty, then it returns an empty list.

Example:
> (deque->list (deque 10 2 34 4 15 6))

- : (Listof Positive-Byte)

'(10 2 34 4 15 6)

procedure

(map func deq1 deq2 ...)  (Deque A)

  func : (A B ... B -> C)
  deq1 : (Deque A)
  deq2 : (Deque B)
Function map is similar to map for lists.

Examples:
> (deque->list (map add1 (deque 1 2 3 4 5 6)))

- : (Listof Positive-Index)

'(2 3 4 5 6 7)

> (deque->list (map * (deque 1 2 3 4 5 6) (deque 1 2 3 4 5 6)))

- : (Listof Positive-Index)

'(1 4 9 16 25 36)

procedure

(foldl func init deq1 deq2 ...)  C

  func : (C A B ... B -> C)
  init : C
  deq1 : (Deque A)
  deq2 : (Deque B)
Function foldl is similar to foldl

foldl currently does not produce correct results when the given function is non-commutative.

Examples:
> (foldl + 0 (deque 1 2 3 4 5 6))

- : Integer [more precisely: Nonnegative-Integer]

21

> (foldl * 1 (deque 1 2 3 4 5 6) (deque 1 2 3 4 5 6))

- : Integer [more precisely: Positive-Integer]

518400

procedure

(foldr func init deq1 deq2 ...)  C

  func : (C A B ... B -> C)
  init : C
  deq1 : (Deque A)
  deq2 : (Deque B)
Function foldr is similar to foldr

foldr currently does not produce correct results when the given function is non-commutative.

Examples:
> (foldr + 0 (deque 1 2 3 4 5 6))

- : Integer [more precisely: Nonnegative-Integer]

21

> (foldr * 1 (deque 1 2 3 4 5 6) (deque 1 2 3 4 5 6))

- : Integer [more precisely: Positive-Integer]

518400

procedure

(filter func que)  (Deque A)

  func : (A -> Boolean)
  que : (Deque A)
Function filter is similar to filter.

Examples:
> (define que (deque 1 2 3 4 5 6))
> (deque->list (filter (λ: ([x : Integer]) (> x 5)) que))

- : (Listof Positive-Byte)

'(6)

> (deque->list (filter (λ: ([x : Integer]) (< x 5)) que))

- : (Listof Positive-Byte)

'(1 2 3 4)

> (deque->list (filter (λ: ([x : Integer]) (<= x 5)) que))

- : (Listof Positive-Byte)

'(1 2 3 4 5)

procedure

(remove func que)  (Deque A)

  func : (A -> Boolean)
  que : (Deque A)
Function remove is similar to filter but remove removes the elements which match the predicate.

Examples:
> (deque->list (remove (λ: ([x : Integer]) (> x 5))
                       (deque 1 2 3 4 5 6)))

- : (Listof Positive-Byte)

'(1 2 3 4 5)

> (deque->list (remove (λ: ([x : Integer]) (< x 5))
                       (deque 1 2 3 4 5 6)))

- : (Listof Positive-Byte)

'(5 6)

> (deque->list (remove (λ: ([x : Integer]) (<= x 5))
                       (deque 1 2 3 4 5 6)))

- : (Listof Positive-Byte)

'(6)

procedure

(andmap func deq1 deq2 ...)  Boolean

  func : (A B ... B -> Boolean)
  deq1 : (Deque A)
  deq2 : (Deque B)
Function andmap is similar to andmap.

Examples:
> (andmap even? (deque 1 2 3 4 5 6))

- : Boolean

#f

> (andmap odd? (deque 1 2 3 4 5 6))

- : Boolean

#f

> (andmap positive? (deque 1 2 3 4 5 6))

- : Boolean

#t

> (andmap negative? (deque -1 -2))

- : Boolean

#t

procedure

(ormap func deq1 deq2 ...)  Boolean

  func : (A B ... B -> Boolean)
  deq1 : (Deque A)
  deq2 : (Deque B)
Function ormap is similar to ormap.

Examples:
> (ormap even? (deque 1 2 3 4 5 6))

- : Boolean

#t

> (ormap odd? (deque 1 2 3 4 5 6))

- : Boolean

#t

> (ormap positive? (deque -1 -2 3 4 -5 6))

- : Boolean

#t

> (ormap negative? (deque 1 -2))

- : Boolean

#t

procedure

(build-deque size func)  (Deque A)

  size : Natural
  func : (Natural -> A)
Function build-deque is similar to build-list.

Examples:
> (deque->list (build-deque 5 (λ:([x : Integer]) (add1 x))))

- : (Listof Integer)

'(1 2 3 4 5)

> (deque->list (build-deque 5 (λ:([x : Integer]) (* x x))))

- : (Listof Integer)

'(0 1 4 9 16)

procedure

(head+tail deq)  (Pair A (Deque A))

  deq : (Deque A)
Function head+tail returns a pair containing the head and the tail of the given deque.

Examples:
> (head+tail (deque 1 2 3 4 5))

- : (Pairof Positive-Byte (U (Deep Positive-Byte) (Shallow Positive-Byte)))

'(1 . #<Deep>)

> (head+tail (build-deque 5 (λ:([x : Integer]) (* x x))))

- : (Pairof Integer (U (Deep Integer) (Shallow Integer)))

'(0 . #<Deep>)

> (head+tail empty)

head+tail: given deque is empty

procedure

(last+init deq)  (Pair A (Deque A))

  deq : (Deque A)
Function last+init returns a pair containing the last element and the init of the given deque.

Examples:
> (last+init (deque 1 2 3 4 5))

- : (Pairof Positive-Byte (U (Deep Positive-Byte) (Shallow Positive-Byte)))

'(5 . #<Deep>)

> (last+init (build-deque 5 (λ:([x : Integer]) (* x x))))

- : (Pairof Integer (U (Deep Integer) (Shallow Integer)))

'(16 . #<Deep>)

> (last+init empty)

last+init: given deque is empty

2.3 Real-Time Deque🔗ℹ

 (require pfds/deque/real-time) package: pfds

Real-Time Deques eliminate the amortization by using two techniques Scheduling and a variant of Global Rebuilding called Lazy Rebuilding. The data structure gives a worst case running time of O(1) for the operations head, tail, last, init, enqueue-front and enqueue.

syntax

(Deque A)

Real-time double ended queue of type A.

procedure

(deque a ...)  (Deque A)

  a : A
Function deque creates a Real-Time Deque with the given inputs.

Example:
> (deque 1 2 3 4 5 6)

- : #(struct:Deque

      ((Rec

        g310539

        (U (Boxof (U (-> (Pairof Integer g310539)) (Pairof Integer g310539)))

           Null))

       Integer

       (Rec

        g310542

        (U (Boxof (U (-> (Pairof Integer g310542)) (Pairof Integer g310542)))

           Null))

       (Rec

        g310545

        (U (Boxof (U (-> (Pairof Integer g310545)) (Pairof Integer g310545)))

           Null))

       Integer

       (Rec

        g310548

        (U (Boxof (U (-> (Pairof Integer g310548)) (Pairof Integer g310548)))

           Null))))

#<Deque>

In the above example, the deque obtained will have 1 as its head element.

procedure

(empty t)  (Deque A)

  t : A
An empty deque.

procedure

(empty? dq)  Boolean

  dq : (Deque A)
Function empty? checks if the given deque is empty or not.

Examples:
> (empty? (deque 1 2 3 4 5 6))

- : Boolean

#f

> (empty? (empty Integer))

- : Boolean

#t

procedure

(enqueue a deq)  (Deque A)

  a : A
  deq : (Deque A)
Function enqueue takes an element and a deque and enqueues the given element into the deque.

Example:
> (enqueue 10 (deque 1 2 3 4 5 6))

- : #(struct:Deque

      ((Rec

        g310580

        (U (Boxof (U (-> (Pairof Integer g310580)) (Pairof Integer g310580)))

           Null))

       Integer

       (Rec

        g310583

        (U (Boxof (U (-> (Pairof Integer g310583)) (Pairof Integer g310583)))

           Null))

       (Rec

        g310586

        (U (Boxof (U (-> (Pairof Integer g310586)) (Pairof Integer g310586)))

           Null))

       Integer

       (Rec

        g310589

        (U (Boxof (U (-> (Pairof Integer g310589)) (Pairof Integer g310589)))

           Null))))

#<Deque>

In the above example, enqueue adds the element 10 to the end of (deque 1 2 3 4 5 6).

procedure

(enqueue-front a deq)  (Deque A)

  a : A
  deq : (Deque A)
Functionenqueue-front takes an element and a deque and adds the given element to the front of deque.

Example:
> (enqueue-front 10 (deque 1 2 3 4 5 6))

- : #(struct:Deque

      ((Rec

        g310601

        (U (Boxof (U (-> (Pairof Integer g310601)) (Pairof Integer g310601)))

           Null))

       Integer

       (Rec

        g310604

        (U (Boxof (U (-> (Pairof Integer g310604)) (Pairof Integer g310604)))

           Null))

       (Rec

        g310607

        (U (Boxof (U (-> (Pairof Integer g310607)) (Pairof Integer g310607)))

           Null))

       Integer

       (Rec

        g310610

        (U (Boxof (U (-> (Pairof Integer g310610)) (Pairof Integer g310610)))

           Null))))

#<Deque>

In the above example, enqueue adds the element 10 to the front of (deque 1 2 3 4 5 6) and returns (deque 10 1 2 3 4 5 6).

procedure

(head deq)  A

  deq : (Deque A)
Function head takes a deque and gives the first element in the deque if deque is not empty else throws an error.

Examples:
> (head (deque 1 2 3 4 5 6))

- : Integer

1

> (head (empty Integer))

head: given deque is empty

procedure

(last deq)  A

  deq : (Deque A)
Function last takes a deque and gives the last element in the queue if deque is not empty else throws an error.

Examples:
> (last (deque 1 2 3 4 5 6))

- : Integer

6

> (last (empty Integer))

last: given deque is empty

procedure

(tail deq)  (Deque A)

  deq : (Deque A)
Function tail takes a deque and returns a deque with rest elements if its a non empty deque else throws an error.

Examples:
> (tail (deque 1 2 3 4 5 6))

- : #(struct:Deque

      ((Rec

        g310660

        (U (Boxof (U (-> (Pairof Integer g310660)) (Pairof Integer g310660)))

           Null))

       Integer

       (Rec

        g310663

        (U (Boxof (U (-> (Pairof Integer g310663)) (Pairof Integer g310663)))

           Null))

       (Rec

        g310666

        (U (Boxof (U (-> (Pairof Integer g310666)) (Pairof Integer g310666)))

           Null))

       Integer

       (Rec

        g310669

        (U (Boxof (U (-> (Pairof Integer g310669)) (Pairof Integer g310669)))

           Null))))

#<Deque>

> (tail (empty Integer))

tail: given deque is empty

In the above example, (tail (deque 1 2 3 4 5 6)), removes the head of the given deque returns (deque 2 3 4 5 6).

procedure

(init deq)  (Deque A)

  deq : (Deque A)
Function init takes a deque and returns a deque without the last element if its a non empty deque else throws an error.

Examples:
> (init (deque 1 2 3 4 5 6))

- : #(struct:Deque

      ((Rec

        g310703

        (U (Boxof (U (-> (Pairof Integer g310703)) (Pairof Integer g310703)))

           Null))

       Integer

       (Rec

        g310706

        (U (Boxof (U (-> (Pairof Integer g310706)) (Pairof Integer g310706)))

           Null))

       (Rec

        g310709

        (U (Boxof (U (-> (Pairof Integer g310709)) (Pairof Integer g310709)))

           Null))

       Integer

       (Rec

        g310712

        (U (Boxof (U (-> (Pairof Integer g310712)) (Pairof Integer g310712)))

           Null))))

#<Deque>

> (init (empty Integer))

init: given deque is empty

In the above example, (init (deque 1 2 3 4 5 6)), removes the last element 6 of the given deque and returns (deque 1 2 3 4 5).

procedure

(deque->list deq)  (Listof A)

  deq : (Deque A)
Function deque->list takes a deque and returns a list of elements. The list will have head of the given deque as its first element. If the given deque is empty, then it returns an empty list.

Example:
> (deque->list (deque 10 2 34 4 15 6))

- : (Listof Integer)

'(10 2 34 4 15 6)

procedure

(map func deq1 deq2 ...)  (Deque A)

  func : (A B ... B -> C)
  deq1 : (Deque A)
  deq2 : (Deque B)
Function map is similar to map for lists.

Examples:
> (deque->list (map add1 (deque 1 2 3 4 5 6)))

- : (Listof Integer)

'(2 3 4 5 6 7)

> (deque->list (map * (deque 1 2 3 4 5 6) (deque 1 2 3 4 5 6)))

- : (Listof Integer)

'(1 4 9 16 25 36)

procedure

(foldl func init deq1 deq2 ...)  C

  func : (C A B ... B -> C)
  init : C
  deq1 : (Deque A)
  deq2 : (Deque B)
Function foldl is similar to foldl

foldl currently does not produce correct results when the given function is non-commutative.

Examples:
> (foldl + 0 (deque 1 2 3 4 5 6))

- : Integer

21

> (foldl * 1 (deque 1 2 3 4 5 6) (deque 1 2 3 4 5 6))

- : Integer

518400

procedure

(foldr func init deq1 deq2 ...)  C

  func : (C A B ... B -> C)
  init : C
  deq1 : (Deque A)
  deq2 : (Deque B)
Function foldr is similar to foldr

foldr currently does not produce correct results when the given function is non-commutative.

Examples:
> (foldr + 0 (deque 1 2 3 4 5 6))

- : Integer

21

> (foldr * 1 (deque 1 2 3 4 5 6) (deque 1 2 3 4 5 6))

- : Integer

518400

procedure

(filter func que)  (Deque A)

  func : (A -> Boolean)
  que : (Deque A)
Function filter is similar to filter.

Examples:
> (define que (deque 1 2 3 4 5 6))
> (deque->list (filter (λ: ([x : Integer]) (> x 5)) que))

- : (Listof Integer)

'(6)

> (deque->list (filter (λ: ([x : Integer]) (< x 5)) que))

- : (Listof Integer)

'(1 2 3 4)

> (deque->list (filter (λ: ([x : Integer]) (<= x 5)) que))

- : (Listof Integer)

'(1 2 3 4 5)

procedure

(remove func que)  (Deque A)

  func : (A -> Boolean)
  que : (Deque A)
Function remove is similar to filter but remove removes the elements which match the predicate.

Examples:
> (deque->list (remove (λ: ([x : Integer]) (> x 5))
                       (deque 1 2 3 4 5 6)))

- : (Listof Integer)

'(1 2 3 4 5)

> (deque->list (remove (λ: ([x : Integer]) (< x 5))
                       (deque 1 2 3 4 5 6)))

- : (Listof Integer)

'(5 6)

> (deque->list (remove (λ: ([x : Integer]) (<= x 5))
                       (deque 1 2 3 4 5 6)))

- : (Listof Integer)

'(6)

procedure

(andmap func deq1 deq2 ...)  Boolean

  func : (A B ... B -> Boolean)
  deq1 : (Deque A)
  deq2 : (Deque B)
Function andmap is similar to andmap.

Examples:
> (andmap even? (deque 1 2 3 4 5 6))

- : Boolean

#f

> (andmap odd? (deque 1 2 3 4 5 6))

- : Boolean

#f

> (andmap positive? (deque 1 2 3 4 5 6))

- : Boolean

#t

> (andmap negative? (deque -1 -2))

- : Boolean

#t

procedure

(ormap func deq1 deq2 ...)  Boolean

  func : (A B ... B -> Boolean)
  deq1 : (Deque A)
  deq2 : (Deque B)
Function ormap is similar to ormap.

Examples:
> (ormap even? (deque 1 2 3 4 5 6))

- : Boolean

#t

> (ormap odd? (deque 1 2 3 4 5 6))

- : Boolean

#t

> (ormap positive? (deque -1 -2 3 4 -5 6))

- : Boolean

#t

> (ormap negative? (deque 1 -2))

- : Boolean

#t

procedure

(build-deque size func)  (Deque A)

  size : Natural
  func : (Natural -> A)
Function build-deque is similar to build-list.

Examples:
> (deque->list (build-deque 5 (λ:([x : Integer]) (add1 x))))

- : (Listof Integer)

'(1 2 3 4 5)

> (deque->list (build-deque 5 (λ:([x : Integer]) (* x x))))

- : (Listof Integer)

'(0 1 4 9 16)

procedure

(head+tail deq)  (Pair A (Deque A))

  deq : (Deque A)
Function head+tail returns a pair containing the head and the tail of the given deque.

Examples:
> (head+tail (deque 1 2 3 4 5))

- : (Pairof

     Integer

     #(struct:Deque

       ((Rec

         g311086

         (U (Boxof (U (-> (Pairof Integer g311086)) (Pairof Integer g311086)))

            Null))

        Integer

        (Rec

         g311089

         (U (Boxof (U (-> (Pairof Integer g311089)) (Pairof Integer g311089)))

            Null))

        (Rec

         g311092

         (U (Boxof (U (-> (Pairof Integer g311092)) (Pairof Integer g311092)))

            Null))

        Integer

        (Rec

         g311095

         (U (Boxof (U (-> (Pairof Integer g311095)) (Pairof Integer g311095)))

            Null)))))

'(1 . #<Deque>)

> (head+tail (build-deque 5 (λ:([x : Integer]) (* x x))))

- : (Pairof

     Integer

     #(struct:Deque

       ((Rec

         g311112

         (U (Boxof (U (-> (Pairof Integer g311112)) (Pairof Integer g311112)))

            Null))

        Integer

        (Rec

         g311115

         (U (Boxof (U (-> (Pairof Integer g311115)) (Pairof Integer g311115)))

            Null))

        (Rec

         g311118

         (U (Boxof (U (-> (Pairof Integer g311118)) (Pairof Integer g311118)))

            Null))

        Integer

        (Rec

         g311121

         (U (Boxof (U (-> (Pairof Integer g311121)) (Pairof Integer g311121)))

            Null)))))

'(0 . #<Deque>)

> (head+tail (empty Integer))

head+tail: given deque is empty

procedure

(last+init deq)  (Pair A (Deque A))

  deq : (Deque A)
Function last+init returns a pair containing the last element and the init of the given deque.

Examples:
> (last+init (deque 1 2 3 4 5))

- : (Pairof

     Integer

     #(struct:Deque

       ((Rec

         g311155

         (U (Boxof (U (-> (Pairof Integer g311155)) (Pairof Integer g311155)))

            Null))

        Integer

        (Rec

         g311158

         (U (Boxof (U (-> (Pairof Integer g311158)) (Pairof Integer g311158)))

            Null))

        (Rec

         g311161

         (U (Boxof (U (-> (Pairof Integer g311161)) (Pairof Integer g311161)))

            Null))

        Integer

        (Rec

         g311164

         (U (Boxof (U (-> (Pairof Integer g311164)) (Pairof Integer g311164)))

            Null)))))

'(5 . #<Deque>)

> (last+init (build-deque 5 (λ:([x : Integer]) (* x x))))

- : (Pairof

     Integer

     #(struct:Deque

       ((Rec

         g311181

         (U (Boxof (U (-> (Pairof Integer g311181)) (Pairof Integer g311181)))

            Null))

        Integer

        (Rec

         g311184

         (U (Boxof (U (-> (Pairof Integer g311184)) (Pairof Integer g311184)))

            Null))

        (Rec

         g311187

         (U (Boxof (U (-> (Pairof Integer g311187)) (Pairof Integer g311187)))

            Null))

        Integer

        (Rec

         g311190

         (U (Boxof (U (-> (Pairof Integer g311190)) (Pairof Integer g311190)))

            Null)))))

'(16 . #<Deque>)

> (last+init (empty Integer))

last+init: given deque is empty