## SRFI-134: Immutable deques

This SRFI defines immutable deques. A deque is a double-ended queue, a sequence which allows elements to be added or removed efficiently from either end.

This egg provides a stream-based implementation of the Banker's Deque representation described by Chris Okasaki in *Purely Functional Data Structures*. Basic deque operations (`ideque-front`, `ideque-add-back`, etc.) run in amortized constant time. Some extensions to the SRFI library are also included in the `(srfi 134 extensions)` module.

## TOC »

## SRFI Description

This page includes excerpts from the SRFI document, but is primarily intended to document the forms exported by the egg. For a full description of the SRFI, see the full SRFI document.

## Authors

The SRFI 134 specification is by Kevin Wortman & John Cowan.

This implementation is by Wolfgang Corcoran-Mathe, based on the two-list sample implementation by Shiro Kawai.

## Specification

Deques are disjoint from all other Scheme types.

## Procedures

### Constructors

`ideque``element``...`procedureReturns an ideque containing the

*elements*. The first element (if any) will be at the front of the ideque and the last element (if any) will be at the back. Takes O(*n*) time, where*n*is the number of elements.

`ideque-tabulate``n``proc`procedureInvokes the predicate

*proc*on every exact integer from 0 (inclusive) to*n*(exclusive). Returns an ideque containing the results in order of generation.

`ideque-unfold``stop?``mapper``successor``seed`procedureInvokes the predicate

*stop?*on*seed*. If it returns false, generate the next result by applying*mapper*to*seed*, generate the next seed by applying*successor*to*seed*, and repeat this algorithm with the new seed. If*stop?*returns true, return an ideque containing the results in order of accumulation.

`ideque-unfold-right``stop?``mapper``successor``seed`procedureInvokes the predicate

*stop?*on*seed*. If it returns false, generate the next result by applying*mapper*to*seed*, generate the next seed by applying*successor*to*seed*, and repeat the algorithm with the new seed. If*stop?*returns true, return an ideque containing the results in reverse order of accumulation.

### Predicates

`ideque?``x`procedureReturns

`#t`if*x*is an ideque, and`#f`otherwise. Takes O(1) time.

`ideque-empty?``ideque`procedureReturns

`#t`if*ideque*contains zero elements, and`#f`otherwise. Takes O(1) time.

`ideque=``elt=``ideque``...`procedureDetermines ideque equality, given an element-equality procedure. Ideque A equals ideque B if they are of the same length, and their corresponding elements are equal, as determined by

*elt=*. If the element-comparison procedure's first argument is from*idequei*, then its second argument is from*idequei+1*, i.e. it is always called as`(elt= a b)`for*a*an element of ideque A, and*b*an element of ideque B.In the n-ary case, every

*idequei*is compared to*idequei+1*(as opposed, for example, to comparing*ideque1*to every*idequei*, for i > 1). If there are zero or one ideque arguments,`ideque=`simply returns true. The name does not end in a question mark for compatibility with the SRFI-1 procedure`list=`.Note that the dynamic order in which the

*elt=*procedure is applied to pairs of elements is not specified. For example, if`ideque=`is applied to three ideques, A, B, and C, it may first completely compare A to B, then compare B to C, or it may compare the first elements of A and B, then the first elements of B and C, then the second elements of A and B, and so forth.The equality procedure must be consistent with

`eq?`. Note that this implies that two ideques which are`eq?`are always`ideque=`, as well; implementations may exploit this fact to "short-cut" the element-by-element comparisons.

`ideque-any``pred``ideque`procedure

`ideque-every``pred``ideque`procedureInvokes

*pred*on the elements of the*ideque*in order until one call returns a true/false value, which is then returned. If there are no elements, returns`#f`/`#t`.

### Queue operations

`ideque-front``ideque`procedure

`ideque-back``ideque`procedureReturns the front/back element of

*ideque*. It is an error for*ideque*to be empty.

`ideque-remove-front``ideque`procedure

`ideque-remove-back``ideque`procedureReturns an ideque with the front/back element of

*ideque*removed. It is an error for*ideque*to be empty.

`ideque-add-front``ideque``obj`procedure

`ideque-add-back``ideque``obj`procedureReturns an ideque with

*obj*pushed to the front/back of*ideque*.

### Other accessors

`ideque-ref``ideque``n`procedureReturns the

*nth*element of*ideque*. It is an error unless*n*is less than the length of*ideque*.

`ideque-take``ideque``n`procedure

`ideque-take-right``ideque``n`procedureReturns an ideque containing the first/last

*n*elements of*ideque*. It is an error if*n*is greater than the length of*ideque*.

`ideque-drop``ideque``n`procedure

`ideque-drop-right``ideque``n`procedureReturns an ideque containing all but the first/last

*n*elements of*ideque*. It is an error if*n*is greater than the length of*ideque*.

`ideque-split-at``ideque``n`procedureReturns two values, the results of

`(ideque-take ideque n)`and`(ideque-drop ideque n)`respectively, but may be more efficient.

### The whole ideque

`ideque-length``ideque`procedureReturns the length of

*ideque*as an exact integer.

`ideque-append``ideque``...`procedureReturns an ideque with the contents of the

*ideque*followed by the others, or an empty ideque if there are none.

`ideque-reverse``ideque`procedureReturns an ideque containing the elements of

*ideque*in reverse order.

