How can I recursively iterate and compare values of a single list in scheme?

Question

I have a single list, and I need to compare every value to every other value until I either reach the end of the list or find a pair of numbers that sum to 0. I'm also limited on what constructs I can use (null?, car, cdr, cons, else). I can't use a nested COND or any variables. I'm at a loss for how to proceed.

I can recursively iterate through the whole list with cdr, but it is only comparing adjacent numbers in the list. For example, my test list should be true because of 5-5=0, but I can't figure out how to get the algorithm to compare the 5 and -5 because car changes every time I iterate.

So far I have:

(define add (lambda (lst)
(cond
;Null check
  ((null? (cdr lst)) #f)
;Adds car and car of cdr to check for 0.
  ((= 0 (+ (car lst) (car(cdr lst)))) #t)
;Recursive portion
  ((car lst) (sum (cdr lst)))  **Not having any luck with this part.
  )))

(sum '(5 6 -5))

Answer 1

Using An Accumulator to Store Checked Elements

One solution would be to write a helper function that takes three arguments: a candidate value to check, a list to check against, and a list of previously checked values. The main function would call the helper function after checking that there are at least two values in the input list to start with.

If the list to check against is empty and there is only one checked value remaining in the list of checked values, there were no zero-sum pairs.

Otherwise, if the list to check against is empty, the candidate value did not sum to zero with any other values, so it can be discarded and the first value from the list of previously checked values can be checked against the rest of that list.

Otherwise, if the sum of the candidate value and the first element of list of values to check against is zero, then a zero-sum pair has been found.

Otherwise, the first element of the list of values to check against did not sum to zero with the candidate, so it can be moved to the list of checked values and the candidate can be checked against the remainder of the list to be checked.

Here is a solution written in Common Lisp. You will have to do a little bit of work to convert it to Scheme, but this shouldn't be much trouble since it is already in a pretty Schemey style. Some minor modifications may be needed to get exactly the behavior desired for your assignment, but I think that the principles used are clear.

(defun zero-summands-helper (candidate xs checked)
  (cond ((and (null xs) (null (cdr checked))) '())
        ((null xs)
         (zero-summands-helper (car checked) (cdr checked) '()))
        ((zerop (+ candidate (car xs)))
         (cons candidate (car xs)))
        (t
         (zero-summands-helper candidate (cdr xs) (cons (car xs) checked)))))

(defun zero-summands (xs)
  (cond ((null xs) '())
        ((null (cdr xs)) '())
        (t
         (zero-summands-helper (car xs) (cdr xs) '()))))

Here are some example interactions:

CL-USER> (zero-summands '(-1 1))
(-1 . 1)
CL-USER> (zero-summands '(1 1))
NIL
CL-USER> (zero-summands '(5 6 -5))
(5 . -5)
CL-USER> (zero-summands '(1 2 3 4 -2 5 6))
(2 . -2)

Common Lisp has a trace feature that is useful for looking at recursive calls. Here zero-summands-helper is traced, which might be helpful for understanding how the above solution works:

CL-USER> (trace zero-summands-helper)
(ZERO-SUMMANDS-HELPER)
CL-USER> (zero-summands '(-1 1))
  0: (ZERO-SUMMANDS-HELPER -1 (1) NIL)
  0: ZERO-SUMMANDS-HELPER returned (-1 . 1)
(-1 . 1)
CL-USER> (zero-summands '(5 6 -5))
  0: (ZERO-SUMMANDS-HELPER 5 (6 -5) NIL)
    1: (ZERO-SUMMANDS-HELPER 5 (-5) (6))
    1: ZERO-SUMMANDS-HELPER returned (5 . -5)
  0: ZERO-SUMMANDS-HELPER returned (5 . -5)
(5 . -5)
CL-USER> (zero-summands '(1 2 3 -2))
  0: (ZERO-SUMMANDS-HELPER 1 (2 3 -2) NIL)
    1: (ZERO-SUMMANDS-HELPER 1 (3 -2) (2))
      2: (ZERO-SUMMANDS-HELPER 1 (-2) (3 2))
        3: (ZERO-SUMMANDS-HELPER 1 NIL (-2 3 2))
          4: (ZERO-SUMMANDS-HELPER -2 (3 2) NIL)
            5: (ZERO-SUMMANDS-HELPER -2 (2) (3))
            5: ZERO-SUMMANDS-HELPER returned (-2 . 2)
          4: ZERO-SUMMANDS-HELPER returned (-2 . 2)
        3: ZERO-SUMMANDS-HELPER returned (-2 . 2)
      2: ZERO-SUMMANDS-HELPER returned (-2 . 2)
    1: ZERO-SUMMANDS-HELPER returned (-2 . 2)
  0: ZERO-SUMMANDS-HELPER returned (-2 . 2)
(-2 . 2)

Using A Helper Function to Check The First Element

Another approach would be to write a helper function that checks to see if the first element of the input list has an additive inverse in the remainder of the list.

The main function would only call the helper function if the input list contains at least two elements. Then the main function would call the helper function with the first element and the rest of the list, iterate over that list, and return either a pair or the empty list. If a pair is returned, we are done and the pair can be returned up the call stack. Otherwise the first element of the input had no additive inverse in the rest of the list, so the main function can be called on the cdr of the input list, checking again if there are at least two elements left and then checking for additive inverses against the first element of the reduced list.

;;; Returns a pair containing X and a member of XS summing to 0 if one exists,
;;; NIL otherwise.
(defun first-zero-summand (x xs)
  (cond ((null xs) '())
        ((zerop (+ x (car xs))) (cons x (car xs)))
        (t
         (first-zero-summand x (cdr xs)))))

;;; Returns a pair of elements of XS containing the first element which has
;;; an additive inverse together with its inverse if such a pair exists,
;;; or NIL otherwise.
(defun some-zero-summand (xs)
  (if (or (null xs) (null (cdr xs)))
      '()
      (or (first-zero-summand (car xs) (cdr xs))
          (some-zero-summand (cdr xs)))))

Sample interaction:

CL-USER> (some-zero-summand '(5 6 -5))
(5 . -5)