CODEWITHSUNDEEP
functional-programmingscheme
temporary_user_name
temporary_user_name

Reputation: 37058

How to find whether a sequence is increasing?

It's a fragment of a larger task, but I'm really struggling with this. Resources for scheme/lisp are a lot more limited than C, Java, and Python.

If I pass in a var list1 that contains a list of numbers, how can I tell whether the list is in monotonically increasing order or not?

Upvotes: 2

Views: 161

Answers (3)

C. K. Young
C. K. Young

Reputation: 223003

(define (monotonically-increasing? lst)
  (apply < lst))

Or, if you want monotonically-non-decreasing:

(define (monotonically-non-decreasing? lst)
  (apply <= lst))

Yes, it's really as simple as that. Totally O(n), and no manual recursion required.

Bonus: For good measure:

(define (sum lst)
  (apply + lst))

:-P

Upvotes: 1

&#211;scar L&#243;pez
&#211;scar L&#243;pez

Reputation: 236004

If efficiency is not an issue, you can do this:

(equal? list1 (sort list1 <=))

That's an O(n log n) solution, because of the sorting. For an optimal solution, simply compare each element with the next one and test if the current element is less than or equal to the next one, being careful with the last element (which doesn't have a next element). That'll yield an O(n) solution.

This is the general idea of what needs to be done, written in a functional style. Still not the fastest way to write the solution, but at least it's O(n) and very short; you can use it as a basis for writing a simpler solution from scratch:

(define (increasing? lst)
  (andmap <=
          lst
          (append (cdr lst) '(+inf.0))))

The above checks for each number in lst if it's less than or equal to the next number. The andmap procedure tests if the <= condition holds for all pairs of elements in two lists. The first list is the one passed as a parameter, the second list is the same list, but shifted one position to the right, with the positive infinite value added at the end to preserve the same size in both lists - it works for the last element because any number will be smaller than infinite. For example, with this list:

(increasing? '(1 2 3))

The above procedure call will check that (<= 1 2) and (<= 2 3) and (<= 3 +inf.0), because all conditions evaluate to #t the whole procedure returns #t. If just one of the conditions had failed, the whole procedure would have returned #f.

Upvotes: 0

Doug Currie
Doug Currie

Reputation: 41180

If a list has less than two elements, then we'll say 'yes.'

If a list has two or more elements, then we'll say 'no' if the first is larger than the second, otherwise recurse on the tail of the list.

Upvotes: 3

Related Questions