Some exercises. These assume map is provided by your version of Scheme (otherwise you'll have to implement it yourself, see ex. 1 of the next section).
1. Implement a tree-map which works like map, but on trees instead of lists:
> (tree-map square '((1 2) (3 (4 5))))(tree-map square '((1 4) (9 (16 25))))
2. Implement (filter pred lst) which given a predicate (unary function returning true or false) and a list, will return a new list of all items for which the predicate returns true. Order must be maintained:
> (filter odd? '(1 2 3 4 5))(1 3 5)
3. Implement this filter function using map.
Hint:
(apply func '(x y z)) ==== (func x y z)
Second hint: append
4. Write an (index lst) function using map:
> (index '(a b c))((0 . a) (1 . b) (2 . c))
Note: this is in my opinion a very ugly way of solving this problem.
5. Write an (unordered-pairs lst) function:
> (unordered-pairs '(1 2 3 4))((3 . 4) (2 . 3) (2 . 4) (1 . 2) (1 . 3) (1 . 4))
Order is not important.
6. Write a (combinations lst) function which returns a list of all possible subsets (= list where order is not important, (1 2) = (2 1)):
> (combinations '(1 2 3))(() (3) (2) (2 3) (1) (1 3) (1 2) (1 2 3))
Order is not important, so
> (combinations '(1 2 3))(() (3) (2) (3 2) (3 1) (2 1) (2 1 3) (1))
is also acceptable.
; 1(define (tree-map func x) (if (list? x) (map (lambda (x) (tree-map func x)) x) (func x))); 2(define (filter pred lst) (cond ((null? lst) ()) ((pred (car lst)) (cons (car lst) (filter pred (cdr lst)))) (else (filter pred (cdr lst))))); 3(define (filter pred lst) (apply append (map (lambda (x) (if (pred x) (list x) ())) lst))); 4(define (index lst) (map (let ((counter -1)) (lambda (x) (set! counter (+ 1 counter)) (cons counter x))) lst)); 5(define (unordered-pairs lst) (if (null? lst) () (append (unordered-pairs (cdr lst)) (map (lambda (x) (cons (car lst) x)) (cdr lst))))); 6(define (combinations lst) (if (null? lst) '(()) (let ((combs (combinations (cdr lst)))) (append combs (map (lambda (x) (cons (car lst) x)) combs)))))
Solve these without the help of any library functions.
1. Implement a (map func lst) function.
2. Implement a (fold-left func init lst) function.
3. Implement a (fold-right func lst init) function.
4. Implement map in terms of fold-left.
5. Implement map in terms of fold-right.
6. Implement (filter pred lst) using one of the folds.
7. Implement (partition pred lst) which separates elements into two lists depending on whether pred returns true or false. Use one of the folds.
> (car (partition odd? '(1 2 3 4 5)))(1 3 5)> (cdr (partition odd? '(1 2 3 4 5)))(2 4)
8. Implement (literal->value digits radix) which works on strings and converts a literal in any radix (up to 36, digits "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ") to a numeric value. No error checking necessary.
Hint: string->list, char->integer, char<?.
> (literal->value "1001" 2)9> (literal->value "F000" 16)61440
9. Implement (run-length-encode lst) (use fold) which groups equal consecutive elements with the sequence length into cons-cells as follows:
> (run-length-encode '(a a a b c c))((a . 3) (b . 1) (c . 2))
10. Implement (run-length-decode lst) which does the inverse of run-length-encode:
> (run-length-decode (run-length-encode '(a a a b c c)))(a a a b c c)
; 1(define (map func lst) (if (null? lst) () (cons (func (car lst)) (map func (cdr lst))))); 2(define (fold-left func init lst) (if (null? lst) init (fold-left func (func init (car lst)) (cdr lst)))); 3(define (fold-right func lst init) (define (fold-right lst init) (if (null? lst) init (fold-right (cdr lst) (func (car lst) init)))) (fold-right (reverse lst) init)); 4(define (map func lst) (fold-left (lambda (acc x) (append acc (list (func x)))) () lst)); 5; Note: the order in which the elements are computed is reversed(define (map func lst) (fold-right (lambda (x acc) (cons (func x) acc)) lst ())); 6(define (filter pred lst) (reverse (fold-left (lambda (acc x) (if (pred x) (cons x acc) acc)) () lst))); 7(define (partition pred lst) (fold-right (lambda (x p) (let ((yes (car p)) (no (cdr p))) (if (pred x) (cons (cons x yes) no) (cons yes (cons x no))))) lst '(() . ()))); 8(define (literal->value literal radix) (fold-left (lambda (total x) (+ (* total radix) x)) 0 (map (lambda (char) (if (char<? char #\A) (- (char->integer char) (char->integer #\0)) (+ (char->integer char) 10 (- (char->integer #\A))))) (string->list literal)))); 9(define (run-length-encode lst) (reverse (fold-left (lambda (acc x) (if (or (null? acc) (not (eq? (caar acc) x))) (cons (cons x 1) acc) (cons (cons x (+ 1 (cdar acc))) (cdr acc)))) () lst))); 10(define (run-length-decode lst) (define (repeat x n) (if (= n 0) () (cons x (repeat x (- n 1))))) (fold-left (lambda (acc x) (append acc (repeat (car x) (cdr x)))) () lst))
[Edited by - SamLowry on May 9, 2007 7:14:29 PM]