;;; ;;; listprocs.ss ;;; UVA CS200 Spring 2003 ;;; ;;; This file contains some useful procedures we have defined for lists. ;;; We use assert to check properties that must be true. If an assertion fails, ;;; it probably means there is a bug in your code. (define (assert pred msg) (if (not pred) (error "Assertion failed: " msg))) ;;; get-nth evaluates to the nth element in the list (where the first element is element 1) (define (get-nth lst num) (assert (> num 0) "get-nth: index out of range") (if (= num 1) (car lst) (get-nth (cdr lst) (- num 1)))) (define (get-last lst) (get-nth lst (length lst))) (define (find-element-number lst el) (if (null? lst) (error "Element not found: " el) (if (eq? (car lst) el) 1 (+ 1 (find-element-number (cdr lst) el))))) (define (insertl f lst start) (if (null? lst) start (f (car lst) (insertl f (cdr lst) start)))) (define (filter f lst) (insertl (lambda (el rest) (if (f el) (cons el rest) rest)) lst null)) (define (quicksort cf lst) (if (null? lst) lst (append (quicksort cf (filter (lambda (el) (cf el (car lst))) (cdr lst))) (list (car lst)) (quicksort cf (filter (lambda (el) (not (cf el (car lst)))) (cdr lst)))))) (define (revintsto n) (if (= n 0) null (cons n (revintsto (- n 1))))) (define (intsto n) (reverse (revintsto n))) ;;; Evaluates to the list parameter with the first instance of el removed. ;;; If there is no instance of el, does nothing. (define (delete lst el) (if (null? lst) null ;; okay to not find it now: (error "Element not found!") (if (eqv? (car lst) el) (cdr lst) (cons (car lst) (delete (cdr lst) el))))) ;;; ;;; member? evaluates to true if thing is in list (could use memq for this) ;;; (define (member? thing lst) (if (null? lst) #f (if (eq? thing (car lst)) #t (member? thing (cdr lst)))))