Programming Praxis

The first exercise removes every nth item from a list. We count using variable i and accumulate the result in variable zs in reverse order. A three-legged cond returns when the input is empty, loops without copying at each n item, or loops with copying otherwise:

(define (remove-nth n xs)
  (let loop ((i 1) (xs xs) (zs (list)))
    (cond ((null? xs) (reverse zs))
          ((= i n) (loop 1 (cdr xs) zs))
          (else (loop (+ i 1) (cdr xs) (cons (car xs) zs))))))

Here’s an example:

> (remove-nth 4 '(1 2 3 4 5 6 7 8 9 10)
(1 2 3 5 6 7 9 10)

This function has time complexity linear in the length of the list.

The second exercise removes duplicate items from a list; it has the same three-legged cond as the first exercise, but the predicate in the second leg checks if the current list element is already in the output, in which case it is ignored.

(define (remove-dups xs)
  (let loop ((xs xs) (zs (list)))
    (cond ((null? xs) (reverse zs))
          ((member (car xs) zs) (loop (cdr xs) zs))
          (else (loop (cdr xs) (cons (car xs) zs))))))

Here are some examples:

> (remove-dups '(1 2 3 4 5))
(1 2 3 4 5)
> (remove-dups '(1 1 2 3 4 5))
(1 2 3 4 5)
> (remove-dups '(1 2 3 4 5 5))
(1 2 3 4 5)
> (remove-dups '(1 2 1 3 1 4 1 5 1))
(1 2 3 4 5)
> (remove-dups '(1 2 2 3 3 3 4 4 4 4 5 5 5 5 5))
(1 2 3 4 5)

We stored the already-seen items in the output list, giving the remove-dups function an O(n²) time complexity; that could be reduced to O(n log n) by using some kind of balanced tree to store the set of already-seen items, or even to O(n) by using a hash table (assuming a good hash function), but that’s more work than we want to do here.

The third function splits a list into two halves using the tortoise-and-hare algorithm from computing folklore; the hare pointer races through the list twice as fast as the tortoise pointer, reaching the end of the list when the tortoise reaches the middle.

(define (split xs)
  (let loop ((tortoise xs) (hare xs) (head (list)))
    (if (or (null? hare) (null? (cdr hare)))
        (values (reverse head) tortoise)
        (loop (cdr tortoise) (cddr hare) (cons (car tortoise) head)))))

Here are some examples:

> (split '(1 2 3 4 5 6))
(1 2 3)
(4 5 6)
> (split '(1 2 3 4 5 6 7))
(1 2 3)
(4 5 6 7)

This function runs in linear time.

Our bonus exercise is to write a function that returns a range of integers: (range n) returns a list of integers from 0 to n, excluding n, (range first past) returns a list of integers from first to past, excluding past, and (range first past step) returns a list of integers from first to past in steps of size step, excluding past. The range is written in ascending order unless past is less than first, in which case the range is written in descending order.

The tricky part of this exercise is making sure to handle all of the arguments properly; that’s easy if your Scheme provides case-lambda, and ugly if it doesn’t:

(define range
  (case-lambda
    ((past) (range 0 past (if (positive? past) 1 -1)))
    ((first past) (range first past (if (< first past) 1 -1)))
    ((first past step)
      (let ((le? (if (positive? step) =)))
        (let loop ((x first) (xs (list)))
          (if (le? past x)
            (reverse xs)
            (loop (+ x step) (cons x xs))))))
    (else (error 'range "invalid arguments"))))

The first two cases simply call range recursively with three arguments. The work in done in the third case, which defines a stopping condition le? less-than-or-equal based on the sign of the step argument. Here are some examples:

> (range 7)
(0 1 2 3 4 5 6)
> (range -3)
(0 -1 -2)
> (range 7 0)
(7 6 5 4 3 2 1)
> (range 11 0 -2)
(11 9 7 5 3 1)

The run-time complexity is linear in the size of the output list.

You can run the program at http://programmingpraxis.codepad.org/TiCFpjxN, where you can see a version of range that doesn’t rely on case-lambda. There are many other examples of list utilities in the Standard Prelude.

Pages: 1 2