Version: 5.0.1.6

### 2Deques

Following Deque data structures implement and provide the functions deque, empty?, enqueue, enqueue-front, head, tail, last, init and deque->list. All the deque structures are polymorphic.

#### 2.1Bankers Deque

 (require (planet krhari/pfds:1:5/bankers-deque))

Bankers Deques are Amortized double ended deques also known as deque developed using Bankers method. Provides amortized running time of O(1) for the operations head, tail, last, init, enqueue-front and enqueue. Uses lazy evaluation and memoization to achieve the amortized running time.

 (Deque A)
A banker’s deque of type A.

 (deque a ...) → (Deque A) a : A
Function deque creates a Bankers Deque with the given inputs.
 Example: > (deque 1 2 3 4 5 6) - : (Deque Positive-Fixnum) #

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

 (empty t) → (Deque A) t : A
An empty deque of type t.
 Examples: > (empty Nothing) - : (Deque Nothing) # > (empty Integer) - : (Deque Integer) #

 (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

 (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)) - : (Deque Positive-Fixnum) #
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.

 (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)) - : (Deque Positive-Fixnum) #

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.

 (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)) - : Positive-Fixnum 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.

 (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)) - : Positive-Fixnum 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.

 (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)) - : (Deque Positive-Fixnum) # > (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).

 (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)) - : (Deque Positive-Fixnum) # > (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).

 (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-Fixnum) '(10 2 34 4 15 6) > (deque->list (empty Integer)) - : (Listof Integer) '()

 (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 Exact-Positive-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 Exact-Positive-Integer) '(1 4 9 16 25 36)

 (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)) - : Exact-Nonnegative-Integer 21 > (foldl * 1 (deque 1 2 3 4 5 6) (deque 1 2 3 4 5 6)) - : Exact-Positive-Integer 518400

 (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)) - : Exact-Nonnegative-Integer 21 > (foldr * 1 (deque 1 2 3 4 5 6) (deque 1 2 3 4 5 6)) - : Exact-Positive-Integer 518400

 (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-Fixnum) '(6) > (deque->list (filter (λ: ([x : Integer]) (< x 5)) que)) - : (Listof Positive-Fixnum) '(1 2 3 4) > (deque->list (filter (λ: ([x : Integer]) (<= x 5)) que)) - : (Listof Positive-Fixnum) '(1 2 3 4 5)

 (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-Fixnum)

'(1 2 3 4 5)

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

- : (Listof Positive-Fixnum)

'(5 6)

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

- : (Listof Positive-Fixnum)

