Substituting for elements that satisfy a predicate

; subst-by-pred
; takes a list and Scheme value, substitutes that value for  
;  elements that satisfy a predicate
(define (subst-by-pred lst new)
  (cond
    [(null? lst) null]
    [(pred? (car lst))
       (cons new (subst-by-pred (cdr lst) new))]
    [else
       (cons (car lst)
             (subst-by-pred (cdr lst) new)]))

Example (again, pred? is number?):

(subst '(cat dog 42 hamster 57 raven) 'Paris) => 
  (cat dog Paris hamster Paris raven)

Note that pred? could be something like

  (define (a-or-b? x)
    (or (eq? x 'a)
        (eq? x 'b))

allowing us to substitute for particular elements. Some commonly-used Scheme predicates include

 null?
 pair?
 symbol?
 string?
 vector?
 char?
 number?
 zero?
 eq?
 equal?

The predicates eq? and equal? are binary, that is, they take two arguments. The others listed here are unary -- they take a single argument. Does it make sense to have a nullary predicate?
The null? and pair? predicates can be used to test whether a Scheme value is a list. When applied to the empty list, null? returns #t. When applied to a non-empty list, pair? returns #t. There is also a unary predicate list?, but it's rarely a good idea to use it. Why? (Pedagogical note: you will receive no credit for any assignment problem or exam answer in which you use list?.)

Both eq? and equal? are used to test the equality of their arguments, but in slightly different ways. The eq? predicate tests the intensional equality of its arguments. Succinctly stated, that means eq? returns #t when its arguments denote the same Scheme object. There's some subtlety in that notion:

 (eq? 42 42) => #t
 (eq? 'foo 'foo) => #t
 (eq? "bar" "bar") => #f
 (eq? '(a b c) '(a b c)) => #f
 
 (define x '(a b c))
 (define y x)
 (eq? x y) => #t

On the other hand, the equal? predicate tests for structural equality. So using it in the above examples would yield #t in each case. Both eq? and equal? are useful when testing programs.

Inserting before first element satisfying a predicate

; insert-left-one-by-pred 
; takes a list and a Scheme value, inserts value before
;  first element satisfying a predicate
(define (insert-left-one-by-pred lst new)
  (cond
    [(null? lst) null]
    [(pred? (car lst))
       (cons new lst)]
    [else
       (cons (car lst)
             (insert-left-one-by-pred (cdr lst) new))]))

What does this procedure return if no element satisfies the predicate?

Example (assuming pred? is number?):

(insert-left-one-by-pred '(cat dog 42 hamster 57 raven)) 'Paris => 
  (cat dog Paris 42 hamster 57 raven))

Inserting before all elements satisfying a predicate

; insert-left-by-pred
; takes a list and a Scheme value, inserts that value
;  before all elements satisfying a predicate 
(define (insert-left-by-pred lst new)
  (cond
    [(null? lst) null]
    [(pred? (car lst))
       (cons new 
             (cons (car lst)
                   (insert-left-by-pred (cdr lst) new)))]
    [else
       (cons (car lst)
             (insert-left-by-pred (cdr lst) new))]))

Inserting after first element satisfying a predicate

; insert-right-one-by-pred
; takes a list and a Scheme value, inserts that value
;  after the first element satisfying a predicate
(define (insert-right-one-by-pred lst new)
  (cond
    [(null? lst) null]
    [(pred? (car lst))
       (cons (car lst)
             (cons new
                   (cdr lst)))]
    [else
       (cons (car lst)
             (insert-right-one-by-pred (cdr lst) new))]))