Scheme Question - How can I check if there are a list of pairs

Question

So I need to write code on scheme that checks if there is a list of pairs? Any ideas on where to get started?

  (define (list-of-pairs? lst)
    (if (null? lst)
        #f
        (if (pair? (cdr lst))
            #t
            (list-of-pairs? (cddr lst)))))

and I have no idea where to go from here if that is even correct

I know this is wrong as I get this error

list-of-pairs?: arity mismatch; the expected number of arguments does not match the given number expected: 1 given: 4 arguments...:

when i input this

(list-of pairs?
   (list
   (cons 1 (cons 2 empty))
   (cons 2 (cons null empty))
   (cons 3 (cons 4 (list 4 5 6))))

Answer 1

"I know this is wrong as I get this error." This arity mismatch error has nothing to do with the posted code. Rather, it seems that OP has experienced the result of some typo in testing the defined procedure. The posted test contains at least two typos: list-of pairs? is missing a hyphen, and the entire expression is missing a closing parenth; this leads me to believe that OP has typed the expression into the body of the question instead of copy-pasting. If this were the actual testing expression the error would probably be more along the lines of list-of undefined; cannot reference an identifier before its definition.

As a side note, this code contains empty and null which are not defined in Standard Scheme; it looks like OP is actually writing Racket, but this doesn't substantially change the answer to OP's question.

Problems With the Posted Code

The OP definition for list-of-pairs? is incorrect. To see why, let's look at a few input examples:

> (list-of-pairs? '())
#f
> (list-of-pairs? '(1))
cddr: contract violation
  expected: (cons/c any/c pair?)
  given: '(1)
 [,bt for context]
> (list-of-pairs? '(1 2))
#t

To start, when the input is the empty list, OP's procedure returns #f. Ordinarily I would expect this case to yield #t, since an empty list is an empty list of pairs, and of any other type you could think of. By itself this isn't a deal breaker, and the procedure could be sensibly written to return #f in such cases.

More serious problems become evident for the next two cases. When the input is a list containing a single integer, I would expect the procedure to yield #f, but instead the result is an error. Why? The list (1) is not empty, so the OP procedure goes on to check whether the cdr of (1) is a pair; but the cdr of (1) is (), and (pair? '()) is #f, so finally the OP procedure checks whether the cddr of (1) is a list-of-pairs?. But, (cddr '(1)) is undefined in Scheme (and in Racket). Expanding this call shows: (cddr '(1)) -> (cdr (cdr '(1))) -> (cdr '()) -> error!

Further, when the input is a list of integers the OP procedure unexpectedly returns #t. This can't be right because an integer is not a pair, and a list of integers is surely not a list of pairs. What is happening here? When the input is (1 2) it is not empty, and the cdr of (1 2) is (2), which is in fact a pair because every list is a pair! Specifically, every list is a pair comprised of a car part and a cdr part. So in this case the expression (if (pair? (cdr lst)) ;... returns #t. But we don't want to know if the cdr of the input is a pair; we want to know if the car of the input is a pair (which OP code never checks), and whether the other elements of the list are also pairs.

A fundamental problem here is that the OP procedure is taking its list input apart incorrectly for the needs of the problem.

One Solution

To solve a problem recursively you always need to identify at least two things: what is the base case, and what is the recursive step. The base case is a simple case for which the answer can be immediately found. The recursive step works to reduce the input case towards the base case in some way. Ordinarily you need to combine the results of each recursive call in some way.

Sometimes it is helpful to describe what we want (in this case to describe what constitutes a list-of-pairs?): a list-of-pairs? is an empty list, or a list for which the first element is a pair, and the remainder of the list is a list-of-pairs?.

Here, the base case is when the input is the empty list. In that case, let's say that the result should be #t, that is, an empty list is an empty list of pairs. When the input is a nonempty list, how can it be reduced towards the base case? If the first element of the input is not a pair, we are done because the input is not a list of pairs. But, if the first element is a pair, then we need to combine this knowledge with the knowledge about the rest of the input list. That is, if the car of the input is a pair, and if the rest of the input is a list-of-pairs?, then the input is a list of pairs. Here the list given to recursive calls of list-of-pairs? has been reduced towards the base case by using cdr. Here is that solution:

(define (list-of-pairs? xs)
  (if (null? xs)
      #t
      (and (pair? (car xs))
           (list-of-pairs? (cdr xs)))))

Knowledge of the first element of the input and the status of the remainder of the list is combined using the and operator. When the first element (of any recursive call) is not a pair, #f is returned and combined with any previous #t values to yield #f. Otherwise #t is returned.

If it is desired that the empty list should not be a list of pairs, the above can be adjusted with a bit of thought, but I will leave that as an exercise for the reader.