11 Enumerations

8.5

11 Enumerations

(require data/enumerate/lib)
	package: data-enumerate-lib

This library defines enumerations. Enumerations are represented as bijections between the natural numbers (or a prefix of them) and the values of some contract. Most of the enumerations defined in this library guarantee that the constructed bijection is efficient, in the sense that decoding a number is roughly linear in the number of bits taken to represent the number.

The two main options on an enumeration convert natural numbers back (from-nat) and forth (to-nat) between the elements of the contract. The simplest enumeration, natural/e is just a pair of identity functions:

> (from-nat natural/e 0)
0
> (to-nat natural/e 1)
1

but the library builds up more complex enumerations from simple ones. For example, you can enumerate lists of the elements of other enumerations using list/e:

> (from-nat (list/e natural/e natural/e natural/e) 0)
'(0 0 0)
> (from-nat (list/e natural/e natural/e natural/e) 1)
'(0 0 1)
> (from-nat (list/e natural/e natural/e natural/e) (expt 2 100))
'(10822639409 2238661967 110761420)
> (to-nat (list/e natural/e natural/e natural/e)
(list 123456789 123456789 123456789))
1881676417513891481838999

To interleave two enumerations, use or/e:

> (from-nat (or/e natural/e (list/e natural/e natural/e)) 0)
0
> (from-nat (or/e natural/e (list/e natural/e natural/e)) 1)
'(0 0)
> (from-nat (or/e natural/e (list/e natural/e natural/e)) 2)
1
> (from-nat (or/e natural/e (list/e natural/e natural/e)) 3)
'(0 1)
> (from-nat (or/e natural/e (list/e natural/e natural/e)) 4)
2

and to construct recursive data structures, use delay/e (with a little help from single/e to build a singleton enumeration for the base-case):

