## Self-Organizing Lists

### November 6, 2015

The hardest part of this problem is plumbing: since the list may change each time it is touched, all of the functions must return the list as well as their result. We use a *box*, as defined in the Standard Prelude, to pass arguments by reference instead of by value:

(define (box v) (vector v)) (define (unbox box) (vector-ref box 0)) (define (box! box v) (vector-set! box 0 v))

Our first function creates an empty set:

(define (set-create) (box (list)))

Searching runs through the set front to back, moving the sought item to the front if it exists in the set; it returns #t if the item is in the set and #f otherwise:

(define (set-member? x xs) (let loop ((front (list)) (back (unbox xs))) (cond ((null? back) #f) ((equal? x (car back)) (box! xs (append (list (car back)) (reverse front) (cdr back))) #t) (else (loop (cons (car back) front) (cdr back))))))

Insertion adds an element to the front of a set if it isn’t already in the set, or moves the element to the front of the set if it is already in the set, returning the set in either case:

(define (set-insert! x xs) (if (not (set-member? x xs)) (box! xs (cons x (unbox xs)))) xs)

The last requirement is a delete function, which removes the item from the set if it is present, then returns the set:

(define (set-delete! x xs) (if (set-member? x xs) (box! xs (cdr (unbox xs)))) xs)

Here are some examples. Note that the order of the items in the set changes after the search:

> (define xs (set-create)) > (set-insert! 1 xs) #((1)) > (set-insert! 2 xs) #((2 1)) > (set-insert! 3 xs) #((3 2 1)) > (set-member? 1 xs) #t > xs #((1 3 2)) > (set-delete! 2 xs) #((1 3)) > (set-delete! 1 xs) #((3)) > (set-delete! 3 xs) #(()) > (set-member? 1 xs) #f

You can run the program at http://ideone.com/Frl4eF.

Standard ML implementation that returns a new set for every operation, so it is not very efficient but it was interesting to write with the supplied properties.

Here’s a cute solution using C++ references to ensure in-place updates – since we can’t assign to reference variables it’s nice to use recursion & rely on modern compilers to turn the tail calls into a loop. It’s easier to think about if we have separate operations to remove a node from a list, and to put one in. There is something appealing about code like this, that looks functional but is, in fact, deeply imperative.

My first attempt was an exercise in creating my own linked list using std::unique_ptr to handle the memory allocations/deallocations.

My second attempt uses std::forward_list. At first, I thought no standard algorithms would help with List::contains. (At least not without being less efficient.) Then I noticed std::adjacent_find could do the job. I don’t think I’m abusing it here.