2

This function is supposed to return #t if the list e is incrementally ordered. The function doesn't work and I can't fix it.

(define (ordered e)
  (if (or (null? e) (> length(e) 1))
      #t
      (if (> (car e) (cadr e))
          #f
          (ordered (cdr e)))))
Sam Tobin-Hochstadt
  • 4,983
  • 1
  • 21
  • 43
Lara
  • 43
  • 4
  • Dan has given the reason why your program fails. In order to find such an error the stepper in DrRacket is a useful tool to know. See http://stackoverflow.com/questions/10499514/y-combinator-discussion-in-the-little-schemer/10500358#10500358 – soegaard May 25 '12 at 15:14
  • 2
    The function could also be written as `(define (ordered e) (apply > e))`. – Dan D. May 25 '12 at 16:17

1 Answers1

1

The base case is in the question is wrong, it's easier (and less error-prone) to simply state that a list is ordered if it has less than two elements. That's what was causing problems in your code, because the base case is ill-defined, your procedure enters in the second case when it shouldn't. When the list has less than two elements, you can't use cadr. To fix your implementation do this:

(define (ordered e) 
  (if (< (length e) 2)
      #t 
      (if (> (car e) (cadr e))
          #f 
          (ordered (cdr e)))))

You can express the solution to this problem more concisely by using cond, and you can avoid using length (which depending on the implementation could be an O(n) operation) like this:

(define (ordered e)
  (cond ((or (null? e) (null? (cdr e))) #t)
        ((> (car e) (cadr e)) #f)
        (else (ordered (cdr e)))))
Óscar López
  • 232,561
  • 37
  • 312
  • 386
  • @Lara I updated my answer with more details and with a correct implementation of the code in your question, take a look – Óscar López May 26 '12 at 00:14