Copyright ©
2005 Suradet Jitprapaikulsarn
สงวนลิขสิทธิ์ 2548 สุรเดช จิตประไพกุลศาล
Homework 6 (Due Monday June 18, 2005)
For simplicity, we will use the following notation to represent samples
of a list (only for illustration)
{ 7, 9, 4 } = (make-LON 7 (make-LON 9 (make-LON 4 empty)))
- Write a function, concatenate,
to join two list of numbers into one list. For instance, if
your first list is { 2, 4, 6 } and your second list is { 8, 9, 10
}, then the resulting list is { 2, 4, 6, 8, 9, 10 }. Solution
;-----------------
; Data Definition
;-----------------
; A list-of-number (LON) is either
; - an empty list
; or a structure consisting of
; - first as a number
; - rest as a list-of-number (LON)
;------------------------------------------------------------------------------
(define-struct LON (first rest))
;--------------
; Data Example
;--------------
(define list-1 empty)
(define list-2 (make-LON 5 empty))
(define list-3 (make-LON 7 (make-LON 9 (make-LON 5 empty))))
;-------------
; Code Pattern
; ------------
;(define (F a)
; (cond
; [(empty? a) ... ]
; [else ... (LON-first a) ...
; ... (F (LON-rest a)) ... ]))
;******************************************************************************
;------------------------------------------------------------------------------
; @description join two lists of numbers
; @param list_a the first list
; @param list_b the second list
; @return the combined list of list_a and list_b
; @contract concatenate: LON LON -> LON
; @example (concatenate empty empty) = empty
; @example (concatenate empty
;
(make-LON 1 empty)) = (make-LON 1 empty)
; @example (concatenate (make-LON 2 empty)
;
empty)
= (make-LON 2 empty)
; @example (concatenate (make-LON 1 (make-LON 2 empty))
;
(make-LON 5 (make-LON 8 empty)))
; = (make-LON 1 (make-LON 2 (make-LON 5 (make-LON 8 empty))))
;------------------------------------------------------------------------------
(define (concatenate list_a list_b)
(cond
[(empty? list_a) list_b]
[else (make-LON (LON-first list_a)
(concatenate (LON-rest list_a) list_b))]))
;------
; Test
;------
"(concatenate empty empty) = " (concatenate empty empty)
"(concatenate empty (make-LON 1 empty)) = " (concatenate empty (make-LON 1 empty))
"(concatenate (make-LON 2 empty) empty) = " (concatenate (make-LON 2 empty) empty)
"(concatenate (make-LON 1 (make-LON 2 empty)) (make-LON 5 (make-LON 8 empty))) = "
(concatenate (make-LON 1 (make-LON 2 empty)) (make-LON 5 (make-LON 8 empty)))
- Write a function, remove,
to remove all occurrences of a particular symbols from a list of
symbols. For instance, if your list is { 2, 5, 7, 2, 3, 4, 2 }
and you want to remove the number 2, then the resulting list is { 5, 7,
3, 4 }. Solution
;-----------------
; Data Definition
;-----------------
; A list-of-symbol (LOS) is either
; - an empty list
; or a structure consisting of
; - first as a symbol
; - rest as a list-of-symbol (LOS)
;------------------------------------------------------------------------------
(define-struct LOS (first rest))
;--------------
; Data Example
;--------------
(define list-1 empty)
(define list-2 (make-LOS 'A empty))
(define list-3 (make-LOS 'Hello (make-LOS 'Hahaha (make-LOS 'Aha empty))))
;--------------
; Code Pattern
;--------------
;(define (F a)
; (cond
; [(empty? a) ... ]
; [else ... (LOS-first a) ...
; ... (F (LOS-rest a)) ... ]))
;******************************************************************************
;------------------------------------------------------------------------------
; @description remove all occurrences of a particular symbols from
; a list of symbols
; @param to-be-removed a symbol to be removed
; @param L a list of symbols
; @return a list without s
; @contract remove: Symbol LOS -> LOS
; @example (remove 'A empty) = empty
; @example (remove 'A (make-LOS 'A empty)) = empty
; @example (remove 'C (make-LOS 'A empty)) = (make-LOS 'A empty)
; @example (remove 'B (make-LOS 'A (make-LOS 'B (make-LOS 'B empty))))
; = (make-LOS 'A empty)
;------------------------------------------------------------------------------
(define (remove to-be-removed L)
(cond
[(empty? L) empty]
[(eq? to-be-removed (LOS-first L)) (remove to-be-removed (LOS-rest L))]
[else (make-LOS (LOS-first L)
(remove to-be-removed (LOS-rest L)))]))
; Test
;------
"(remove 'A empty) = " (remove 'A empty)
"(remove 'A (make-LOS 'A empty)) = " (remove 'A (make-LOS 'A empty))
"(remove 'C (make-LOS 'A empty)) = " (remove 'C (make-LOS 'A empty))
"(remove 'B (make-LOS 'A (make-LOS 'B (make-LOS 'B empty)))) = "
(remove 'B (make-LOS 'A (make-LOS 'B (make-LOS 'B empty))))
- Write a function, inList,
to check whether a particular student is in a list of student records. Solution
;-----------------
; Data Definition
;-----------------
; A student record (SR) is a structure consisting of
; - firstName as symbol
; - lastName as symbol
; - id as number
;------------------------------------------------------------------------------
(define-struct SR (firstName lastName id))
;--------------
; Data Example
;--------------
(define Tom (make-SR 'Tom 'Cruise 12345))
(define Brad (make-SR 'Brad 'Pitt 78901))
(define Val (make-SR 'Val 'Kilmer 67890))
;--------------
; Code Pattern
;--------------
;(define (F a)
; (cond
; [(empty? a) ... ]
; [else ... (SR-firstName a) ...
; ... (SR-lastName a) ...
; ... (SR-id a) ... ]))
;******************************************************************************
;-----------------
; Data Definition
;-----------------
; A list-of-student-record (LOSR) is either
; - an empty list
; or a structure consisting of
; - first as student record
; - rest as list-of-student-record (LOSR)
;------------------------------------------------------------------------------
(define-struct LOSR (first rest))
;--------------
; Data Example
;--------------
(define list-1 empty)
(define list-2 (make-LOSR (make-SR 'Tom 'Cruise 12345) empty))
(define list-3 (make-LOSR (make-SR 'Val 'Kilmer 67890)
(make-LOSR (make-SR 'Brad 'Pitt 78901)
(make-LOSR (make-SR 'Tom 'Cruise 12345) empty))))
;--------------
; Code Pattern
;--------------
;(define (F a)
; (cond
; [(empty? a) ... ]
; [else ... (SR-firstName (LOSR-first a)) ...
; ... (SR-lastName (LOSR-first a)) ...
; ... (SR-id (LOSR-first a)) ...
; ... (F (LOS-rest a)) ... ]))
;******************************************************************************
;------------------------------------------------------------------------------
; @description check if two student records are the same
; @param student_1 the first student
; @param student_2 the second student
; @return true if student_1 has the same first name, last name, and is as
; student_2, false otherwise
; @contract SR-eq?: SR SR -> boolean
; @example (SR-eq? Tom Tom) = true
; @example (SR-eq? Tom Val) = false
; @example (SR-eq? Val Brad) = false
;------------------------------------------------------------------------------
(define (SR-eq? student_1 student_2)
(and (eq? (SR-firstName student_1) (SR-firstName student_2))
(eq? (SR-lastName student_1) (SR-lastName student_2))
(eq? (SR-id student_1) (SR-id student_2))))
;------------------------------------------------------------------------------
; @description check if a particular student is in a list of student records
; @param someone a student record to look for
; @param L a list of student records
; @return true if someone is in L, false otherwise
; @contract inList: SR LOSR -> boolean
; @example (inList Tom empty) = false
; @example (inList Tom list-2) = true
; @example (inList Val list-2) = false
; @example (inList Brad list-3) = true
;------------------------------------------------------------------------------
(define (inList someone L)
(cond
[(empty? L) false]
[(SR-eq? (LOSR-first L) someone) true]
[else (inList someone (LOSR-rest L))]))
;------
; Test
;------
"(SR-eq? Tom Tom) = " (SR-eq? Tom Tom)
"(SR-eq? Tom Val) = " (SR-eq? Tom Val)
"(SR-eq? Val Brad) = " (SR-eq? Val Brad)
"(inList Tom empty) = " (inList Tom empty)
"(inList Tom list-2) = " (inList Tom list-2)
"(inList Val list-2) = " (inList Val list-2)
"(inList Brad list-3) = " (inList Brad list-3)
- Write a function, count,
to count the number of a particular symbol in a list of symbols. Solution
;-----------------
; Data Definition
;-----------------
; A list-of-symbol (LOS) is either
; - an empty list
; or a structure consisting of
; - first as a symbol
; - rest as a list-of-symbol (LOS)
;------------------------------------------------------------------------------
(define-struct LOS (first rest))
;--------------
; Data Example
;--------------
(define list-1 empty)
(define list-2 (make-LOS 'A empty))
(define list-3 (make-LOS 'Hello (make-LOS 'Hahaha (make-LOS 'Aha empty))))
;--------------
; Code Pattern
;--------------
;(define (F a)
; (cond
; [(empty? a) ... ]
; [else ... (LOS-first a) ...
; ... (F (LOS-rest a)) ... ]))
;******************************************************************************
;------------------------------------------------------------------------------
; @description count the number of a particular symbol in a list of symbols
; @param s a symbol to be counted
; @param L a list of symbols
; @return the number of occurrences of s in L
; @contract count: Symbol LOS -> number
; @example (count 'A empty) = 0
; @example (count 'A (make-LOS 'A empty)) = 1
; @example (count 'C (make-LOS 'A empty)) = 0
; @example (count 'B (make-LOS 'A (make-LOS 'B (make-LOS 'B empty)))) = 2
;------------------------------------------------------------------------------
(define (count s L)
(cond
[(empty? L) 0]
[(eq? s (LOS-first L)) (+ 1 (count s (LOS-rest L)))]
[else (count s (LOS-rest L))]))
;------
; Test
;------
"(count 'A empty) = " (count 'A empty)
"(count 'A (make-LOS 'A empty)) = " (count 'A (make-LOS 'A empty))
"(count 'C (make-LOS 'A empty)) = " (count 'C (make-LOS 'A empty))
"(count 'B (make-LOS 'A (make-LOS 'B (make-LOS 'B empty)))) = "
(count 'B (make-LOS 'A (make-LOS 'B (make-LOS 'B empty))))