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 creates a new record of the successful search so that the second routine above replays the memory in the original order. Perhaps the new record has been placed in longer term memory. I conjecture that the rat did this program in response to finding the food. This program processes the rat’s observation in reverse order conforming to the surprising observations made by the authors.

Presumably the first linked list is kept in short term memory and the longer memory is formed only upon finding food. This is good engineering if writing long term memory is expensive.