University of Engineering and Technology Lahore Department of Computer Science and Engineering Programming Fundamentals II Problem Set 5

1

Examples

;gets the nth member of a list. Assume n >= 1 (define takeNth (lambda (n lst) (if (empty? lst) "List too short" (if (= n 1) (car lst) (takeNth (- n 1) (cdr lst)) ))))

;length of a list (define listLength (lambda (lst) (if (empty? lst) 0 (+ 1 (listLength (cdr lst))) )))

;remove the nth member of a list. Assume n >= 1 (define remNthHelper (lambda (n lst index) (if (empty? lst) ’() (if (= n index) (remNthHelper n (cdr lst) (+ index 1)) (cons (car lst) (remNthHelper n (cdr lst) (+ index 1))) ))))

(define removeNth (lambda (n lst) (if (> n (listLength lst)) "Given list too short" 1

(remNthHelper n lst 1) )))

;remove members m through n of a list (define subHelper (lambda (m n lst index) (if (empty? lst) ’() (if (and (= index m)) (subHelper m n (cdr lst) (+ index 1)) (cons (car lst) (subHelper m n (cdr lst) (+ index 1))) )))) (define subList (lambda (m n lst) (if (> n (listLength lst)) "Given list too short" (subHelper m n lst 1) )))

;we can write removeNth using subList (define remove (lambda (n lst) (subList n n lst) ) )

; rotates the list left by 1; (rotateL ’(1 2 3)) -> (2 3 1) (define rotateLHelper (lambda (1st lst) (if (empty? lst) (list 1st) (cons (car lst) (rotateLHelper 1st (cdr lst))) ))) (define rotateL (lambda (lst) (if (empty? lst) lst (rotateLHelper (car lst) (cdr lst)) )))

2

; rotate the list right (define rotateR (lambda (lst) (if (empty? lst) ’() (cons (takeNth (listLength lst) lst) (removeNth (listLength lst) lst))) ) )

2

List manipulation
1. Write the procedure append that combines two lists to form a single list : > (append (list 1 2 3) (list 4 5 6)) (1 2 3 4 5 6) 2. Write the procedure reverse that takes a list as input and reverses it : > (reverse (list 1 2 3)) 321 3. Write the procedure zip that pairs corresponding members of two lists : > (zip (list (list 1 2 3) (list 6 7 8))) ((mcons 1 6) (mcons 2 7) (mcons 3 8)) 4. Write the procedure take which returns the first n values of a list: > (take 2 (list 1 2 3)) (1 2)

3

Procedure on list elements

5. Write a function deepListLength that returns the total number of atomic elements in the list: > (deepListLength (list (cons 1 2) 5 3)) 4 6. Write a function map that takes a list and a function and returns a list with the given function applied to each member of the input list: > (map (lambda (x) (* x x)) (list 1 2 3)) (1 4 9) 7. Write a function filter that takes two inputs, a list of numbers and a predicate function. The output is the list of numbers present in the input list that satisfy the predicate function: 3

> (filter (list 1 2 3 4 5) even?) (2 4) 8. Write a function ascList? that checks if a given list of numbers is in ascending order or not: > (ascList? #t > (ascList? #f (list 1 2 3)) (list 2 10 3))

4

Generating Lists

9. Write a function ascRange which produces a list of numbers in an ascending order. For example: > (ascRange 1 5 1) (1 2 3 4 5) > (ascRange 3 5 0.5) (3 3.5 4.0 4.5 5.0) > (ascRange 3 5.25 0.5) (3 3.5 4.0 4.5 5.0) The general form is (ascRange first last step). 10. Write a procedure absRange that generalizes ascRange and dscRange. When you wrote ascRange and dscRange you must have noticed that the only difference between the two was how you compared the first and last values. In one case you used > and in the other < . The absRange function takes the comparison operator as a function. For example > (absRange 1 5 (/ 1 2) >) 1 1 (1 1 1 2 2 2 3 3 1 4 5 2 5 ) 2 2 > (absRange 5 2 (/ -1 2) (myDefine ’x 9 ’((y 4) (z 6))) ((x 9) (y 4) (z 6)) 4

12. Write a function occurs that takes a list as an argument and outputs a list showing the number of occurences of each element in a list: > (occurs ’(3 a 3 4 5 a b)) ((3 2) (a 2) (4 1) (5 1) (b 1))

5