(define bt/e
  (delay/e
   (or/e (single/e #f)
         (list/e bt/e bt/e))))

> (from-nat bt/e 0)
#f
> (from-nat bt/e 1)
'(#f #f)
> (from-nat bt/e 2)
'(#f (#f #f))
> (from-nat bt/e 3)
'((#f #f) #f)
> (from-nat bt/e (expt 2 100))
'(((((((#f #f) #f) (#f (#f #f))) (((#f (#f #f)) (#f #f)) ((#f #f) #f)))
    (((#f #f) (#f #f)) (#f ((#f #f) (#f (#f #f))))))
   (((((#f #f) #f) (#f (#f #f))) (((#f (#f #f)) (#f #f)) ((#f #f) #f)))
    (((#f #f) #f) (#f ((#f #f) (#f (#f #f)))))))
  ((((((#f #f) #f) (#f (#f #f))) (((#f (#f #f)) (#f #f)) ((#f #f) #f)))
    (((#f #f) (#f #f)) (#f ((#f #f) (#f (#f #f))))))
   (((((#f #f) #f) (#f (#f #f))) (((#f (#f #f)) (#f #f)) ((#f #f) #f)))
    (((#f #f) #f) (#f ((#f #f) (#f (#f #f))))))))

The library also supports dependent enumerations. For example, to build ordered pairs, we can allow any natural number in the first component, but we want to have only natural numbers that are larger than that in the second component. The cons/de lets us express the dependency (using a notation similar to the contract cons/dc) and then we can use nat+/e, which builds a enumerators of natural numbers that are larger than or equal to its argument:

(define ordered-pair/e
  (cons/de [hd natural/e]
           [tl (hd) (nat+/e (+ hd 1))]))

> (for/list ([i (in-range 10)])
    (from-nat ordered-pair/e i))
'((0 . 1)
  (0 . 2)
  (1 . 2)
  (1 . 3)
  (0 . 3)
  (1 . 4)
  (2 . 3)
  (2 . 4)
  (2 . 5)
  (0 . 4))

Sometimes the best way to get a new enumeration is to adjust the output of a previous one. For example, if we wanted ordered pairs that were ordered in the other direction, we just need to swap the components of the pair from the ordered-pair/e enumeration. The function map/e adjusts existing enumerations. It accepts a contract describing the new kinds of values and functions that convert back and forth between the new and old kinds of values.

(define (swap-components x) (cons (cdr x) (car x)))
(define other-ordered-pair/e
  (map/e swap-components
         swap-components
         ordered-pair/e
         #:contract (cons/c natural?
                            natural?)))

> (for/list ([i (in-range 10)])
    (from-nat other-ordered-pair/e i))
'((1 . 0)
  (2 . 0)
  (2 . 1)
  (3 . 1)
  (3 . 0)
  (4 . 1)
  (3 . 2)
  (4 . 2)
  (5 . 2)
  (4 . 0))

Some of the combinators in the library are guaranteed to build enumeration functions that are bijections. But since map/e accepts arbitrary functions and or/e accepts enumerations with arbitrary contracts, they may project enumerations that are not be bijections. To help avoid errors, the contracts on map/e and or/e does some random checking to see if the result would be a bijection. Here’s an example that, with high probability, signals a contract violation.

> (map/e (λ (x) (floor (/ x 100)))
         (λ (x) (* x 100))
         natural/e
         #:contract natural?)
map/e: contract violation;
new enumeration would not be two-way
passing 569 to `from-nat` produces:
  569
which, when passed through `in' and `out', produces:
  500
which, when passed to `to-nat' produces 500,
but it should have been 569
  in: (->i
       ((in
         (e es c)
         (cond
          ((null? es) (-> (enum-contract e) c))
          (else
           (dynamic->*
            #:mandatory-domain-contracts
            (map enum-contract ...)
            #:range-contracts
            (list c)))))
        (out
         (e es c)
         (cond
          ((null? es) (-> c (enum-contract e)))
          (else
           (dynamic->*
            #:mandatory-domain-contracts
            (list c)
            #:range-contracts
            (map enum-contract ...)))))
        (e enum?)
        #:contract
        (c contract?))
       #:rest
       (es (listof enum?))
       #:pre/desc
       (in out e es)
       (appears-to-be-a-bijection?
        in
        out
        (cons e es))
       (result enum?))
  contract from:
      <pkgs>/data-enumerate-lib/data/enumerate.rkt
  blaming: top-level
   (assuming the contract is correct)
  at: <pkgs>/data-enumerate-lib/data/enumerate.rkt:45:3

The contract on or/e has a similar kind of checking that attempts to find overlaps between the elements of the enumerations in its arguments.

Sometimes, there is no easy way to make two functions that form a bijection. In that case you can use pam/e and supply only one function to make a one way enumeration. For example, we can make an enumeration of picts of binary trees like this:

(define pict-bt/e
  (pam/e
   (λ (bt)
     (binary-tidier
      (let loop ([bt bt])
        (cond
          [(list? bt) (apply tree-layout (map loop bt))]
          [else #f]))))
   bt/e
   #:contract pict?))

> (from-nat pict-bt/e 10)
> (from-nat pict-bt/e 11)
> (from-nat pict-bt/e 12)

Putting all these pieces together, here is a definition of an enumeration of closed expressions of the untyped lambda calculus.

(define/contract (lc-var/e bvs memo)
  (-> (set/c symbol?) (hash/c (set/c symbol?) enum?) enum?)
  ; memoization is a significant performance improvement
  (hash-ref!
   memo
   bvs
   (delay/e
    (or/e
     ; the variables currently in scope
     (apply fin/e (set->list bvs))

     ; the λ case; first we build a dependent
     ; pair of a bound variable and a body expression
     ; and then use map/e to build the usual syntax
     (map/e
      (λ (pr) `(λ (,(car pr)) ,(cdr pr)))
      (λ (λ-exp) (cons (caadr λ-exp) (caddr λ-exp)))
      (cons/de
       [hd symbol/e]
       [tl (hd) (lc-var/e (set-add bvs hd) memo)])
      #:contract (list/c 'λ (list/c symbol?) lc-exp?))

     ; application expressions
     (list/e (lc-var/e bvs memo) (lc-var/e bvs memo))))))

(define (lc-exp? x)
  (match x
    [(? symbol?) #t]
    [`(λ (,x) ,e) (and (symbol? x) (lc-exp? e))]
    [`(,a ,b) (and (lc-exp? a) (lc-exp? b))]))

(define lc/e (lc-var/e (set) (make-hash)))

> (from-nat lc/e 0)
'(λ (a) a)
> (from-nat lc/e 1)
'((λ (a) a) (λ (a) a))
> (from-nat lc/e 2)
'(λ (a) (λ (a) a))
> (to-nat lc/e
          '(λ (f)
             ((λ (x) (f (x x)))
              (λ (x) (f (x x))))))
120491078480010

11.1 Core Enumeration

(require data/enumerate)

package: data-enumerate-lib

The data/enumerate library contains the core subset of the enumeration library; its exports are described in the sections Enumeration Properties, Querying Enumerations, and Constructing Enumerations.

There are more enumeration functions than just the core, provided by data/enumerate/lib.

11.2 Enumeration Properties

In addition to the functions that form the bijection, an enumeration also has a contract, a count, and three boolean properties associated with it: if it is finite or not, if it is a bijection to the natural numbers or merely maps from the natural numbers without going back, and if the contract it has is a flat-contract?.

The functions in this section are predicates for the boolean properties and selection functions for other properties.

When an enumeration prints out, it shows the first few elements of the enumeration and, if it is either a finite enumeration or a one way enumeration, it prints finite and one-way, as appropriate. If those prefixes are not printed, then the enumeration is not finite and is not one-way.

procedure
(enum? x) → boolean?
x : any/c

Identifies a value as an enumeration.

procedure
(finite-enum? v) → boolean?
v : any/c

Identifies finite enumerations.

procedure
(infinite-enum? v) → boolean?
v : any/c

Identifies infinite enumerations, i. e., enumerations that map all natural numbers.

procedure
(two-way-enum? v) → boolean?
v : any/c

Identifies two way enumerations, i. e., enumerations that can map back and forth from values that satisfy the enumeration’s contract to the natural numbers.

procedure
(one-way-enum? v) → boolean?
v : any/c

Identifies one way enumerations, i. e., enumerations that can map only from the natural numbers to values that satisfy the enumeration’s contract, but not back.

procedure
(flat-enum? v) → boolean?
v : any/c

Identifies flat enumerations, i. e., enumerations whose contracts are flat-contract?s.

procedure
(enum-count e) → natural?
e : finite-enum?

Returns the number of elements of an enumeration.

procedure
(enum-contract e) → contract?
e : enum?

Returns the contract? that e enumerates.

11.3 Querying Enumerations

The functions in this section exercise the enumeration, turning natural numbers back and forth to the values that an enumeration enumerates.

procedure
(from-nat e n) → (enum-contract e)
  e : enum?
   n :
(if (finite-enum? e)
    (integer-in 0 (enum-count e))
    natural?)

Decodes n from e.

procedure
(to-nat e x) →
(if (finite-enum? e)
    (integer-in 0 (enum-count e))
    natural?)
  e : two-way-enum?
  x : (enum-contract e)

Encodes x from e.

procedure
(enum->list e [n]) → (listof (enum-contract e))
  e : enum?
   n :
(if (finite-enum? e)
    (integer-in 0 (enum-count e))
    natural?)
= (enum-count e)

Returns a list of the first n values in e.

If n is not supplied, then e must be a finite-enum.

Examples:

> (enum->list (list/e natural/e natural/e) 8)
'((0 0) (0 1) (1 0) (1 1) (0 2) (1 2) (2 0) (2 1))
> (enum->list (below/e 8))
'(0 1 2 3 4 5 6 7)

procedure
(in-enum e) → sequence?
e : enum?

Constructs a sequence suitable for use with for loops.

Note that enumerations are also sequences directly, too.

Example:

> (for/list ([i (in-enum (below/e 5))])
i)
'(0 1 2 3 4)

11.4 Constructing Enumerations

This section contains the fundamental operations for building enumerations.

value
natural/e : (and/c infinite-enum? two-way-enum? flat-enum?)

An enumeration of the natural numbers.

Examples:

> (from-nat natural/e 5)
5
> (to-nat natural/e 5)
5

procedure
(below/e max) →
(and/c (if (= max +inf.0)
           finite-enum?
           infinite-enum?)
       two-way-enum?
       flat-enum?)
  max : (or/c natural? +inf.0)

An enumeration of the first max naturals or, if max is +inf.0, all of the naturals.

Example:

> (enum->list (below/e 10))
'(0 1 2 3 4 5 6 7 8 9)

value
empty/e : (and/c finite-enum? two-way-enum? flat-enum?)

The empty enumeration.

Example:

> (enum->list empty/e)
'()

procedure
(map/e f f-inv #:contract c e) → enum?
  f : (-> (enum-contract e) c)
  f-inv : (-> c (enum-contract e))
  c : contract?
  e : enum?
(map/e f f-inv #:contract c e ...+) → enum?
   f :
(dynamic->* #:mandatory-domain-contracts (map enum-contract e)
            #:range-contracts (list c))
   f-inv :
(dynamic->* #:mandatory-domain-contracts (list c)
            #:range-contracts (map enum-contract e))
  c : contract?
  e : enum?

Builds an enumeration of c from e by calling f on each element of the enumeration and f-inv of each value of c.

If multiple enumerations are supplied, f is expected to accept any combination of elements of the given enumerations, i. e., the enumerations are not processed in parallel like the lists in map, but instead any element from the first enumeration may appear as the first argument to f and any element from the second may appear as the second argument to f, etc.

If e is a one way enumeration, then the result is a one way enumeration and f-inv is ignored. Otherwise, the result is a two way enumeration.

Examples:

> (define evens/e
    (map/e (λ (x) (* x 2))
           (λ (x) (/ x 2))
           natural/e
           #:contract (and/c natural?
                             even?)))
> (enum->list evens/e 10)
'(0 2 4 6 8 10 12 14 16 18)
> (define odds/e
    (map/e add1
           sub1
           evens/e
           #:contract (and/c natural? odd?)))
> (enum->list odds/e 10)
'(1 3 5 7 9 11 13 15 17 19)
> (define ordered-pair/e
    (map/e (λ (x y) (cons x (+ x y)))
           (λ (p)
             (define x (car p))
             (define y (cdr p))
             (values x (- y x)))
           natural/e
           natural/e
           #:contract (and/c (cons/c natural? natural?)
                             (λ (xy) (<= (car xy) (cdr xy))))))
> (enum->list ordered-pair/e 10)
'((0 . 0)
  (0 . 1)
  (1 . 1)
  (1 . 2)
  (0 . 2)
  (1 . 3)
  (2 . 2)
  (2 . 3)
  (2 . 4)
  (0 . 3))

procedure
(pam/e f #:contract c e ...+) → one-way-enum?
   f :
(dynamic->* #:mandatory-domain-contracts (map enum-contract e)
            #:range-contracts (list c))
  c : contract?
  e : enum?

Builds a one way enumeration from the given enumerations, combining their elements with f, in a manner similar to map/e.

Examples:

> (define rationals/e
    (pam/e /
           (nat+/e 1)
           (nat+/e 2)
           #:contract (and/c exact? rational? positive?)))
> (enum->list rationals/e 10)
'(1/2 1/3 1 2/3 1/4 1/2 3/2 1 3/4 1/5)

procedure
(except/e e [#:contract c] x ...) → two-way-enum?
  e : two-way-enum?
  c : (or/c #f contract?) = #f
  x : (enum-contract e)

Returns a two way enumeration identical to e except that all x are removed from the enumeration. See also but-not/e.

If c is #f, then it is not treated as a contract, instead the resulting contract is synthesized from contract on e and the xs.

Examples:

> (define except-1/e
(except/e natural/e 3))
> (from-nat except-1/e 2)
2
> (from-nat except-1/e 4)
5
> (to-nat except-1/e 2)
2
> (to-nat except-1/e 4)
3

procedure
(or/e [#:one-way-enum? one-way-enum?] e-p ...) → enum?
one-way-enum? : boolean? = #f
e-p : (or/c enum? (cons/c enum? (-> any/c boolean?)))

An enumeration of all of the elements of the enumerations in the e-p arguments.

If the enumerations have overlapping elements, then pass #t as one-way-enum? so the result is a one way enumeration.

In more detail, if all of the arguments have or are two way enumerations and one-way-enum? is #f, then the result is also a two way enumeration and each argument must come with a predicate to distinguish its elements from the elements of the other enumerations. If the argument is a pair, then the predicate in the second position of the pair is used. If the argument is an enumeration, then it must be a flat enumeration and the contract is used as its predicate.

If any of the arguments are one way enumerations (or one-way-enum? is not #f), then the result is a one way enumeration and any predicates in the arguments are ignored.

Example:

> (enum->list (or/e natural/e (list/e natural/e natural/e))
10)
'(0 (0 0) 1 (0 1) 2 (1 0) 3 (1 1) 4 (0 2))

procedure
(append/e [ #:one-way-enum? one-way-enum?]
e-p ...+) → enum?
one-way-enum? : boolean? = #f
e-p : (or/c enum? (cons/c enum? (-> any/c boolean?)))

An enumeration of the elements of the enumerations given in e-p that enumerates the elements in order that the enumerations are supplied. All but the last enumeration must be finite.

Like or/e the resulting enumeration is either a one way enumeration or a two way enumeration depending on the status of the arguments, and append/e has the same constraints on overlapping elements in the arguments.

Example:

> (enum->list
   (append/e (take/e natural/e 4)
             (list/e natural/e natural/e))
   10)
'(0 1 2 3 (0 0) (0 1) (1 0) (1 1) (0 2) (1 2))

procedure
(thunk/e eth
[ #:count count
#:two-way-enum? is-two-way-enum?
#:flat-enum? is-flat-enum?]) → enum?
   eth :
(-> (and/c (if (= count +inf.0)
               infinite-enum?
               (and/c finite-enum?
                      (let ([matching-count? (λ (e) (= (enum-count e) count))])
                        matching-count?)))
           (if is-two-way-enum?
               two-way-enum?
               one-way-enum?)
           (if is-flat-enum?
               flat-enum?
               (not/c flat-enum?))))
  count : (or/c +inf.0 natural?) = +inf.0
  is-two-way-enum? : any/c = #t
  is-flat-enum? : any/c = #t

A delayed enumeration identical to the result of eth.

The count, is-two-way-enum?, and is-flat-enum? arguments must be accurate predications of the properties of the result of eth.

The argument eth is invoked when the result enumeration’s contract or bijection is used, either directly or indirectly via a call to enum-contract, from-nat, or to-nat.

Example:

> (letrec ([bt/e (thunk/e
                  (λ ()
                    (or/e (single/e #f)
                          (list/e bt/e bt/e))))])
    (enum->list bt/e 5))
'(#f (#f #f) (#f (#f #f)) ((#f #f) #f) ((#f #f) (#f #f)))

procedure
(list/e [#:ordering ordering] e ...) → enum?
ordering : (or/c 'diagonal 'square) = 'square
e : enum?

An enumeration of lists of values enumerated by the e.

If ordering is 'square, it uses a generalized form of Szudzik’s “elegant” ordering and if ordering is 'diagonal, it uses a generalized form of Cantor’s mapping from pairs of naturals to naturals.

Examples:

> (enum->list (list/e
               (fin/e "Brian" "Jenny" "Ki" "Ted")
               natural/e
               (fin/e "Terra" "Locke" "Edgar" "Mash"))
              5)
'(("Brian" 0 "Terra")
  ("Jenny" 0 "Terra")
  ("Ki" 0 "Terra")
  ("Ted" 0 "Terra")
  ("Brian" 0 "Locke"))
> (enum->list (list/e natural/e natural/e)
              10)
'((0 0) (0 1) (1 0) (1 1) (0 2) (1 2) (2 0) (2 1) (2 2) (0 3))
> (enum->list (list/e #:ordering  'diagonal natural/e natural/e)
              10)
'((0 0) (0 1) (1 0) (0 2) (1 1) (2 0) (0 3) (1 2) (2 1) (3 0))

procedure
(dep/e e
f
[ #:f-range-finite? f-range-finite?
#:flat? flat?
#:one-way? one-way?]) → enum?
  e : enum?
   f :
(-> (enum-contract e)
    (and/c (if f-range-finite?
               finite-enum?
               infinite-enum?)
           (if one-way?
               one-way-enum?
               two-way-enum?)
           (if flat?
               flat-enum?
               (not/c flat-enum?))))
  f-range-finite? : boolean? = #f
  flat? : boolean? = #t
  one-way? : boolean? = (one-way-enum? e)

Constructs an enumeration of pairs like the first case of cons/de.

Examples:

> (define dep/e-ordered-pair/e
    (dep/e natural/e
           (λ (hd) (nat+/e (+ hd 1)))))
> (enum->list dep/e-ordered-pair/e 10)
'((0 . 1)
  (0 . 2)
  (1 . 2)
  (1 . 3)
  (0 . 3)
  (1 . 4)
  (2 . 3)
  (2 . 4)
  (2 . 5)
  (0 . 4))

procedure
(bounded-list/e k n)
→ (and/c finite-enum? two-way-enum? flat-enum?)
k : natural?
n : natural?

An enumeration of tuples of naturals with max n of length k.

Example:

> (enum->list (bounded-list/e 3 2)
5)
'((0 0 2) (1 0 2) (0 1 2) (1 1 2) (0 2 0))

11.5 More Enumeration Operations

(require data/enumerate/lib)
	package: data-enumerate-lib

The data/enumerate/lib library extends the data/enumerate library with some higher-level enumerations and functions on enumerations. Its contents are described in the sections Derived Enumeration Constructors, Enumeration Utility, and Pre-built Enumerations.

11.6 Derived Enumeration Constructors

syntax
(cons/de [car-id car-enumeration-expr]
         [cdr-id (car-id) cdr-enumeration-expr]
         cons/de-option)
(cons/de [car-id (cdr-id) car-enumeration-expr]
         [cdr-id cdr-enumeration-expr]
         cons/de-option)

cons/de-option =
| #:dep-expression-finite? expr cons/de-option
| #:flat? expr cons/de-option
| #:one-way? expr cons/de-option

Constructs an enumeration of pairs where the first component of the pair is drawn from the car-enumeration-expr’s value and the second is drawn from the cdr-enumeration-expr’s value.

In the first form, the cdr-enumeration-expr can use car-id, which is bound to the value of the car position of the pair, mutatis mutandis in the second case.

If #:dep-expression-finite? keyword and expression are present, then the value of the dependent expression is expected to be an infinite enumeration if the expression evaluates to #f and a finite enumeration otherwise. If the keyword is not present, then the dependent expressions are expected to always produce infinite enumerations.

If #:flat? is present and evaluates to a true value, then the value of both sub-expressions are expected to be flat enumerations and if it evaluates to #f, then the enumerations must not be flat enumerations. If the keyword is not present, then the dependent expressions are expected to always produce flat enumerations.

If #:one-way? is present and evaluates to a true value, then the result enumeration is a one way enumeration

The dependent expressions are expected to always produce two way enumerations if the non-dependent expression is a two way enumeration and the dependent the dependent expressions are expected to always produce one way enumerations if the non-dependent expression is a one way enumeration.

Examples:

> (define ordered-pair/e
    (cons/de [hd natural/e]
             [tl (hd) (nat+/e (+ hd 1))]))
> (enum->list ordered-pair/e 10)
'((0 . 1)
  (0 . 2)
  (1 . 2)
  (1 . 3)
  (0 . 3)
  (1 . 4)
  (2 . 3)
  (2 . 4)
  (2 . 5)
  (0 . 4))

procedure
(flip-dep/e e
f
[ #:f-range-finite? f-range-finite?]
#:flat? flat?
[ #:one-way? one-way?]) → enum?
  e : enum?
   f :
(-> (enum-contract e)
    (and/c (if f-range-finite?
               finite-enum?
               infinite-enum?)
           (if one-way?
               one-way-enum?
               two-way-enum?)
           (if flat?
               flat-enum?
               (not/c flat-enum?))))
  f-range-finite? : boolean? = #f
  flat? : #t
  one-way? : boolean? = (one-way-enum? e)

Constructs an enumeration of pairs like the second case of cons/de.

Examples:

> (define flip-dep/e-ordered-pair/e
    (flip-dep/e natural/e
                (λ (tl) (below/e tl))
                #:f-range-finite? #t))
> (enum->list flip-dep/e-ordered-pair/e 10)
'((0 . 1)
  (0 . 2)
  (1 . 2)
  (0 . 3)
  (1 . 3)
  (2 . 3)
  (0 . 4)
  (1 . 4)
  (2 . 4)
  (3 . 4))

procedure
(cons/e e1 e2 [#:ordering ordering]) → enum?
  e1 : enum?
  e2 : enum?
  ordering : (or/c 'diagonal 'square) = 'square

An enumeration of pairs of the values from e1 and e2. Like list/e, the ordering argument controls how the resting elements appear.

Examples:

> (enum->list (cons/e (take/e natural/e 4) (take/e natural/e 5)) 5)
'((0 . 0) (1 . 0) (2 . 0) (3 . 0) (0 . 1))
> (enum->list (cons/e natural/e (take/e natural/e 5)) 5)
'((0 . 0) (0 . 1) (0 . 2) (0 . 3) (0 . 4))
> (enum->list (cons/e (take/e natural/e 4) natural/e) 5)
'((0 . 0) (1 . 0) (2 . 0) (3 . 0) (0 . 1))
> (enum->list (cons/e natural/e natural/e) 5)
'((0 . 0) (0 . 1) (1 . 0) (1 . 1) (0 . 2))

procedure
(listof/e e
[ #:simple-recursive? simple-recursive?]) → enum?
   e :
(if simple-recursive?
    enum?
    infinite-enum?)
  simple-recursive? : any/c = #t

An enumeration of lists of values enumerated by e.

If simple-recursive? is #f, then the enumeration is constructed by first choosing a length and then using list/e to build lists of that length. If not, it builds a recursive enumeration using delay/e. The second option (which is the default) method is significantly more efficient when calling from-nat with large numbers, but it also has much shorter lists near the beginning of the enumeration.

Examples:

> (enum->list (listof/e natural/e #:simple-recursive? #f) 10)
'(() (0) (1) (0 0) (0 1) (2) (1 0) (0 0 0) (0 0 1) (0 1 0))
> (enum->list (listof/e natural/e) 10)
'(() (0) (0 0) (1) (1 0) (0 0 0) (1 0 0) (2) (2 0) (2 0 0))
> (to-nat (listof/e natural/e #:simple-recursive? #f) '(1 2 3 4 5 6))
2929082647
> (to-nat (listof/e natural/e) '(1 2 3 4 5 6))
19656567028457999961819135393421096124461042490733963

This plot shows some statistics for the first 500 items in each enumeration. The first plot shows how many different lengths each encounters. The red circles are when the #:simple-recursive? argument is #t and the blue stars are when that argument is #f.

This plot shows the different values, but this time on a log scale. As you can see, zero appears much more frequently when the #:simple-recursive? argument is #f.

procedure
(non-empty-listof/e e
[ #:simple-recursive? simple-recursive?])
→ enum?
   e :
(if simple-recursive?
    enum?
    infinite-enum?)
  simple-recursive? : any/c = #t

Like listof/e, but without the empty list.

Example:

> (enum->list (non-empty-listof/e natural/e) 5)
'((0) (0 0) (1) (1 0) (0 0 0))

procedure
(listof-n/e e n) → enum?
   e :
(if simple-recursive?
    enum?
    infinite-enum?)
  n : natural?

Example:

> (enum->list (listof-n/e natural/e 3) 10)
'((0 0 0)
  (0 0 1)
  (0 1 0)
  (0 1 1)
  (1 0 0)
  (1 0 1)
  (1 1 0)
  (1 1 1)
  (0 0 2)
  (1 0 2))

syntax
(delay/e enum-expression ... keyword-options)

keyword-options =
| #:count count-expression keyword-options
| #:two-way-enum? two-way-boolean-expression keyword-options
| #:flat-enum? flat-boolean-expression keyword-options

Returns an enumeration immediately, without evaluating the enum-expressions. When the result enumeration is inspected (directly or indirectly) via from-nat, to-nat, or enum-contract, the enum-expressions are evaluated and the value of the last one is cached. The value is then used as the enumeration.

If the count-expression is not supplied or if it evaluates to +inf.0, the resulting enumeration is a infinite enumeration. Otherwise the expression must evaluate to an natural? and the resulting enumeration is a finite enumeration of the given count.

If two-way-boolean-expression is supplied and it evaluates to anything other than #f, the resulting enumeration must be a two way enumeration; otherwise it must be a one way enumeration.

If flat-boolean-expression is supplied and it evaluates to anything other than #f, the resulting enumeration must be a flat enumeration; otherwise it must not be.

This expression form is useful for building recursive enumerations.

Example:

> (letrec ([bt/e (delay/e
                  (or/e (single/e #f)
                        (list/e bt/e bt/e)))])
    (enum->list bt/e 5))
'(#f (#f #f) (#f (#f #f)) ((#f #f) #f) ((#f #f) (#f #f)))

procedure
(take/e e n #:contract contract) → finite-enum?
  e : enum?
   n :
(if (finite-enum? e)
    (integer-in 0 (enum-count e))
    natural?)
   contract :
(λ (x)
  (and ((enum-contract e) x)
       (< (to-nat e x) n)))

Identical to e but only includes the first n values.

If the contract argument is not supplied, then e must be both a two way enumeration and a flat enumeration.

Example:

> (enum->list (take/e natural/e 5))
'(0 1 2 3 4)

procedure
(slice/e e lo hi #:contract contract) → finite-enum?
  e : enum?
   lo :
(and/c (if (finite-enum? e)
           (integer-in 0 (enum-count e))
           natural?)
       (<=/c hi))
   hi :
(if (finite-enum? e)
    (integer-in 0 (enum-count e))
    natural?)
   contract :
(and/c (enum-contract e)
       (λ (x)
         (<= lo (to-nat e x))
         (< (to-nat e x) hi)))

Identical to e but only includes the values between lo (inclusive) and hi (exclusive).

Examples:

> (enum->list (slice/e natural/e 5 10))
'(5 6 7 8 9)
> (slice/e natural/e 20 20)
#<empty-enum>

procedure
(fin/e x ...) → (and/c finite-enum? flat-enum?)
x : any/c

Builds an enumeration containing each x, in the order given.

If there are multiple arguments, then they must all be distinct; numbers except for +nan.0 and +nan.0 are compared using = and all other values (including +nan.0 and +nan.0) are compared using equal?.

If some other equality function is appropriate, use map/e with (below/e n) as the first argument to explicitly specify how to differentiate the elements of the enumeration.

If all of the arguments match the contract

(or/c symbol? boolean? char? keyword? null?
string? bytes? number?)

then the result is a two way enumeration, otherwise it is a one way enumeration.

Examples:

> (enum->list (fin/e "Brian" "Jenny" "Ki" "Ted"))
'("Brian" "Jenny" "Ki" "Ted")
> (enum->list (fin/e 1 3 5 7 9 11 13 15))
'(1 3 5 7 9 11 13 15)

procedure
(single/e v #:equal? same?) → (and/c finite-enum? two-way-enum?)
v : any/c
same? : equal?

Returns an enumeration of count one containing only v.

It uses same? to build the contract in the enumeration, always passing v as the first argument to same?.

Examples:

> (enum->list (single/e 12345))
'(12345)
> (enum->list (single/e (λ (x) x)))
'(#<procedure>)

procedure
(range/e lo hi) → (and/c two-way-enum? flat-enum?)
   lo :
(and/c (or/c -inf.0 exact-integer?)
       (<=/c hi))
  hi : (or/c exact-integer? +inf.0)

An enumeration of the exact integers between lo and hi.

Examples:

> (enum->list (range/e 10 20))
'(10 11 12 13 14 15 16 17 18 19 20)
> (enum->list (range/e 10 10))
'(10)
> (enum->list (range/e -inf.0 0) 10)
'(0 -1 -2 -3 -4 -5 -6 -7 -8 -9)
> (enum->list (range/e -inf.0 +inf.0) 10)
'(0 1 -1 2 -2 3 -3 4 -4 5)

procedure
(nat+/e lo) → (and/c infinite-enum? two-way-enum? flat-enum?)
lo : natural?

An enumeration of natural numbers larger than lo.

Example:

> (enum->list (nat+/e 42) 5)
'(42 43 44 45 46)

procedure
(but-not/e big small) → two-way-enum?
big : two-way-enum?
small : (and/c two-way-enum? flat-enum? finite-enum?)

Returns a two way enumeration like big except that the elements of small are removed. Every element in small must also be in big. See also except/e.

This operation is the one from Yorgey and Foner (2018)’s paper on subtracting bijections.

Example:

> (enum->list (but-not/e (below/e 10) (below/e 5)))
'(5 6 7 8 9)

Generally, but-not/e produces an enumeration that performs better than the result of (apply except/e big (enum->list small)) when the range of small is a large set. When it is small, using except/e performs better.

The two enumerations may also be in different orders.

Examples:

> (define (evens-below/e n)
    (map/e (λ (x) (* x 2))
           (λ (x) (/ x 2))
           (below/e (/ n 2))
           #:contract (and/c natural? even? (<=/c n))))
> (enum->list
   (but-not/e (below/e 20)
              (evens-below/e 20)))
'(5 11 3 13 7 15 1 17 9 19)
> (enum->list
   (apply except/e (below/e 20)
          (enum->list (evens-below/e 20))))
'(1 3 5 7 9 11 13 15 17 19)

procedure
(vector/e [#:ordering ordering] e ...) → enum?
ordering : (or/c 'diagonal 'square) = 'square
e : enum?

An enumeration of vectors of values enumerated by the e.

The ordering argument is the same as the one to list/e.

Example:

> (enum->list (vector/e (fin/e "Brian" "Jenny" "Ki" "Ted")
                        natural/e
                        (fin/e "Terra" "Locke" "Edgar" "Mash"))
              5)
'(#("Brian" 0 "Terra")
  #("Jenny" 0 "Terra")
  #("Ki" 0 "Terra")
  #("Ted" 0 "Terra")
  #("Brian" 0 "Locke"))

procedure
(permutations-of-n/e n)
→ (and/c finite-enum? two-way-enum? flat-enum?)
n : natural?

Returns an enumeration of the permutations of the natural numbers smaller than n.

Example:

> (enum->list (permutations-of-n/e 3))
'((0 1 2) (0 2 1) (1 0 2) (1 2 0) (2 0 1) (2 1 0))

procedure
(permutations/e l) → enum?
l : list?

Returns an enumeration of the permutations of l.

Example:

> (enum->list (permutations/e '(Brian Jenny Ted Ki)))
'((Brian Jenny Ted Ki)
  (Brian Jenny Ki Ted)
  (Brian Ted Jenny Ki)
  (Brian Ted Ki Jenny)
  (Brian Ki Jenny Ted)
  (Brian Ki Ted Jenny)
  (Jenny Brian Ted Ki)
  (Jenny Brian Ki Ted)
  (Jenny Ted Brian Ki)
  (Jenny Ted Ki Brian)
  (Jenny Ki Brian Ted)
  (Jenny Ki Ted Brian)
  (Ted Brian Jenny Ki)
  (Ted Brian Ki Jenny)
  (Ted Jenny Brian Ki)
  (Ted Jenny Ki Brian)
  (Ted Ki Brian Jenny)
  (Ted Ki Jenny Brian)
  (Ki Brian Jenny Ted)
  (Ki Brian Ted Jenny)
  (Ki Jenny Brian Ted)
  (Ki Jenny Ted Brian)
  (Ki Ted Brian Jenny)
  (Ki Ted Jenny Brian))

procedure
(set/e e) → enum?
e : enum?

Returns an enumeration of finite sets of values from e.

Examples:

> (enum->list (set/e (fin/e "Brian" "Jenny" "Ki")))
(list
(set)
(set "Brian")
(set "Jenny")
(set "Brian" "Jenny")
(set "Ki")
(set "Brian" "Ki")
(set "Jenny" "Ki")
(set "Brian" "Jenny" "Ki"))
> (enum->list (set/e natural/e) 10)
(list
(set)
(set 0)
(set 1)
(set 0 1)
(set 2)
(set 0 2)
(set 1 2)
(set 0 1 2)
(set 3)
(set 0 3))

procedure
(infinite-sequence/e e) → one-way-enum?
e : finite-enum?

Returns an enumeration of infinite sequences of elements of e. If e is an empty enumeration, returns an empty enumeration.

The infinite sequence corresponding to the natural number n is based on dividing the bits of (* (+ 1 n) pi) into chunks of bits where the largest value is (enum-count e). Since (* (+ 1 n) pi) has infinite digits, there are infinitely many such chunks. Since * is defined on all naturals, there are infinitely many such numbers. The generation of the sequence is efficient in the sense that the digits are generated incrementally without needing to go deeper than to find the requested value. The generation of the sequence is inefficient in the sense that the approximation of (* (+ 1 n) pi) gets larger and larger as you go deeper into the sequence.

Examples:

> (define bjtks/e (infinite-sequence/e
                   (fin/e 'Brian 'Jenny 'Ted 'Ki)))
> (for ([e (from-nat bjtks/e 42)]
        [i (in-range 10)])
    (printf "~a = ~a\n" i e))
0 = Ted
1 = Brian
2 = Ted
3 = Jenny
4 = Jenny
5 = Jenny
6 = Ki
7 = Jenny
8 = Ki
9 = Jenny

procedure
(hash-traverse/e f
xs
#:get-contract get-contract
#:contract contract) → enum?
  f : (-> any/c enum?)
  xs : (hash/c any/c any/c)
  get-contract : (-> any/c contract?)
  contract : contract?

Constructs an enumeration that simultaneously enumerates each of the enumerations returned by f applied to each value of xs.

If supplied, the get-contract argument is applied to the keys in the hash and is expected to return the contract for the corresponding enumeration. If the contract argument is supplied, it is used directly as the contract for all of enumerations. One of the two arguments must be supplied.

Examples:

> (define hash-traverse-1/e
    (let ([h (hash "Brian" 5 "Jenny" 15 "Ted" 25 "Ki" 30)])
      (hash-traverse/e (λ (n) (below/e n))
                       h
                       #:get-contract
                       (λ (v) (and/c exact-integer? (<=/c (hash-ref h v)))))))
> (enum->list hash-traverse-1/e 5)
'(#hash(("Brian" . 0) ("Jenny" . 0) ("Ki" . 0) ("Ted" . 0))
  #hash(("Brian" . 1) ("Jenny" . 0) ("Ki" . 0) ("Ted" . 0))
  #hash(("Brian" . 2) ("Jenny" . 0) ("Ki" . 0) ("Ted" . 0))
  #hash(("Brian" . 3) ("Jenny" . 0) ("Ki" . 0) ("Ted" . 0))
  #hash(("Brian" . 4) ("Jenny" . 0) ("Ki" . 0) ("Ted" . 0)))
> (to-nat hash-traverse-1/e
          '#hash(("Brian" . 4) ("Jenny" . 1) ("Ted" . 16) ("Ki" . 7)))
14334

procedure
(fold-enum f
bs
#:f-range-finite? f-range-finite?) → enum?
   f :
(if f-range-finite?
    (-> list? any/c finite-enum?)
    (-> list? any/c infinite-enum?))
  bs : list?
  f-range-finite? : #f

This is like foldr, but f returns enumerations of as and assumes that the accumulator is initialized to '().

Examples:

> (define fold-enum-1/e
    (fold-enum (λ (as b)
                 (below/e (+ (foldr + 0 as) b)))
               (list 1 2 3)
               #:f-range-finite? #t))
> (enum->list fold-enum-1/e 5)
'((0 0 0) (0 0 1) (0 0 2) (0 1 0) (0 1 1))
> (to-nat fold-enum-1/e (list 0 1 1))
4

11.7 Enumeration Utility

procedure
(random-index e) → natural?
e : enum?

Returns a random index into e. This works for finite and infinite enumerations, regardless of the count of the enumeration. For finite enumerations, it picks an index uniformly at random using random-natural and for infinite enumerations it picks a natural number n from the geometric distribution and uses that as an exponent, picking uniformly at random in the interval between (expt 2 n) and (expt 2 (+ n 1)).

Examples:

> (random-index natural/e)
2862558194308991670751670239175779720960130781378688176582991985758746782776490624130945188328059440
> (random-index (below/e 5000000000))
4880824453

11.8 Pre-built Enumerations

This section describes enumerations of some common Racket datatypes.

value
char/e : (and/c finite-enum? two-way-enum? flat-enum?)

An enumeration of characters.

Examples:

> (enum->list char/e 5)
'(#\a #\b #\c #\d #\e)
> (to-nat char/e #\λ)
955

value
string/e : (and/c infinite-enum? two-way-enum? flat-enum?)

An enumeration of strings.

Examples:

> (enum->list string/e 5)
'("a" "b" "c" "d" "e")
> (to-nat string/e "racket")
34015667898221561123161278314514

value
bool/e : (and/c finite-enum? two-way-enum? flat-enum?)

An enumeration of booleans.

Example:

> (enum->list bool/e)
'(#t #f)

value
symbol/e : (and/c infinite-enum? two-way-enum? flat-enum?)

An enumeration of symbols.

Examples:

> (enum->list symbol/e 5)
'(a b c d e)
> (to-nat symbol/e 'racket/base)
14463363701250876059548377015002918685315716675027977448257554

value
integer/e : (and/c infinite-enum? two-way-enum? flat-enum?)

An enumeration of the integers.

Example:

> (enum->list integer/e 10)
'(0 1 -1 2 -2 3 -3 4 -4 5)

value
flonum/e : (and/c infinite-enum? two-way-enum? flat-enum?)

An enumeration of flonum?s.

Examples:

> (enum->list flonum/e 10)
'(+inf.0 -inf.0 +nan.0 0.0 5e-324 -5e-324 1e-323 -1e-323 1.5e-323 -1.5e-323)
> (to-nat flonum/e 1.0)
9214364837600034818
> (to-nat flonum/e -1.0)
9214364837600034819

value
exact-rational/e
: (and/c infinite-enum? one-way-enum? flat-enum?)

An enumeration of rational numbers that duplicates entries (roughly, it enumerates all pairs of integers and natural numbers and then divides them which leads to duplicates).

Example:

> (enum->list exact-rational/e 13)
'(0 1/2 -1/2 1/3 -1/3 1 -1 2/3 -2/3 1/4 -1/4 1/2 -1/2)

value
two-way-real/e : (and/c infinite-enum? two-way-enum? flat-enum?)

An enumeration of reals; it includes only integer/e and flonum/e.

Example:

> (enum->list two-way-real/e 5)
'(0 +inf.0 1 -inf.0 -1)

value
real/e : (and/c infinite-enum? one-way-enum? flat-enum?)

An enumeration of reals; it includes exact-rational/e and flonum/e.

Example:

> (enum->list real/e 10)
'(+inf.0 0 -inf.0 1/2 +nan.0 -1/2 0.0 1/3 5e-324 -1/3)

value
two-way-number/e
: (and/c infinite-enum? two-way-enum? flat-enum?)

An enumeration of numbers; it includes two-way-real/e and complex numbers made from pairs of those real numbers.

Example:

> (enum->list two-way-number/e 10)
'(+inf.0
  0
  +inf.0+inf.0i
  1
  0.0+inf.0i
  -inf.0+inf.0i
  -inf.0
  0+1i
  +nan.0+inf.0i
  -1)

value
number/e : (and/c infinite-enum? one-way-enum? flat-enum?)

An enumeration of numbers; it includes real/e and complex numbers made from pairs of those real numbers.

Example:

> (enum->list number/e 10)
'(+inf.0 +inf.0+inf.0i 0 0 -inf.0+inf.0i 0+1/2i -inf.0 +nan.0+inf.0i 1/2 1/2)

1	Imperative Queues
2	Growable Vectors
3	Orders and Ordered Dictionaries
4	Splay Trees
5	Skip Lists
6	Interval Maps
7	Binary Heaps
8	Integer Sets
9	Bit Vectors
10	Union-Find: Sets with only Canonical Elements
11	Enumerations
	Bibliography

11.1	Core Enumeration
11.2	Enumeration Properties
11.3	Querying Enumerations
11.4	Constructing Enumerations
11.5	More Enumeration Operations
11.6	Derived Enumeration Constructors
11.7	Enumeration Utility
11.8	Pre-built Enumerations