Homework 5. Listdiffs

A listdiff is a pair whose car is L and whose cdr is eq? to either L, or to (cdrL), or to (cdr (cdrL))), etc. The cdr of a listdiff need not be a pair; it may be any object. Therefore, the car of a listdiff must either be a pair, or an object that is eq? to the cdr.

A listdiff D represents the prefix of (carD) that precedes (cdrD). For example, suppose ils is the improper list (a e i o u . y). Then (cons ils ils) returns an empty listdiff, (cons ils (cdr (cdr ils))) returns a listdiff with the same elements as the list (a e), and (cons (cdr ils) 'y) returns a listdiff with the same elements as (e i o u). Conversely, neither (cons '() ils) nor (cons ils (append '(a e i o u) 'y)) returns a listdiff.

Listdiffs are intended to be efficient representations for sublists. Normally if you want to represent a sublist of length N nondestructively, you must invoke cons N times to copy the N pairs in the sublist. However, with a listdiff you must invoke cons only once, to create the pair whose car is the first element of the sublist and whose cdr is the first element after the end of the sublist.

Define the following procedures, which are specified using the entry format described in R6RS §6.2, except that the label "procedure" is omitted. All but expr2ld have semantics similar to the standard Scheme procedures for lists; for example, cons-ld is to listdiffs as cons is to lists.

(null-ld? obj): Return #t if obj is an empty listdiff, #f otherwise.
(ld? obj): Return #t if obj is a listdiff, #f otherwise.
(cons-ld obj listdiff): Return a listdiff whose first element is obj and whose remaining elements are listdiff. (Unlike cons, the last argument cannot be an arbitrary object; it must be a listdiff.)
(car-ld listdiff): Return the first element of listdiff. It is an error if listdiff has no elements. ("It is an error" means the implementation can do anything it likes when this happens, and we won't test this case when grading.)
(cdr-ld listdiff): Return a listdiff containing all but the first element of listdiff. It is an error if listdiff has no elements.
(ld obj …): Return a newly allocated listdiff of its arguments.
(length-ld listdiff): Return the length of listdiff.
(append-ld listdiff …): Return a listdiff consisting of the elements of the first listdiff followed by the elements of the other listdiffs. The resulting listdiff is always newly allocated, except that it shares structure with the last argument. (Unlike append, the last argument cannot be an arbitrary object; it must be a listdiff.)
(ld-tail listdiff k): Return listdiff, except with the first k elements omitted. If k is zero, return listdiff. It is an error if k exceeds the length of listdiff.
(list->ld list): Return a listdiff that represents the same elements as list.
(ld->list listdiff): Return a list that represents the same elements as listdiff.
(map-ld proc listdiff1 listdiff2 ...): The listdiffs should all have the same listdiff length. Proc should accept as many arguments as there are listdiffs and return a single value. Proc should not mutate any of the listdiffs. The map-ld procedure applies proc element-wise to the elements of the listdiffs and returns a listdiff of the results, in order. This acts like the standard map function, except that it uses listdiffs instead of lists, and it avoids the overhead of converting its listdiff arguments to lists.
(expr2ld expr): Return a Scheme expression that is like expr except that it uses listdiff procedures instead of the corresponding list procedures.

Your implementation of the above routines must be free of side effects. Also, except for expr2ld, your implementation should avoid using unnecessary storage: e.g., it should minimize the number of calls to cons, and when it uses recursion it should when possible use tail recursion. Returned values may share storage with arguments; they need not copy their arguments.

Submit

Submit one file:

hw5.scm: should contain your procedure definitions. Your implementation should work on the SEASnet installation of racket, the Scheme implementation installed on SEASnet.

Here are a few examples:

(define ils (append '(a e i o u) 'y))
(define d1 (cons ils (cdr (cdr ils))))
(define d2 (cons ils ils))
(define d3 (cons ils (append '(a e i o u) 'y)))
(define d4 (cons '() ils))
(define d5 0)
(define d6 (ld ils d1 37))
(define d7 (append-ld d1 d2 d6))
(define e1 (expr2ld '(map (lambda (x) (+ x 1))
                          (list (length (list d1)) 2 4 8)
                          (append (list) (list-tail (list 1 16 32) 1)))))

(ld? d1)                               ⇒  #t
(ld? d2)                               ⇒  #t
(ld? d3)                               ⇒  #f
(ld? d4)                               ⇒  #f
(ld? d5)                               ⇒  #f
(ld? d6)                               ⇒  #t
(ld? d7)                               ⇒  #t

(null-ld? d1)                          ⇒  #f
(null-ld? d2)                          ⇒  #t
(null-ld? d3)                          ⇒  #f
(null-ld? d6)                          ⇒  #f

(car-ld d1)                            ⇒  a
(car-ld d2)                            ⇒  error
(car-ld d3)                            ⇒  error
(car-ld d6)                            ⇒  (a e i o u . y)

(length-ld d1)                         ⇒  2
(length-ld d2)                         ⇒  0
(length-ld d3)                         ⇒  error
(length-ld d6)                         ⇒  3
(length-ld d7)                         ⇒  5

(define kv1 (cons d1 'a))
(define kv2 (cons d2 'b))
(define kv3 (cons d3 'c))
(define kv4 (cons d1 'd))
(define d8 (ld kv1 kv2 kv3 kv4))
(define d9 (ld kv3 kv4))
(eq? d8 (ld-tail d8 0))                ⇒  #t
(equal? (ld->list (ld-tail d8 2))
        (ld->list d9))                 ⇒  #t
(null-ld? (ld-tail d8 4))              ⇒  #t
(ld-tail d8 -1)                        ⇒  error
(ld-tail d8 5)                         ⇒  error

(eq? (car-ld d6) ils)                  ⇒  #t
(eq? (car-ld (cdr-ld d6)) d1)          ⇒  #t
(eqv? (car-ld (cdr-ld (cdr-ld d6))) 37)⇒  #t
(equal? (ld->list d6)
        (list ils d1 37))              ⇒  #t
(eq? (list-tail (car d6) 3) (cdr d6))  ⇒  #t

(equal? e1 '(map-ld (lambda (x) (+ x 1))
                    (ld (length-ld (ld d1)) 2 4 8)
                    (append-ld (ld) (ld-tail (ld 1 16 32) 1))))
                                       ⇒  #t