6.6

4.6 Pairs and Lists

A pair combines two values, and a list is either the constant null or a pair whose second element is a list. Pairs and lists are transparent immutable values, and they may be concrete or symbolic. Two pairs or two lists are eq? (resp. equal?) if their corresponding elements are eq? (resp. equal?).

As values of unsolvable types, symbolic pairs and lists cannot be created via define-symbolic[*]. Instead, they are created by applying pair- or list-producing procedures to symbolic inputs, or by controlling the application of such procedures with symbolic values. This pattern for creating non-primitive symbolic values generalizes to all unsolvable datatypes.

Examples:
> (define-symbolic x y z n integer?)
> (define xs (take (list x y z) n))        ; (1) xs is a symbolic list
> (define sol (solve (assert (null? xs))))
> (evaluate xs sol)

'()

> (define sol
    (solve (begin
             (assert (= (length xs) 2))
             (assert (not (equal? xs (reverse xs))))
             (assert (equal? xs (sort xs <))))))
> (evaluate xs sol)

'(1 4)

Examples:
> (define-symbolic b boolean?)
> (define p (if b (cons 1 2) (cons 4 #f))) ; (2) p is a symbolic pair
> (define sol (solve (assert (boolean? (cdr p)))))
> (evaluate p sol)

'(4 . #f)

> (define sol (solve (assert (odd? (car p)))))
> (evaluate p sol)

'(1 . 2)

Rosette lifts the following operations on pairs and lists: