Here is a C function that reverses a linked list:

typedef struct node_ {
    int data;
    struct node_ *next;
} node_t;

node_t *list_reverse(node_t *first) {
    node_t *a = NULL;
    node_t *b = first;
    while(NULL != b) {
        node_t *next = b->next;
        b->next = a;
        a = b;
        b = next;
    }
    return a;
}

Here is the same function in Scheme:

(define (list-reverse! first)
  (let loop ((a '())
             (b first))
    (cond ((null? b)
           a)
          (else
            (let ((next (cdr b)))
              (set-cdr! b a)
              (loop b next))))))

(SRFI-1 contains a reverse! function that does the same thing.)

For me, the Scheme was a direct transcription of the C. Someone more familiar with Scheme's do or while loop mechanisms might have ended up with something that looked even more like the C version. Use set! as well, & you get something like this:

(define (list-reverse! first)
  (let ((a '())
        (b first))
    (while (not (null? b))
           (let ((next (cdr b)))
             (set-cdr! b a)
             (set! a b)
             (set! b next)))
    a))

Likewise, I could rewrite the C version to look more like the Scheme. Like this:

node_t *list_reverse_(node_t *a, node_t *b)
{
    if(!b) {
        return a;
    } else {
        node_t *next = b->next;
        b->next = a;
        list_reverse_(b, next);
    }
}

node_t *list_reverse(node_t *first)
{
    return list_reverse_(NULL, first);
}

Observations:

• A linked list is a built-in type for Scheme; in C it has to be defined.
• Scheme's syntax for variable initialization is very different from the syntax for assignment. C went the opposite route. There are pros & cons to both.
• Also, C's variable declaration syntax blends in more than Scheme's.

last updated 2 years ago #