CODEWITHSUNDEEP
functional-programminglisprackettyped-racket
testomg
testomg

Reputation: 45

check if list of integers is ascending

I am trying to write a function to check if a list of integers is strictly ascending or not. I have the following:

(: ascending : (Listof Integer) -> Boolean)
;; test whether a list of integers is *strictly* ascending
(define (ascending x)
  (match x
    ('() #f)
    ((cons hd tl)
     (cond
       ((< hd (second x)) #t)
       ((> hd (second x)) #f)
       (else (ascending tl))))))

It works for the first three checks but not the last three as given below:

(check-expect (ascending (list 1 2 3 4 5)) #t)
(check-expect (ascending (list 5 4 3 2 1)) #f)
(check-expect (ascending (list 5 1 2 3 4)) #f)
(check-expect (ascending (list 1 2 3 5 4)) #f)
(check-expect (ascending (list 1 3 2 4 5)) #f)
(check-expect (ascending (list 1 2 3 4 1)) #f)

I don't understand what I am doing wrong because I have to do the following:

  1. Check if the list is empty and raise an error. Done. Tick.
  2. If the there are only two elements on the list, compare hd and tl and if hd < tl then #t, if not then #f. Done Tick.
  3. Other do the two comparison for all entire list until you have a value #t or #f.

Please help.

Upvotes: 1

Views: 422

Answers (5)

rnso
rnso

Reputation: 24593

One can also use iterative for loop with set!, though this is not normally preferred: 

(define (asc? l)
  (define res #t)
  (for ((i (sub1 (length l)))
        #:when (not(< (list-ref l i)
                      (list-ref l (add1 i)))))
    (set! res #f)
    )
  res)

Testing: 

(asc? (list 1 2 3 4 5))

(asc? (list 1 2 3 4 5 4))

Output:

#t
#f

Upvotes: 0

Mulan
Mulan

Reputation: 135367

If you're allowed to use pattern matching to solve this, you can use more sophisticated patterns to break your problem down into separate parts.

(: ascending? : (Listof Integer) -> Boolean :)
(define (ascending? xs)
  (match xs
    [(list)           #f] ;; empty list is not considered ascending
    [(list a)         #t] ;; single-element list is always ascending
    ;; match first two elements (a, b) and remaining elements as c
    ;; a should be less than b, and recurse
    [(list a b c ...) (and (< a b) (ascending? (cons b c)))]))

To me, this read a lot better than the '() or (cons ...) style matches. And because we used a more expressive pattern in the third case, it keeps the code that actually does stuff really simple.

(ascending? '())               ;; => #f
(ascending? '(1))              ;; => #t
(ascending? '(1 2))            ;; => #t
(ascending? '(1 2 3 4 5 6 7))  ;; => #t
(ascending? '(1 2 3 1))        ;; => #f

I should mention, there's nothing wrong with the other style of patterns you were using. I just think its easier to read when the patterns are consistent. So instead of matching '() with cons and list etc, if you wanted to use the quoted-style of patterns, use them for each case so that it's easier to see which cases you're handling.

This ascending? procedure operates the same, just using a different style of pattern matching expressions

(: ascending? : (Listof Integer) -> Boolean :)
(define (ascending? xs)
  (match xs
    [`()               #f]
    [`(,a)             #t]
    [`(,a . (,b . ,c)) (and (< a b) (ascending? (cons b c)))]))

One more thing: You said ...

Check if the list is empty and raise an error. Done. Tick.

Returning #f isn't raising an error. If you truly intend to raise an error if someone passes in an empty list, then you should use the error procedure

...
(match xs
  [(list) (error 'ascending? "empty list given")]
  ...

Upvotes: 1

ben rudgers
ben rudgers

Reputation: 3669

For me, sometimes it is helpful to stick with the higher level abstractions in the problem description rather than decomposing the problem to fit into a programming pattern such as pattern matching.

Specification

For example a strictly ordered list can be said to have two mathematical properties:

  1. The list is sorted (monotonic).

  2. The list length is equal to the cardinality of the set containing all the list elements.

Implementation

Working from that more mathematical specification:

 #lang typed/racket
 (: strictly-ordered-list? : (Listof Integer) -> Boolean)
 (define (strictly-ordered-list? xs) 
   (define sorted (sort xs <))
     (and (equal? xs sorted)
       (= (set-count (list->set xs))
          (length sorted))))

Discussion

The implementation is written at the abstraction layer we're interested in, lists. It tests the properties of lists and doesn't get bogged down in iterating over and comparing elements. Potentially, it trades a bit of speed, but usually for interesting sized data O(n log n) versus O(n) is not likely to be the bottle neck.

Upvotes: 0

Leo
Leo

Reputation: 1934

Since the function #'< takes any number of arguments, you can simply do:

(apply #'< '(1 2 3 4)) => T

Upvotes: 1

Barmar
Barmar

Reputation: 781834

You have a few problems.

First, you're missing a case for a list with only 1 element, which should be the base case, and return #t. Otherwise, you'll use (second x) on a list with only 1 element, which is an error.

Next, when the list has 2 or more elements, it's ascending if the first element is less than the second element and the tail of the list is also ascending. You're only checking the first two elements. Your else clause only runs when the first and second elements are equal, because the first two cond checks handle < and >. The recursive call isn't a separate case, it's combined with the case where the first two elements are ascending.

(define (ascending x)
  (match x
    ('() #f) ;; Empty list is error
    ((cons hd '()) #t) ;; 1-element is success
    ((cons hd tl)
     (if (< hd (second x))
         (ascending tl)
         #f))))

The if can also be simplified to:

(and (< hd (second x)) (ascending tl))

Upvotes: 2

Related Questions