wiki:Tutorial7

HtDP

There is an example of how to do exercises from HtDP according to the described process.

; size
; produce the number of symbols in a given list

; list-of-lists
;
; a list is either/one of:
;    the-empty-list 
;    (cons symbol list) - a pair of a symbol and a list/the-empty-list
;    (cons list list)   - a pair of a list and another list.
;
; there are 3 possibilities, 3 clauses, 3 invariants
;
; the-empty-list is a list
; a list is list-of-symbols-and-lists

(define l1 '())
(define l2 '(list of symbols))
(define l3 '(list of symbols (and lists)))
(define l4 '(list of () lists))
(define l5 '(()))

; [Symbol] -> Number
;(define (size (l) 0))       ; a stub, producing a value of proper type

; checking of expectations, assertions
;(= (size l1) 0)
;(= (size l2) 3)
;(= (size l3) 5)
;(= (size l4) 3)
;(= (size l5) 0)

; fixes
(define empty? null?)

; template:

; 1. 3 clauses in the data definition produces 3 clauses of a cond in the template.
;
; (define (size l)
;    (cond (() ...)
;          (() ...)
;          (() ...)))

; 2. adding selectors for non-atomic/compound data
;
; (define (size l)
;    (cond (() ...)                     ; the-empty-list is an atom
;          (() ... (car l) ... (cdr l))
;          (   ... (car l) ... (cdr l))))

; 3. adding tests/guards for each clause.
;
; (define (size l)
;    (cond ((empty? l)        ...)
;          ((symbol? (car l)) ... (car l) ... (cdr l)) 
;          (else              ... (car l) ... (cdr l))))

; 4. adding recursion
;
; (define (size l)
;    (cond ((empty? l)        ...)
;          ((symbol? (car l)) ... (car l) (size (cdr l)))
;          (else              ... (size (car l)) (size (cdr l)))))

; 5. adding the base case
;
; (define (size l)
;    (cond ((empty? l)        0)  ; the size of empty list is 0
;          ((symbol? (car l)) ... (car l) (size (cdr l)))
;          (else              ... (size (car l)) (size (cdr l)))))

; 6. adding combining functions
;
; (define (size l)
;    (cond ((empty? l)        0)
;          ((symbol? (car l)) (+ 1 (size (cdr l))))
;          (else              (+ (size (car l)) (size (cdr l))))))

(define (size l)
  (cond ((empty? l) 0)
	((symbol? (car l)) (+ 1 (size (cdr l))))
	(else (+ (size (car l)) (size (cdr l))))))

; testing
(and
 (= (size l1) 0)
 (= (size l2) 3)
 (= (size l3) 5)
 (= (size l4) 3)
 (= (size l5) 0))

;---------------------------------------------------------------------------------------

; occurs
; produce a number of occuriences of a given symbol

(define l1 '())
(define l2 '(this or that))
(define l3 '(this and (this and that)))

; [Symbol] -> Symbol -> Number
;(define (occurs l s) 0)

; checking expectations:
;
;(= (occurs l1 'this) 0)
;(= (occurs l2 'xxx) 0)
;(= (occurs l2 'that) 1)
;(= (occurs l3 'this) 2)

; template:
;
; (define (occurs l s)
;    (cond ((empty? l)    ...)
;          ((... (car l)) ... (car l) (occurs (cdr l) s))
;          (else          ... (occurs (car l) s) (occurs (cdr l) s))))
;

; fill the template in a systematic way - in case when it is a symbol,
;    check whether it is the same symbol or not

(define (occurs l s)
  (cond ((empty? l) 0)
	((symbol? (car l)) (if (eq? s (car l))
			       (+ 1 (occurs (cdr l) s))
			       (occurs (cdr l) s)))
	(else (+ (occurs (car l) s) (occurs (cdr l) s)))))

(and
 (= (occurs l1 'this) 0)
 (= (occurs l2 'that) 1)
 (= (occurs l2 'xxx) 0)
 (= (occurs l3 'this) 2))

; do not go deep into sub-lists

(define (occurs1 l s)
  (cond ((empty? l) 0)
	((eq? s (car l)) (+ 1 (occurs1 (cdr l) s)))
	(else            (occurs1 (cdr l) s))))

(and
 (= (occurs1 l1 'this) 0)
 (= (occurs1 l2 'that) 1)
 (= (occurs1 l2 'xxx) 0)
 (= (occurs1 l3 'this) 1))

;----------------------------------------------------------------------------------------

; replace
; replace occurence of a symbol x with symbol y in a list l, producing a new 
; structurally identical list (of the same shape).
; basic immutability 

; Symbol -> Symbol -> [Symbol] -> [Symbol]
;(define (replace x y l) '())

(define l1 '(this and that))
(define l2 '(this or that))
(define l3 '(this and (this and that)))
(define l4 '(this or (this or that)))
(define l5 '(that or (that or that)))

; template
;
; (define (replace x y l)
;    (cond (() ...)
;          (() ... (car l) (replace x y (cdr l)))
;          (else ... (replace x y (car l)) (replace x y (cdr l)))))

(define (replace x y l)
  (cond ((null? l) '())
	((symbol? (car l)) (if (eq? x (car l))
			       (cons y (replace x y (cdr l)))
			       (cons (car l) (replace x y (cdr l)))))
	(else (cons (replace x y (car l)) (replace x y (cdr l))))))

; checking expectations

(and
 (equal? (replace 'this 'that '()) '())
 (equal? (replace 'and 'or l1) l2)
 (equal? (replace 'and 'or l3) l4)
 (equal? (replace 'this 'that l4) l5))

; happy happy! joy joy!

Last modified 7 years ago Last modified on Jul 18, 2013, 12:24:50 PM
Note: See TracWiki for help on using the wiki.