The objective is given a list of items, remove the last occurrence of a specified item from the list using only user-defined functions except for very basic built-in ones like car, cdr, =, - etc. For example, if we've been given the list (A B A C), using our procedure to remove the last occurrence of A from the list should produce a list (A B C). Hope I'm being clear.
The program itself consists of five procedures:
Four helper procedures:
remove-1st
remove-all-occurrences
member?
size
And the one this fuss is all about:
remove-last-occurrence
By the way, you'll have noticed that all procedures are implemented using tail recursion.
If you're using MIT/GNU Scheme, you can use the built-in procedure "load" like this (load "demo.scm") to load the file into your interactive environment. Here's the code itself:
;;
;; Procedure: remove-1st
;; ---------------------
;; Takes in an item and a list and removes the first occurrence of the item in
;; the list.
;;
;; Usage example:
;; (remove-1st 'A '(B A C A)) => (B C A)
;;
(define remove-1st
(lambda (x ls)
(if (null? ls) ; If an empty list
'() ; Return an empty list
(if (equal? x (car ls)) ; Otherwise, if first item in list
(cdr ls) ; Return rest of list, done
(cons (car ls) (remove-1st x (cdr ls)))))))
; Otherwise, cons first item and
; rest of list with our item removed
;;
;; Procedure: remove-all-occurrences
;; ---------------------------------
;; Takes in an item and a list and removes all top-level occurrences of the
;; item in the list.
;;
;; Usage example:
;; (remove-all-occurrences 'A '(A B A C)) => (B C)
;;
(define remove-all-occurrences
(lambda (x ls)
(if (equal? (remove-1st x ls) ls) ; If list with item removed equals
ls ; itself, return list intact
(remove-all-occurrences x (remove-1st x ls)))))
; Otherwise, remove all occurrences
; of item from list with item
; removed as first occurrence
;;
;; Procedure: member?
;; ------------------
;; This predicate procedure checks whether an item is present in a list. If
;; there is at least one occurrence of the item in the list, a value of true is
;; returned. Otherwise, the procedure returns false.
;;
;; Usage examples:
;; (member? 'A '(A B C)) => #t
;; (member? 'D '(A B C)) => #f
;;
(define member?
(lambda (x ls)
(if (null? ls) ; If an empty list
#f ; Return false
(or (equal? x (car ls)) ; If x is first item in list, done
(member? x (cdr ls)))))) ; Otherwise, check the rest of items
;;
;; Procedure: size
;; ---------------
;; Takes in a list as argument and returns the number of elements it contains.
;;
;; Usage examples:
;; (size '(A B C D)) => 4
;; (size '()) => 0
;;
(define size
(lambda (ls)
(if (null? ls) ; If it's an empty list
0 ; Return zero as its size
(+ 1 (size (cdr ls)))))) ; Otherwise, add one to the size of the
; list minus the first element
;;
;; Procedure: remove-last-occurrence
;; ---------------------------------
;; This procedure removes only the last occurrence of an item in a list.
;;
;; Usage example:
;; (remove-last-occurrence 'A '(B A B A C)) => (B A B C)
;;
;; How it works:
;; First of all, if an empty list has been sent to the procedure, we likewise
;; are going to return an empty list too. Otherwise, we check whether the
;; specified item is in the list and if that comes out as true we're going to
;; check if it's the item's last occurrence in the list by removing all
;; occurrences of it from the list and making a comparison between the number
;; of elements when there are zero occurrences of the item in the list plus one
;; and when they're all there. The sizes being equal means that there is one
;; occurrence of the item in the list. So we now can remove it and return the
;; list. Otherwise, we're going to cons the list's first item and the list
;; produced as the result of removing the last occurrence of the item from the
;; list minus the first element.
;;
(define remove-last-occurrence
(lambda (x ls)
(if (null? ls)
'()
(if (and (member? x ls)
(= (+ (size (remove-all-occurrences x ls)) 1)
(size ls)))
(remove-1st x ls)
(cons (car ls) (remove-last-occurrence x (cdr ls)))))))
;; end of file
)))))))
" I think I just decided I hate scheme... \$\endgroup\$