;;; ;;; listprocs.ss ;;; UVA CS200 Spring 2004 ;;; ;;; This file contains some useful procedures we have defined for lists. ;;; 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)) (if (= num 1) (car lst) (get-nth (cdr lst) (- num 1)))) (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)))))