Writing an alternating series checker in racket

Question

I am trying to make a program which determines if an inputted list alternates in sign. For example, my program would return true if given the list(s): [-1, 5, -10] or [5, -17, 25]. The program would return false if given the list(s): [-1, -5, 6] or [1, -2, -6].

I've tried making a simple cond statement which checks the sign of the first number in the list and then after checks the second number in the list to make sure the first number was positive and the second number was negative or the first number was negative and the second number was positive.

(define (alternating-signs-in-list? lst)
  (cond 
        [(> (first lst) 0)
         (cond [(< (first (rest lst)) 0) (alternating-signs-in-list? (rest lst))])]
        [(< (first lst) 0)
         (cond [(> (first (rest lst)) 0) (alternating-signs-in-list? (rest lst))])]
        [else false]))

I expected the code presented to work but was met with an error stating:

first: expects a non-empty list; given: empty

This error occurred when I made the following check-expect:

(check-expect (alternating-signs-in-list? (cons 1 (cons -5 (cons 50 empty)))) true).

Why is the following error occurring and is there an easy fix I can make to get my code to start working. Thank you.

The main problem with your code is that you forgot the base case(s) of the recursion! You must always check for the empty list case, and sometimes, also for the single-element case. — Óscar López

Óscar López Óscar López · Accepted Answer · 2019-02-11T14:56:15

The trick is to compare pairs of elements at the same time (first and second of the list), until the list is exhausted. The error you're receiving is because you forgot to handle the empty-list case, and for this problem in particular, we also need to handle the case when the list has a single element left.

Before proceeding, it's useful to implement a same-sign? procedure, it's easy if we leverage the sgn procedure (that returns the sign of a number), and if we assume that 0 is positive:

(define (same-sign? n1 n2)
  ; they have the same sign if their `sgn` value is the same
  (= (if (zero? n1) 1 (sgn n1))
     (if (zero? n2) 1 (sgn n2))))

The main procedure goes like this:

(define (alternating-signs-in-list? lst)
  (cond ((or (empty? lst) (empty? (rest lst))) #t) ; empty list / single element case
        ((same-sign? (first lst) (second lst)) #f) ; they are NOT alternating
        (else (alternating-signs-in-list? (rest lst))))) ; advance recursion

Alternatively, we can also write the above using just boolean connectors:

(define (alternating-signs-in-list? lst)
  (or (empty? lst)
      (empty? (rest lst))
      (and (not (same-sign? (first lst) (second lst)))
           (alternating-signs-in-list? (rest lst)))))

Either way, it works as expected:

(alternating-signs-in-list? '(-1 5 -10))
=> #t
(alternating-signs-in-list? '(5 -17 25))
=> #t
(alternating-signs-in-list? '(-1 -5 6))
=> #f
(alternating-signs-in-list? '(1 -2 -6))
=> #f

Writing an alternating series checker in racket

1 Answers