(module mp1 (lib "eopl.ss" "eopl") ;; ommitting defintions for Task 1 from public view ;; (provide duple invert swapper count-occurrences list-index flatten) ;; Task 2 (provide two-even-one-odd-upto-six) ;; Task 3 should be in mp1.txt; there is discussion of it below ;; Task 4 should be in mp1.txt; there is discussion of it below ;; Task 5 (provide longest-runs) ;; A Nat is a non-negative integer ;; A Listof[X] is one of: ;; - '() ;; - (cons X Listof[X] ) ;;; Remaining problems are about the following data definition ;; An IntegerSequence is one of: ;; - '() ;; - (cons (cons Nat Integer) IntegerSequence ;; TASK 2 (define two-even-one-odd-upto-six (list (cons 2 0) (cons 1 1) (cons 2 2) (cons 1 3) (cons 2 4) (cons 1 5) (cons 3 6))) ;; The exception to the above is a (deliberate) subtle "bug" ;; in the data definition; the data definition for IntegerSequence ;; does not disallow using zero as the k part of a pair, which ;; has an unfortunate consequence for clients of this data ;; definition. Here is an example of another definition for ;; two-even-one-odd-upto-six that takes advantage of the "bug" ;; and thus prints as: ;; ((1 . 0) (0 . 1) (1 . 0) (1 . 1) (2 . 2) (1 . 3) (2 . 4) (1 . 5) (3 . 6)) (define two-even-one-odd-upto-six-alt (list (cons 1 0) (cons 0 1) (cons 1 0) (cons 1 1) (cons 2 2) (cons 1 3) (cons 2 4) (cons 1 5) (cons 3 6))) ;; TASK 3 ;; either of the following answers were acceptable: ;; - "Yes, these two lists represent the same sequence" ;; and the two representations and one sequence, such as: ;; ((0 . 1) (3 . 2)) ;; ((3 . 2)) ;; which *both* represent the sequence [2, 2, 2] ;; (See the subtle bug discussed for Task 2 above.) ;; - "Yes, these two lists would be representations of the same sequence ;; if we ignore the representation invariant" ;; and the two representations and one sequence, such as: ;; ((3 . 2)) ;; ((2 . 2) (1 . 2)) ;; which *both* represent the sequence [2, 2, 2] ;; TASK 4 ;; The problem is that the provided implementation of intseq-append ;; does not preserve the representation invariant described for ;; IntegerSequence. ;; ;; An example input illustrating the problem: ; (intseq-append '((1 . 1)) '((1 . 1))) ;; should be: ((2 . 1)) ;; but it will instead produce ((1 . 1) (1 . 1)) ;; which does not satisfy the representation invariant. ;; TASK 5 ;; (Scheme's LET special form makes these bits of code a little ;; easier on the eyes.) ;; longest-runs : IntegerSequence -> Listof[Integer] ;; usage: (longest-runs iseq) returns integers with longest runs in iseq (define longest-runs (lambda (seq) (cond ((null? seq) '()) (else (let ((k (car (car seq))) (n (cdr (car seq)))) (longest-runs-helper (cdr seq) k (list n))))))) ;; longest-runs-helper : IntegerSequence Nat Listof[Int] -> Listof[Int] ;; usage: (longest-runs-helper iseq max sofar) processes iseq with ;; knowledge that earlier entries had maximum length runs of ;; length max and all integers in sofar had runs of length max (define longest-runs-helper (lambda (iseq max sofar) (cond ((null? iseq) sofar) (else (let ((k (car (car iseq))) (n (cdr (car iseq)))) (cond ((> k max) (longest-runs-helper (cdr iseq) k (list n))) ((= k max) (longest-runs-helper (cdr iseq) max (cons n sofar))) (else (longest-runs-helper (cdr iseq) max sofar)))))))) ;; Note that the code above *assumes* that there are no entries in ;; the input with k=0, because it was an easy thing to overlook. ;; But for completeness, here is a version that does handle that ;; case properly (by not relying on the representation invariant at ;; all). ;; A Pos is a positive integer ;; longest-runs-alt : IntegerSequence -> Listof[Int] ;; usage: (longest-runs iseq) returns integers with longest runs in iseq (define longest-runs-alt (lambda (iseq) (cond ((null? iseq) '()) (else (let ((k (car (car iseq))) (n (cdr (car iseq)))) (cond ((= k 0) (longest-runs-alt (cdr iseq))) (else (longest-runs-alt-helper (cdr iseq) k (list n) k n )))))))) ;; longest-runs-alt-helper : IntegerSequence Pos Listof[Int] Pos Int ;; usage: (longest-runs-alt-helper iseq max sofar last-len last-int) ;; where ;; iseq is remainder of sequence to process ;; max-len is length of max run seen; ;; sofar is integers with runs of length max ;; last-len is length of last (non-empty) run seen ;; last-int is integer in last (non-empty) run seen (define longest-runs-alt-helper (lambda (iseq max-len sofar last-len last-int) (cond ((null? iseq) sofar) (else (let ((k (car (car iseq))) (n (cdr (car iseq)))) (cond ((= k 0) (longest-runs-alt-helper (cdr iseq) max-len sofar last-len last-int)) (else (let ((real-last-len (if (= n last-int) (+ last-len k) k))) (cond ((> real-last-len max-len) (longest-runs-alt-helper (cdr iseq) real-last-len (list n) real-last-len n)) ((= real-last-len max-len) (longest-runs-alt-helper (cdr iseq) max-len (cons n sofar) real-last-len n)) ((< real-last-len max-len) (longest-runs-alt-helper (cdr iseq) max-len sofar real-last-len n))))))))))) )