'(6)

 (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

 (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

 (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)

 (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-Fixnum (Deque Positive-Fixnum)) '(1 . #) > (head+tail (build-deque 5 (λ:([x : Integer]) (* x x)))) - : (Pairof Integer (Deque Integer)) '(0 . #) > (head+tail (empty Integer)) head+tail: given deque is empty

 (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-Fixnum (Deque Positive-Fixnum)) '(5 . #) > (last+init (build-deque 5 (λ:([x : Integer]) (* x x)))) - : (Pairof Integer (Deque Integer)) '(16 . #) > (last+init (empty Integer)) last+init: given deque is empty

#### 2.2Implicit Deque

 (require (planet krhari/pfds:1:5/implicitdeque))

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.

 (Deque A)
Implicit double ended queue of type A.

 (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 (Shallow Positive-Fixnum) (Deep Positive-Fixnum)) #

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

 empty : (Deque Nothing)
An empty deque

 (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

 (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 (Shallow Positive-Fixnum) (Deep Positive-Fixnum)) #

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

 (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 (Shallow Positive-Fixnum) (Deep Positive-Fixnum)) #

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.

 (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)) - : Positive-Fixnum 1 > (head empty) head: given deque is empty

 (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)) - : Positive-Fixnum 6 > (last empty) last: given deque is empty

 (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 (Shallow Positive-Fixnum) (Deep Positive-Fixnum)) # > (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)).

 (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 (Shallow Positive-Fixnum) (Deep Positive-Fixnum)) # > (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)

 (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-Fixnum) '(10 2 34 4 15 6)

 (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 Exact-Positive-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 Exact-Positive-Integer) '(1 4 9 16 25 36)

 (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)) - : Exact-Nonnegative-Integer 21 > (foldl * 1 (deque 1 2 3 4 5 6) (deque 1 2 3 4 5 6)) - : Exact-Positive-Integer 518400

 (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)) - : Exact-Nonnegative-Integer 21 > (foldr * 1 (deque 1 2 3 4 5 6) (deque 1 2 3 4 5 6)) - : Exact-Positive-Integer 518400

 (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-Fixnum) '(6) > (deque->list (filter (λ: ([x : Integer]) (< x 5)) que)) - : (Listof Positive-Fixnum) '(1 2 3 4) > (deque->list (filter (λ: ([x : Integer]) (<= x 5)) que)) - : (Listof Positive-Fixnum) '(1 2 3 4 5)

 (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-Fixnum)

'(1 2 3 4 5)

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

- : (Listof Positive-Fixnum)

'(5 6)

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

- : (Listof Positive-Fixnum)

'(6)

 (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

 (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

 (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)

 (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-Fixnum (U (Shallow Positive-Fixnum) (Deep Positive-Fixnum))) '(1 . #) > (head+tail (build-deque 5 (λ:([x : Integer]) (* x x)))) - : (Pairof Integer (U (Shallow Integer) (Deep Integer))) '(0 . #) > (head+tail empty) head+tail: given deque is empty

 (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-Fixnum (U (Shallow Positive-Fixnum) (Deep Positive-Fixnum))) '(5 . #) > (last+init (build-deque 5 (λ:([x : Integer]) (* x x)))) - : (Pairof Integer (U (Shallow Integer) (Deep Integer))) '(16 . #) > (last+init empty) last+init: given deque is empty

#### 2.3Real-Time Deque

 (require (planet krhari/pfds:1:5/realtimedeque))

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.

 (Deque A)
Real-time double ended queue of type A.

 (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) - : (Deque Positive-Fixnum) #

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

 (empty t) → (Deque A) t : A
An empty deque.

 (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

 (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)) - : (Deque Positive-Fixnum) #

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

 (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)) - : (Deque Positive-Fixnum) #

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).

 (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)) - : Positive-Fixnum 1 > (head (empty Integer)) head: given deque is empty

 (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)) - : Positive-Fixnum 6 > (last (empty Integer)) last: given deque is empty

 (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)) - : (Deque Positive-Fixnum) # > (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).

 (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)) - : (Deque Positive-Fixnum) # > (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).

 (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-Fixnum) '(10 2 34 4 15 6)

 (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 Exact-Positive-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 Exact-Positive-Integer) '(1 4 9 16 25 36)

 (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)) - : Exact-Nonnegative-Integer 21 > (foldl * 1 (deque 1 2 3 4 5 6) (deque 1 2 3 4 5 6)) - : Exact-Positive-Integer 518400

 (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)) - : Exact-Nonnegative-Integer 21 > (foldr * 1 (deque 1 2 3 4 5 6) (deque 1 2 3 4 5 6)) - : Exact-Positive-Integer 518400

 (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-Fixnum) '(6) > (deque->list (filter (λ: ([x : Integer]) (< x 5)) que)) - : (Listof Positive-Fixnum) '(1 2 3 4) > (deque->list (filter (λ: ([x : Integer]) (<= x 5)) que)) - : (Listof Positive-Fixnum) '(1 2 3 4 5)

 (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-Fixnum)

'(1 2 3 4 5)

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

- : (Listof Positive-Fixnum)

'(5 6)

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

- : (Listof Positive-Fixnum)

'(6)

 (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

 (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

 (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)

 (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-Fixnum (Deque Positive-Fixnum)) '(1 . #) > (head+tail (build-deque 5 (λ:([x : Integer]) (* x x)))) - : (Pairof Integer (Deque Integer)) '(0 . #) > (head+tail (empty Integer)) head+tail: given deque is empty

 (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-Fixnum (Deque Positive-Fixnum)) '(5 . #) > (last+init (build-deque 5 (λ:([x : Integer]) (* x x)))) - : (Pairof Integer (Deque Integer)) '(16 . #) > (last+init (empty Integer)) last+init: given deque is empty