list ← list ##.alpush key val   ⍝ List ⍺ extended with key-value pair ⍵
val list ← list ##.alpop  key       ⍝ Value for key ⍵, and reduced list ⍺
     val ← list ##.alget  key       ⍝ Value for key ⍵ from list ⍺
    list ← list ##.alset  key val   ⍝ List ⍺ with key-value ⍵ replacement

An  association list (AKA: dictionary, symbol table, look-up table) is a classic
and generally useful structure.  It is implemented here as a pair of vectors  of
keys and values.  Each item of the keys vector would typically  be  a  character
vector but it could be any array.

An example might be a list of things people found on the beach:

    ⊢ found ← ('milly' 'molly' 'may') ('star' 'thing' 'stone')    ⍝ keys values
┌─────────────────┬──────────────────┐
│┌─────┬─────┬───┐│┌────┬─────┬─────┐│
││milly│molly│may│││star│thing│stone││
│└─────┴─────┴───┘│└────┴─────┴─────┘│
└─────────────────┴──────────────────┘

    found alget 'may'                           ⍝ what did may find?
stone

[alpush] and [alpop] prefix and remove keys from the list:

    ⊢ found ← found alpush 'maggie' 'shell'     ⍝ maggie discovered a shell
┌────────────────────────┬────────────────────────┐
│┌──────┬─────┬─────┬───┐│┌─────┬────┬─────┬─────┐│
││maggie│milly│molly│may│││shell│star│thing│stone││
│└──────┴─────┴─────┴───┘│└─────┴────┴─────┴─────┘│
└────────────────────────┴────────────────────────┘

    ⎕ found ← found alpop 'molly'               ⍝ Pop molly and her finding
thing
      found
┌──────────────────┬──────────────────┐
│┌──────┬─────┬───┐│┌─────┬────┬─────┐│
││maggie│milly│may│││shell│star│stone││
│└──────┴─────┴───┘│└─────┴────┴─────┘│
└──────────────────┴──────────────────┘

[alget] and [alset] access and replace list items:

    found alget 'may'                           ⍝ may's finding
stone

    ⊢ found ← found alset 'may' 'pebble'        ⍝ swap may's stone for a pebble
┌──────────────────┬───────────────────┐
│┌──────┬─────┬───┐│┌─────┬────┬──────┐│
││maggie│milly│may│││shell│star│pebble││
│└──────┴─────┴───┘│└─────┴────┴──────┘│
└──────────────────┴───────────────────┘

    found alget 'may'                           ⍝ ... and check
pebble

Shadowing
---------
[alpush]  _prefixes_ a new value to the list.  This means that a new association
"shadows" an existing one of the same key as far as subsequent calls to  [alget]
are concerned. [alpop] removes the last-pushed pairing, thus "unshadowing" it.

    found                                       ⍝ association list
┌──────────────────┬───────────────────┐
│┌──────┬─────┬───┐│┌─────┬────┬──────┐│
││maggie│milly│may│││shell│star│pebble││
│└──────┴─────┴───┘│└─────┴────┴──────┘│
└──────────────────┴───────────────────┘

    ⊢ found ← found alpush 'may' 'rock'         ⍝ may's rock shadows her pebble
┌──────────────────────┬────────────────────────┐
│┌───┬──────┬─────┬───┐│┌────┬─────┬────┬──────┐│
││may│maggie│milly│may│││rock│shell│star│pebble││
│└───┴──────┴─────┴───┘│└────┴─────┴────┴──────┘│
└──────────────────────┴────────────────────────┘

    found alget 'may'                           ⍝ may's latest find
rock
    ⎕ found ← found alpop 'may'                 ⍝ unshadowing may
rock
    found alget 'may'                           ⍝ previous value revealed
pebble

Technical notes:

[alget] is coded:

    alget←{keys vals←⍺ ⋄ (keys⍳⊂⍵)⊃vals}

If the sought key is not in the list, the code generates INDEX ERROR. It is easy
to tweak the function to return a special "not found" value instead:

    alget←{keys vals←⍺ ⋄ (keys⍳⊂⍵)⊃vals,⊂'Eh?'}
                                       ¯¯¯¯¯¯¯
Similar changes would allow [alset] and [alpop] to be equally permissive.

Examples:

    list←('milly' 'molly' 'may')('star' 'thing' 'stone')

    list alget 'may'                            ⍝ associated with may:
stone

    ⊢ list ← list alpush 'maggie' 'shell'       ⍝ prefix maggie and her shell
┌────────────────────────┬────────────────────────┐
│┌──────┬─────┬─────┬───┐│┌─────┬────┬─────┬─────┐│
││maggie│milly│molly│may│││shell│star│thing│stone││
│└──────┴─────┴─────┴───┘│└─────┴────┴─────┴─────┘│
└────────────────────────┴────────────────────────┘

    ⊢ item list ← list alpop 'molly'            ⍝ without molly and her thing
┌─────┬───────────────────────────────────────┐
│thing│┌──────────────────┬──────────────────┐│
│     ││┌──────┬─────┬───┐│┌─────┬────┬─────┐││
│     │││maggie│milly│may│││shell│star│stone│││
│     ││└──────┴─────┴───┘│└─────┴────┴─────┘││
│     │└──────────────────┴──────────────────┘│
└─────┴───────────────────────────────────────┘

    ⊢ list ← list alset 'may' 'pebble'          ⍝ may's stone replaced
┌──────────────────┬───────────────────┐
│┌──────┬─────┬───┐│┌─────┬────┬──────┐│
││maggie│milly│may│││shell│star│pebble││
│└──────┴─────┴───┘│└─────┴────┴──────┘│
└──────────────────┴───────────────────┘

See also: Graphs list key foldl

Back to: contents

Back to: Workspaces