UpNextPrevPrevTailTail

2.11 Alists

Another frequently used LISP structure is the association list (alist), which is an associative memory: a list where each element is a pair with a search item and a value item. The function assoc picks the pair for a given search item out of the alist. For example constructing a multiplier with memory:

      fluid ’(product_database*);  
      symbolic procedure multiply(u,v);  
       begin scalar w,r;  
        w:=u.v;  
        r:=assoc(w,product_database*);  
        if r then return cdr r; % found  
        r:=u*v;  
        product_database*:=(w.r).product_database*;  
        return r;  
      end;

here the pair u.v is used as search item. If an entry is found in the database, its value part is returned. Otherwise the product is computed and the new entry is added to the database. After calling this function with arguments 2 and 3, and then with 2 and 6 the structure would be

     .-------.    .-------.  
     | * | *-+--->| * | / |  
     ‘-|-----’    ‘-|-----’  
       |            |  
     .-------.    .-------.  
     | * | 6 |    | * | 12|  
     ‘-|-----’    ‘-|-----’  
       |            |  
     .-------.    .-------.  
     | 2 | 3 |    | 2 | 6 |  
     ‘-------’    ‘-------’

Here each element in the top level list points to one generalized name-value pair, where the name itself is a structure (here a pair of two numbers). REDUCE uses association lists for many different purposes; e.g. if an expression is simplified, the expression and its simplified variant are stored in an association list such that for a second access to the same expression its simplified form is immediately accessible.

UpNextPrevPrevTailFront