11 Enumerations

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.

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

11.2 Querying Enumerations

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

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

Note that enumerations are also sequences directly, too.

11.3 Constructing Enumerations

This section contains the fundamental operations for building enumerations.

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.

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.

If the enumerations have overlapping elements, then pass #f 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 #f), then the result is a one way enumeration and any predicates in the arguments are ignored.

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.

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.

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.

11.4 More Enumeration Operations

The data/enumerate/lib extends data/enumerate with a bunch of additional ways to build enumerations, some utility functions, and a bunch of pre-built enumerations.

11.4.1 More Enumeration Constructors

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.

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.

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.

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 exact-nonnegative-integer? 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 one way enumeration; otherwise it must be a two 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.

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