February 12, 2006 in “Nature”
David Foster and Matthew Wilson

I recently read of experiments on rats who had recently found a reward by traversing a maze. (Original paper here? by David Foster and Matthew Wilson) Evidence was presented that after finding the reward, the rats processed details of the traversal in reverse order. The reporter, at least, thought it surprising that while recollecting a success, the order of events would be reversed. Assuming that the memory of animals employes a linked list (in the sense of software) the following explanation seems obvious.

The simplest way to form a linked list of temporal events leaves the list in a form where the simplest way to recount the events, recounts the events backwards in time. Merely copying the list, using these two simple algorithms, results in a new list whose simple access yields the events forward in time. The events are processed in reverse order as the copy is created.

The easiest program to make a linked list to capture details of a sequence of events is as follows:

struct node {ob observation; node * link;};
static node * root = 0;
while (searching) {
   int obs = read();
   node * nn = malloc(sizeof (node));
   nn -> link = root;
   nn -> observation = obs;
   root = nn;}
After this program finishes the sequence of observations has been recorded. The easiest program to report the observations is:
while(root) {report (root-> observation); root = root-> link;}
Alas this reports the events in reverse order; the last observation is reported first.

There is another simple program to reverse the order of the record:

{node * root2 = root; root = 0;
while(root2) {node * nn = malloc(sizeof(node));
   nn -> link = root;
   nn -> observation = root2-> observation;
   root = nn;
   root2 = root2-> link;}
This leaves a new record of the successful events so that the second routine above replays the memory in the traversal order. I conjecture that the rat did this program in response to finding the food.

Presumably the first linked list is kept in short term memory and the longer memory is formed only upon finding food.