`ideque-count``pred``ideque`procedure*pred*is a procedure taking a single value and returning a single value. It is applied element-wise to the elements of ideque, and a count is tallied of the number of elements that produce a true value. This count is returned. The dynamic order of calls to pred is unspecified.

`ideque-zip``ideque1``ideque2``...`procedureReturns an ideque of lists (not ideques) each of which contains the corresponding elements of ideques in the order specified. Terminates when all the elements of any of the ideques have been processed.

### Mapping

`ideque-map``proc``ideque`procedureApplies

*proc*to the elements of*ideque*and returns an ideque containing the results in order. The dynamic order of calls to*proc*is unspecified.

`ideque-filter-map``proc``ideque`procedureApplies

*proc*to the elements of*ideque*and returns an ideque containing the true (i.e. non-`#f`) results in order. The dynamic order of calls to*proc*is unspecified.

`ideque-for-each``proc``ideque`procedure

`ideque-for-each-right``proc``ideque`procedureApplies

*proc*to the elements of*ideque*in forward/reverse order and returns an unspecified result.

`ideque-fold``proc``nil``ideque`procedure

`ideque-fold-right``proc``nil``ideque`procedureInvokes

*proc*on the elements of*ideque*in forward/reverse order, passing the result of the previous invocation as a second argument. For the first invocation,*nil*is used as the second argument. Returns the result of the last invocation, or*nil*if there was no invocation.

`ideque-append-map``proc``ideque`procedureApplies

*proc*to the elements of*ideque*. It is an error if the result is not a list. Returns an ideque containing the elements of the lists in order.

### Filtering

`ideque-filter``pred``ideque`procedure

`ideque-remove``pred``ideque`procedureReturns an ideque containing the elements of

*ideque*that do/do not satisfy*pred*.

`ideque-partition``proc``ideque`procedureReturns two values, the results of

`(ideque-filter pred ideque)`and`(ideque-remove pred ideque)`respectively.

### Searching

`ideque-find-right``pred``ideque``#!optional``failure`procedureReturns the first/last element of

*ideque*that satisfies*pred*. If there is no such element, returns the result of invoking the thunk*failure*; the default thunk is`(lambda () #f)`.

`ideque-take-while``pred``ideque`procedure

`ideque-take-while-right``pred``ideque`procedureReturns an ideque containing the longest initial/final prefix of elements in

*ideque*all of which satisfy*pred*.

`ideque-drop-while``pred``ideque`procedure

`ideque-drop-while-right``pred``ideque`procedureReturns an ideque which omits the longest initial/final prefix of elements in

*ideque*all of which satisfy*pred*, but includes all other elements of*ideque*.

`ideque-span``pred``ideque`procedure

`ideque-break``pred``ideque`procedureReturns two values, the initial prefix of the elements of

*ideque*which do/do not satisfy*pred*, and the remaining elements.

### Conversion

`list->ideque``list`procedure

`ideque->list``ideque`procedureConversion between ideque and list structures. FIFO order is preserved, so the front of a list corresponds to the front of an ideque.

`generator->ideque``generator`procedure

`ideque->generator``ideque`procedureConversion between srfi-158 generators and ideques. A generator is a procedure that is called repeatedly with no arguments to generate consecutive values, and returns an end-of-file object when it has no more values to return.

## Extensions

The following forms are extensions to SRFI 134. Import the `(srfi 134 extensions)` module to use them.

`ideque-pop-front``ideque`procedure`ideque-pop-back``ideque`procedureReturns two values: the front/back element of

*ideque*and an ideque of the remaining elements. It is an error if*ideque*is empty.

`ideque-rotate``ideque``k`procedureCyclically permutes

*ideque*to the right or left, depending on the sign of the integer*k*. When*k*is positive, the elements of*ideque*are rotated*k*places to the right; when*k*is negative, they are rotated |*k*| places to the left.

`ideque->stream``ideque`procedure`stream->ideque``stream`procedureConversion between ideque and srfi-41 streams. FIFO order is preserved.

## Exceptions

This egg tries to give useful information when things go wrong. Procedure arguments are type-checked; when a type check fails, a condition of kind `(exn type assertion)` is raised. Ideque bounds errors are signaled by `(exn bounds assertion)` conditions. This conforms to the condition protocol used by CHICKEN's internal libraries.

See the Module (chicken condition) page for more information.

## About this egg

### Dependencies

The srfi-1, srfi-41, and typed-records eggs are required.

The test and test-generative eggs are required to run the included tests (use `chicken-install -test`).

### Maintainer

Wolfgang Corcoran-Mathe <wcm at sigwinch dot xyzzy without the zy>

### Repository

### Version history

- 0.1
- (2020-11-30) Initial release.
- 0.2
- (2021-01-02) Apply upstream fixes for
`ideque-take`and`ideque-drop`. - 0.2.1
- (2021-10-19) Add types and increase compiler optimization setting.
- 1.0.0
- (2022-08-22) Improve type and bounds checks. Follow CHICKEN's internal condition protocol.
- 1.1.0
- (2022-09-19) Switch to new banker's deque implementation. Add extensions. Greatly expand tests.
- 1.1.1
- (2023-03-04) Fix egg dependencies and add a missing type check.

## License

Copyright (c) 2015 Shiro Kawai <shiro@acm.org> Copyright © 2022 Wolfgang Corcoran-Mathe <wcm@sigwinch.xyz>

Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE