;; 6.891 Problem Set 1 -- Nelson Elhage
;;
;; util.scm -- some generic utility functions not necessarily specific
;; to this problem set


;;Return the index of a given value in a list, using eqv? to determine
;;equality, or #f if it is not found
(define (search-list list value)
  (define (iter list index)
    (cond ((null? list) #f)
          ((eqv? value (car list)) index)
          (else (iter (cdr list) (1+ index)))))
  (iter list 0))

#|
Example:

(search-list '(1 2 3) 2)

;Value: 1
|#

;;Merge two lists that are sorted according to predicate?
;;If an element is in both lists, call merge with both values
;;and use the result
(define (merge-lists l1 l2 #!optional predicate? merge)
  (if (default-object? predicate?) (set! predicate? <))
  (if (default-object? merge) (set! merge (lambda (a b) a)))
  (cond ((null? l1) l2)
        ((null? l2) l1)
        (else
         (let ((first-l1 (car l1))
               (first-l2 (car l2)))
           (cond ((predicate? first-l1 first-l2)
                  (cons first-l1 (merge-lists (cdr l1) l2 predicate? merge)))
                 ((predicate? first-l2 first-l1)
                  (cons first-l2 (merge-lists l1 (cdr l2) predicate? merge)))
                 (else
                  (cons (merge first-l1 first-l2)
                        (merge-lists (cdr l1) (cdr l2) predicate? merge))))))))

#|
Example:

(merge-lists '(1 2 4 7 9) '(2 3 5 7 8) < cons)

;Value: (1 (2 . 2) 3 4 5 (7 . 7) 8 9)
|#