How to write your own "list?" procedure in Scheme

Question

I am trying to write my own 'list?' predicate in scheme. I know that definition of a list: 1. en empty list 2. pair, whose cdr is a pair

I know my code is wrong because it is returning true value on every pair, but every pair is not a list. I do not know how to implement the condition that cdr of the list must be also a pair.

(define (my-list? x)
  (if (equal? x ()) #t
      (pair? x)))

"2. pair, whose cdr is a pair" is wrong. I should be "2. paor, whose cdr is a list?" Your example didn't check the cdr so you need to do that when argument is a pair. — Sylwester

Óscar López Óscar López · Accepted Answer · 2019-02-02T14:45:30

The list? procedure checks if a list is proper (nested cons-cells ending in a null value), hence we have to consider three cases:

(define (my-list? x)
  (cond ((null? x) #t)                 ; empty list
        ((pair? x) (my-list? (cdr x))) ; pair, advance recursion
        (else #f)))                    ; atom

A null value is considered an empty list. If we're in a pair, then we advance on its cdr by calling the procedure recursively. If it's not null nor a pair, it's an atom. This will cover edge cases, such as this:

(my-list? 42)
=> #f
(my-list? (cons 1 2))
=> #f

And will return true for proper lists:

(my-list? '())
=> #t
(my-list? (cons 1 (cons 2 '())))
=> #t

How to write your own "list?" procedure in Scheme

1 Answers