Remove duplication from the Scheme function

Question

(define (merge-sorted lst1 lst2)
  (cond ((null? lst1) lst2)
        ((null? lst2) lst1)
        ((>= (car lst1) (car lst2))
         (cons (car lst2) (merge-sorted lst1 (cdr lst2))))
        (else
         (cons (car lst1) (merge-sorted (cdr lst1) lst2)))))
Output:

(merge-sorted '(1 3 4) '(2 4 5))
=> '(1 2 3 4 4 5)

I have to write function on lists in Scheme. How can I fix the duplication?

Answer 1

Instead of having >= as one condition, you can test equality separately, whereby whenever (car lst1) is equal to (car lst2), you would keep one of them, but remove both on your recursive call by doing:

(cons (car lst1)
      (merge-sorted (cdr lst1) (cdr lst2)))

For example:

(define (merge-sorted lst1 lst2)
  (cond
    ((null? lst1) lst2)
    ((null? lst2) lst1)
    ((> (car lst1)
        (car lst2))
     (cons (car lst2)
           (merge-sorted lst1 (cdr lst2))))
    ((< (car lst1)
        (car lst2))
     (cons (car lst1)
           (merge-sorted (cdr lst1) lst2)))
    (else
     (cons (car lst1)
           (merge-sorted (cdr lst1) (cdr lst2))))))

then you would have:

(merge-sorted '(1 3 4) '(2 4 5))
=> '(1 2 3 4 5)