Scheme cond getting stuck in a loop

Question

(define (sort list length loop1 loop2 temp)
(cond ((>= loop1 length)
        (list))
     ((< loop1 length)
        (cond ((>= loop2 length)
                (set! loop1 (+ loop1 1))
                (set! loop2 (+ loop1 1)))
            ((< loop2 length)
                (cond ((> (list-ref list loop1) (list-ref list loop2)))
                    (set-car! temp (list-ref list loop1))
                    (list-set! list loop1 (list-ref list loop2))
                    (list-set! list loop2 temp)
                    (set-car! temp '())
                )
                (set! loop2 (+ loop2 1))
            )
        )
        (sort list length loop1 loop2 temp))
)

)

Hello, this is a scheme recursive function of a tail recursive function. There seems to be a problem with the cond part because it starts to get stuck in a loop. There's probably a syntax error cause the line of codes seemed to work individually when I tried it in the terminal.

Answer 1

I'm going to reformulate your function a little bit, based on two insights:

1. Scheme lists are not random-access, so using list indices is not a good way to go. (In particular, list-ref and list-set! are both O(n) operations.)
2. Using extensive mutation is not very Schemey either. In fact, some implementations, like Racket, have immutable lists.

Here's how I might rewrite the function using the same algorithm (note that your sort is not easy to implement without mutation (in contrast, you can implement mergesort without any mutation), so my version still has some mutation, but not as much as yours ;-)):

(define (sort! lst)
  (let outer ((lhs lst))
    (unless (null? lhs)
      (let inner ((rhs (cdr lhs)))
        (if (null? rhs)
            (outer (cdr lhs))
            (let ((a (car lhs))
                  (b (car rhs)))
              (when (> a b)
                (set-car! lhs b)
                (set-car! rhs a))
              (inner (cdr rhs))))))))

Note that using this inner/outer loop structure is cleaner than the cond you had, so my version doesn't use cond at all.

Example usage (tested on Guile):

> (define lst (list 3 1 4 1 5 9))   ; important: **not** '(3 1 4 1 5 9)
> (sort! lst)
> lst
(1 1 3 4 5 9)

---

If you want to use a random-access data structure, that's called vector in Scheme. Here's the same algorithm for vectors:

(define (sort! vec)
  (let outer ((i 0))
    (unless (>= i (vector-length vec))
      (let inner ((j (+ i 1)))
        (if (>= j (vector-length vec))
            (outer (+ i 1))
            (let ((a (vector-ref vec i))
                  (b (vector-ref vec j)))
              (when (> a b)
                (vector-set! vec i b)
                (vector-set! vec j a))
              (inner (+ j 1))))))))

Note that I use i and j for the left-hand and right-hand vector indices, instead of the lhs and rhs left-hand and right-hand "cursors" that I used for the list version.

Example usage (tested on Racket):

> (define vec (vector 3 1 4 1 5 9))
> (sort! vec)
> vec
#(1 1 3 4 5 9)