Sorting algorithm lisp-scheme

Question

I have decided to learn some functional language and I hooked up with the lisp-scheme after all.

I am trying to make a function which checks if a list is sorted, either with lowest first getting higher or vice versa, and if it can be sorted it should return true else false.

This is my first code, working only if the list is increasing (or equal).

    (define sorted?
     (lambda (lst)
      (cond ((empty? lst) #t)
            (else (and (<= (car lst) (cadr lst))
                  (sorted? (cdr lst)))))))

clarification: something like (sorted? '(1 2 3 4 5)) and (sorted? '(5 4 3 2 1)) should return true, else if not sorted false of course.

How am I supposed to think when programming in a functional style? The syntax seems straight-forward but I'm not used to the logic.

Answer 1

Specific implementation

I'd take Óscar López's answer and go one step further:

(define sorted? (lambda (lst)
  (letrec ((sorted-cmp 
            (lambda (lst cmp)
              (cond ((or (empty? lst) (empty? (cdr lst)))
                     #t)
                    (else (and (cmp (car lst) (cadr lst))
                               (sorted-cmp (cdr lst) cmp)))))))
    (or (sorted-cmp lst <=) (sorted-cmp lst >=)))))

The biggest difference between this version and his is that sorted? now defines Óscar's version as an internal helper function using letrec and calls it both ways.

Functional Thinking

You actually chose a good example for illustrating some aspects of how Scheme views the world, and your implementation was off to a very good start.

One important functional principle involved in the solution to this problem is that anything you could put (**here** more stuff '(1 2 3 4)), you can pass around as an argument to another function. That is, functions are first class in a functional programming language. So the fact that you were using <= in your comparison means that you can pass <= as a parameter to another function that makes a comparison accordingly. Óscar's answer is a great illustration of that point.

Another aspect of this problem that embodies another common functional pattern is a function that consists primarily of a (cond) block. In many functional programming languages (Haskell, ML, OCaml, F#, Mathematica), you get stronger pattern matching abilities than you get, by default in Scheme. So with (cond) in Scheme, you have to describe how to test for the pattern that you seek, but that's usually fairly straightforward (for example the (or (empty? lst) (empty? (cdr lst))) in this implementation.

One final functional programming pattern that I see as well-embodied in this problem is that many functional programming solutions are recursive. Recursion is why I had to use letrec instead of plain ol' let.

Almost anything you can do by operating on the first element (or 2 elements as in this case) and then repeating the operation on the tail (cdr) of the list you do that way. Imperative for- or while-style loops aren't impossible in Scheme (although they are pretty much impossible in pure functional languages such as Haskell), they're slightly out of place in Scheme under many circumstances. But Scheme's flexibility that allows you, as the developer, to make that decision enables important performance or maintainability optimizations in certain circumstances.

Continuing exploration

My first implementation of sorted? for my answer here was going to decide which comparison operator to pass to sorted-cmp based on what it saw in the list. I backed off on that when I spotted that a list could start with two equal numbers '(1 1 2 3 4 5). But as I think more about it, there's definitely a way to track whether you've decided a direction yet and, thus, only have one call required to sorted-cmp. You might consider exploring that next.