Thinking in Terms of Results

I want you to understand that sometimes you can see a problem in a different way and rewrite it so that a special case goes away and becomes the normal case, and that’s good code.

— Linus Torvalds

Here’s the textbook way to remove an item from a singly linked list:

void remove_cs101(list *l, list_item *target) {
        list_item *cur = l->head,
                  *prev = NULL;

        while (cur != target) {
                prev = cur;
                cur = cur->next;
        }

        if (prev)
                prev->next = cur->next;
        else
                l->head = cur->next;
}

And here’s the one Linus calls good taste:

void remove_elegant(list *l, list_item *target) {
        list_item **p = &l->head;

        while (*p != target)
                p = &(*p)->next;

        *p = target->next;
}

The first version walks the list and then asks “was it the head?”. The second one asks a different question: which pointer has to change? Once you think about the result instead of the walk, the head stops being special.

Curious?

Now look at this:

?- insertionSort([2, 3, 2, 1], S).
S = [1, 2, 2, 3] ;
false.

?- insertionSort(I, [1, 2, 3]).
I = [1, 2, 3] ;
I = [2, 1, 3] ;
I = [3, 1, 2] ;
I = [1, 3, 2] ;
I = [2, 3, 1] ;
I = [3, 2, 1] ;
false.

The same insertion sort that sorts a list also lists every permutation that sorts into a given result. Nobody wrote a second algorithm for that. To see how, we need a little bit of Prolog.

Prolog in three steps

1. State facts.
2. Define rules.
3. Ask queries.

Let’s start from a small family.

State facts

% parent(Parent, Child)
parent(anne, brad).    % Anne is Brad's parent
parent(anne, claire).  % Anne is Claire's parent
parent(tom, brad).     % Tom is Brad's parent
parent(tom, claire).   % Tom is Claire's parent
parent(brad, ella).    % Brad is Ella's parent
parent(julia, ella).   % Julia is Ella's parent

Define rules

Implication is read right to left, and the comma means “and”.

% A is a child of B if B is a parent of A
child(A, B) :- parent(B, A).

% A and B are siblings if they share a parent and are not the same person
sibling(A, B) :-
    parent(P, A),
    parent(P, B),
    A \= B.

% A is a grandparent of B if A is a parent of C, and C is a parent of B
grandparent(A, B) :-
    parent(A, C),
    parent(C, B).

Ask queries

Some queries answer with a truth value. Others bind variables to every value that makes the query true.

% Is Brad a parent of Ella?
?- parent(brad, ella).
true.

% Who are the children of Anne?
?- child(X, anne).
X = brad ;
X = claire.

% Are Brad and Claire siblings? (Twice: through Anne, and through Tom.)
?- sibling(brad, claire).
true ;
true.

% Who are the grandparents of Ella?
?- grandparent(X, ella).
X = anne ;
X = tom ;
false.

Notice that we never said how to find a grandparent. We said what a grandparent is, and the solver searched for every answer.

Remove, with a twist

Here’s how to remove an element from a list:

remove(E, [E | R], R).
remove(E, [H | R], [H | Left]) :-
    remove(E, R, Left).

It does what it says:

?- remove(3, [1, 2, 3], X).
X = [1, 2] ;
false.

But remove doesn’t describe a procedure. It describes a relation between an element, a list, and that list without the element. So we can ask the question the other way around: which lists give [1, 1, 1] once you remove a 3?

?- remove(3, L, [1, 1, 1]).
L = [3, 1, 1, 1] ;
L = [1, 3, 1, 1] ;
L = [1, 1, 3, 1] ;
L = [1, 1, 1, 3] ;
false.

We just got a way to insert an element at every possible position. For free!¹

Employing this technique

A permutation of [H | T] is a permutation of T with H put back somewhere. And “put back somewhere” is just remove, read backwards:

perm([], []).
perm([H | T], P) :-
    perm(T, P1),
    remove(H, P, P1).

?- perm([1, 2, 3], P).
P = [1, 2, 3] ;
P = [2, 1, 3] ;
P = [2, 3, 1] ;
P = [1, 3, 2] ;
P = [3, 1, 2] ;
P = [3, 2, 1] ;
false.

The insertion sort from the beginning works the same way. A sorting algorithm takes any permutation of a list and produces the ordered one. Run the same reasoning backwards and you enumerate every distinct permutation that sorts to that result:

?- insertionSort(I, [1, 2, 2, 3]).
I = [1, 2, 2, 3] ;
I = [2, 1, 2, 3] ;
I = [3, 1, 2, 2] ;
I = [2, 2, 1, 3] ;
I = [3, 2, 1, 2] ;
I = [1, 3, 2, 2] ;
I = [2, 3, 1, 2] ;
I = [1, 2, 3, 2] ;
I = [2, 1, 3, 2] ;
I = [2, 2, 3, 1] ;
I = [3, 2, 2, 1] ;
I = [2, 3, 2, 1] ;
false.

Sorting and generating permutations turn out to be the reverse of one another.

Let’s summarize

What made this possible?

• Pattern matching
• Implicit flow control
• Symbolic “reasoning”
• Logic constructions
• Computations as queries

The moral

The moral of the story is: deal with all elements of a set by ignoring them and working with the set’s definition. […] deal with all computations possible under control of a given program by ignoring them and working with the program.

— Edsger W. Dijkstra, On the Cruelty of Really Teaching Computing Science

That’s what thinking in terms of results means. Linus’s pointer-to-pointer removes a special case because it describes what has to change, not how to get there. Prolog takes the same idea all the way: describe what the result is, and every way of reaching it comes along.

It isn’t a reason to write everything in Prolog. Pick the right tool for each job. But ask yourself:

• Do you backtrack your results?
• Do you prune search spaces?
• Do you generate non-deterministic results?
• Do you need reversible flows?

If the answer is yes, maybe it’s time to stop writing the steps and start writing down the result.

The full code

Here’s the full insertion sort, in SWI-Prolog. I designed it from the beginning to be reversible; that isn’t the default for every implementation. The insertionSort/2 wrapper takes the length from whichever list is known, so the search always knows when to stop.

:- use_module(library(clpfd)).

remove(E, [E | R], R).
remove(E, [H | R], [H | Left]) :-
    remove(E, R, Left).

perm([], []).
perm([H | R], P) :-
    perm(R, P1),
    remove(H, P, P1).

insert(X, [], [X]).
insert(X, [X1|L1], [X, X1|L1]):-
  X #=< X1.
insert(X, [X1|L1], [X1|L]):-
  X #> X1,
  insert(X, L1, L).

insertionSort(0, [], []).
insertionSort(N, [X|L], S):-
  N > 0,
  N1 is N - 1,
  insertionSort(N1, L, S1),
  insert(X, S1, S).

insertionSort(L, S) :-
  nonvar(L) -> (
    nonvar(S) ->
      length(S, N),
      insertionSort(N, L, S)
    ;
      length(L, N),
      insertionSort(N, L, S)
  ) ;
    nonvar(S),
    length(S, N),
    insertionSort(N, L, S).