2 Deques

9.0.900

Racket

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
        g298595
        (U (Pairof Positive-Byte g298595) (Promiseof g298595) Null))
       Integer
       (Rec
        g298597
        (U (Pairof Positive-Byte g298597) (Promiseof g298597) 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
        g298667
        (U (Pairof Positive-Byte g298667) (Promiseof g298667) Null))
       Integer
       (Rec
        g298669
        (U (Pairof Positive-Byte g298669) (Promiseof g298669) 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
        g298688
        (U (Pairof Positive-Byte g298688) (Promiseof g298688) Null))
       Integer
       (Rec
        g298690
        (U (Pairof Positive-Byte g298690) (Promiseof g298690) 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
        g298782
        (U (Pairof Positive-Byte g298782) (Promiseof g298782) Null))
       Integer
       (Rec
        g298784
        (U (Pairof Positive-Byte g298784) (Promiseof g298784) 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
        g298825
        (U (Pairof Positive-Byte g298825) (Promiseof g298825) Null))
       Integer
       (Rec
        g298827
        (U (Pairof Positive-Byte g298827) (Promiseof g298827) 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
         g299499
         (U (Pairof Positive-Byte g299499) (Promiseof g299499) Null))
        Integer
        (Rec
         g299501
         (U (Pairof Positive-Byte g299501) (Promiseof g299501) Null))
        Integer)))
'(1 . #<Deque>)
> (head+tail (build-deque 5 (λ:([x : Integer]) (* x x))))
- : (Pairof
     Integer
     #(struct:Deque
       ((Rec g299525 (U (Pairof Integer g299525) (Promiseof g299525) Null))
        Integer
        (Rec g299527 (U (Pairof Integer g299527) (Promiseof g299527) 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
         g299568
         (U (Pairof Positive-Byte g299568) (Promiseof g299568) Null))
        Integer
        (Rec
         g299570
         (U (Pairof Positive-Byte g299570) (Promiseof g299570) Null))
        Integer)))
'(5 . #<Deque>)
> (last+init (build-deque 5 (λ:([x : Integer]) (* x x))))
- : (Pairof
     Integer
     #(struct:Deque
       ((Rec g299594 (U (Pairof Integer g299594) (Promiseof g299594) Null))
        Integer
        (Rec g299596 (U (Pairof Integer g299596) (Promiseof g299596) 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
        g303245
        (U (Boxof (U (-> (Pairof Integer g303245)) (Pairof Integer g303245)))
           Null))
       Integer
       (Rec
        g303248
        (U (Boxof (U (-> (Pairof Integer g303248)) (Pairof Integer g303248)))
           Null))
       (Rec
        g303251
        (U (Boxof (U (-> (Pairof Integer g303251)) (Pairof Integer g303251)))
           Null))
       Integer
       (Rec
        g303254
        (U (Boxof (U (-> (Pairof Integer g303254)) (Pairof Integer g303254)))
           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
        g303286
        (U (Boxof (U (-> (Pairof Integer g303286)) (Pairof Integer g303286)))
           Null))
       Integer
       (Rec
        g303289
        (U (Boxof (U (-> (Pairof Integer g303289)) (Pairof Integer g303289)))
           Null))
       (Rec
        g303292
        (U (Boxof (U (-> (Pairof Integer g303292)) (Pairof Integer g303292)))
           Null))
       Integer
       (Rec
        g303295
        (U (Boxof (U (-> (Pairof Integer g303295)) (Pairof Integer g303295)))
           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
        g303307
        (U (Boxof (U (-> (Pairof Integer g303307)) (Pairof Integer g303307)))
           Null))
       Integer
       (Rec
        g303310
        (U (Boxof (U (-> (Pairof Integer g303310)) (Pairof Integer g303310)))
           Null))
       (Rec
        g303313
        (U (Boxof (U (-> (Pairof Integer g303313)) (Pairof Integer g303313)))
           Null))
       Integer
       (Rec
        g303316
        (U (Boxof (U (-> (Pairof Integer g303316)) (Pairof Integer g303316)))
           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
        g303366
        (U (Boxof (U (-> (Pairof Integer g303366)) (Pairof Integer g303366)))
           Null))
       Integer
       (Rec
        g303369
        (U (Boxof (U (-> (Pairof Integer g303369)) (Pairof Integer g303369)))
           Null))
       (Rec
        g303372
        (U (Boxof (U (-> (Pairof Integer g303372)) (Pairof Integer g303372)))
           Null))
       Integer
       (Rec
        g303375
        (U (Boxof (U (-> (Pairof Integer g303375)) (Pairof Integer g303375)))
           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
        g303409
        (U (Boxof (U (-> (Pairof Integer g303409)) (Pairof Integer g303409)))
           Null))
       Integer
       (Rec
        g303412
        (U (Boxof (U (-> (Pairof Integer g303412)) (Pairof Integer g303412)))
           Null))
       (Rec
        g303415
        (U (Boxof (U (-> (Pairof Integer g303415)) (Pairof Integer g303415)))
           Null))
       Integer
       (Rec
        g303418
        (U (Boxof (U (-> (Pairof Integer g303418)) (Pairof Integer g303418)))
           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
         g303792
         (U (Boxof (U (-> (Pairof Integer g303792)) (Pairof Integer g303792)))
            Null))
        Integer
        (Rec
         g303795
         (U (Boxof (U (-> (Pairof Integer g303795)) (Pairof Integer g303795)))
            Null))
        (Rec
         g303798
         (U (Boxof (U (-> (Pairof Integer g303798)) (Pairof Integer g303798)))
            Null))
        Integer
        (Rec
         g303801
         (U (Boxof (U (-> (Pairof Integer g303801)) (Pairof Integer g303801)))
            Null)))))
'(1 . #<Deque>)
> (head+tail (build-deque 5 (λ:([x : Integer]) (* x x))))
- : (Pairof
     Integer
     #(struct:Deque
       ((Rec
         g303818
         (U (Boxof (U (-> (Pairof Integer g303818)) (Pairof Integer g303818)))
            Null))
        Integer
        (Rec
         g303821
         (U (Boxof (U (-> (Pairof Integer g303821)) (Pairof Integer g303821)))
            Null))
        (Rec
         g303824
         (U (Boxof (U (-> (Pairof Integer g303824)) (Pairof Integer g303824)))
            Null))
        Integer
        (Rec
         g303827
         (U (Boxof (U (-> (Pairof Integer g303827)) (Pairof Integer g303827)))
            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
         g303861
         (U (Boxof (U (-> (Pairof Integer g303861)) (Pairof Integer g303861)))
            Null))
        Integer
        (Rec
         g303864
         (U (Boxof (U (-> (Pairof Integer g303864)) (Pairof Integer g303864)))
            Null))
        (Rec
         g303867
         (U (Boxof (U (-> (Pairof Integer g303867)) (Pairof Integer g303867)))
            Null))
        Integer
        (Rec
         g303870
         (U (Boxof (U (-> (Pairof Integer g303870)) (Pairof Integer g303870)))
            Null)))))
'(5 . #<Deque>)
> (last+init (build-deque 5 (λ:([x : Integer]) (* x x))))
- : (Pairof
     Integer
     #(struct:Deque
       ((Rec
         g303887
         (U (Boxof (U (-> (Pairof Integer g303887)) (Pairof Integer g303887)))
            Null))
        Integer
        (Rec
         g303890
         (U (Boxof (U (-> (Pairof Integer g303890)) (Pairof Integer g303890)))
            Null))
        (Rec
         g303893
         (U (Boxof (U (-> (Pairof Integer g303893)) (Pairof Integer g303893)))
            Null))
        Integer
        (Rec
         g303896
         (U (Boxof (U (-> (Pairof Integer g303896)) (Pairof Integer g303896)))
            Null)))))
'(16 . #<Deque>)
> (last+init (empty Integer))
last+init: given deque is empty

1	Queues
2	Deques
3	Heaps
4	Random Access Lists
5	VList
6	Streams
7	Red-Black Trees
8	Tries
9	Treap