SS 2004Mar12: The code at the end of this page implements alists data structures for Tcl. The following text is my brainstorm during the design of this implementation/API written in form of tutorial.
Alists, or Association Lists are lists of a special format. Each two elements of the list represent a key and an associated value. The following Tcl list is an alist with three elements:
[list a 1 b 2 c 3]
The key a is associated with the value 1, b with value 2, and so on. (Note: alists are very used in Lisp dialects, but the format is a bit different. Every alist element is a two element list, so the format is like [list [list a 1] [list b 2] [list c 3]]]. In Tcl the flat list format is more convenient).
Alists are very powerful, because they have many advantages of structures (in the sense of C struct or Scheme structs) but are more dynamic because fields are not accessed by index.
Alists can be incrementally augmented just adding two elements to their list representation. Because functions to get/set values by keys search the alist from left to right, an added key/value can shadow the next identical key in the alist.
Alists can be viewed as a mapping from keys to data that can be extended, reduced or non-destructively altered at runtime, and at the same time be a valid list.
[CMCc — incidentally, mappings from keys to data can also be fruitfully looked at as partial functions]
[DKF — Actually, the alist value is not updatable; it is the variable containing the alist that is updatable; model the variable as a higher-order function from "abstract time" (i.e., generation sequence number) to the relation representing the current alist.]
Alists are very generic, but the first goal of this library is provide a way to encapsulate an object representation in a simple but powerful data structure.
(skip it if you want just the tutorial)
The alist representation has the benefit to be a valid dict representation, but the usage and design is a bit different. Basically they are very similar but the API is different: dicts are designed to be generic, while this implementation of alists is designed to make it easy to be used as powerful structures (in the sense of C "struct").
Alists require a struct-like declaration, that creates a command to create new alists of the defined types with pre-initialized fields.
To get or set a key that does not exists always raises an error (of course the programmer may add keys by hand just appending a key/value pair to the list representation of the alist, but the main idea is that alists are used to access named fields of a pre-defined data structure, so to set an unknown key can't just create a new key/value pair: it's not defensive programming).
Alists can be implemented very well using dict, but since dict is still only available in Tcl >= 8.5 this implementation uses only commands available in Tcl 8.4 (notably lset). BTW, note that alists implemented with dict lost some interesting priprietis (because the lookup is no longer from "left" to "right", and also can't hold multiple identical keys).
(DKF — As implemented in the 8.5.0 release, dictionaries are order-preserving and so have effective right-to-left lookup order. This was a late change in the 8.5 betas. They still can't hold multiple identical keys by design.)
To define a new alist, the alist command is used:
For example:
alist flower petals color type
The call to the alist command with this arguments creates a command named [make-flower] that returns a list representing an alist with the specified keys/values pairs.
To access fields we use the alget and alset commands.
For example, to create a flower that's a red rose with 5 petals we may write:
set rose [make-flower]
alset rose petals 5
alset rose color red
alset rose type rosealset has the following signature:
The alset command takes as arguments the name of a variable that holds a valid alist, the name of the key to set, and the new value. It's possible to specify more than just one key/value pair, so the previous last three lines of code are equivalent to:
alset rose petals 5 color red type rose
To access the value associated with a given key we use alget, that has the following signature:
We may for example create a function that pretty-prints a flower object:
proc print-flower flower {
puts "This flower is a [alget $flower type] with [alget $flower petals] [alget $flower color] petals"
}
print-flower $roseWill print: "This flower is a rose with 5 red petals".
Both alget and alset will raise an error if the specified key does not exists.
When alists are declared, we can specify the default value for every key. This way, the [make-<alistname>] command will create alists with every value initialized to the default value specified in the declaration.
For example we may want to re-declare the flower structure in this way:
alist flower {petals 0} {color none} {type unknown}Now every new flower alist created using [make-flower] will be initialized with the default values we provided. As you can see to specify a default value, instead to use the key name, we use a two-element list with the key name and the default value.
This is the behaviour of the new definition:
set someflower [make-flower] print-flower $someflower
Will output: "This flower is a unknown with 0 none petals".
Another way to initialize fields at creation time is to pass arguments to the [make-flower] function. For example to create a flower with the default values but with 3 white petals we can write:
set someflower [make-flower petals 3 color white]
It should be noted that if no default value is specified in the alist declaration, nor arguments are passed to the [make-...] command, all the fields are initialized to an empty string.
alists (like dicts) are able to nest. Let's see why and how to use this feature.
Suppose you are creating a program for a florist that ships different kind of flowers in a box to different addresses.
The program is used to manage shipping of boxes, so to define the box object can be handy. A box in our case is some container with a flower inside and a shipping address. It is also available in different colours.
To start, we may want to define the 'address' object.
alist address street number city
The second step is to define the 'box' object.
alist box color content shipaddr
To create a yellow box object with a red rose with 10 petals inside to be shipped in Rome, Appia Street, 40, we may write something like this:
set aflower [make-flower color red petals 10 type rose]
set addr [make-address street Appia number 40 city Rome]
set box [make-box color red content $aflower shipaddr $addr]Now the alist box contains two nested alists. How to access them? We can just use the dot to create "key paths" that describe the path to reach a given key inside nested alist.
For example to get the city of the box's shipping address we can just write:
alget $box shipaddr.city
alset works just the same way. That's OK, but to create a box with a flower inside and a shipping address was a bit verbose. We can use the default initialization of alists and define boxes this way:
alist box color [list content [make-flower]] [list shipaddr [make-address]]
This way all the box created using [make-box] will contain nested flower and address alists.
Now to create the previous box we can write:
set box [make-box color red \
content.color red content.petals 10 content.type rose \
shipaddr.city Rome shipaddr.street Appia shipaddr.number 40]That's it. Note that after we created the box, we may like to, for example, change the flower inside. If $whiteflower already contains a flower alist with a 30 petals yellow marguerite we have just to write:
alset box content $whiteflower
For complex manipulation of alists it can be a good idea to write functions that do the work for us. Remember that alists are just values (so, just strings), so you can pass and return they with normal procedures.
Our florist wants to expand its product line, so it plans to ship boxes with more than one flower. The florist's software development division face a new problem: to describe boxes with N flowers inside.
A simple solution is to make the ‘content’ field of the box alist, a list of alists. Every element is a flower alist. This works as representation, but it can be uncomfortable to read/modify boxes's content. Fortuantely our alists have support for this. If an element in a key path is a number, it is used to index a particular list element.
For example:
alget $alist foo.3
Will return the value of the element with index 3 of the list stored in the ‘foo’ field of $alist.
For extension:
alget $somebox content.5.color
Will return the value of the ‘color’ key of the alist at index 5 in the list-of-alists stored in the ‘content’ field.
Still to add new boxes to the content may be tricky. We need to get the content list of alists, append a new flower to it, and then set this new list.
So, assuming we created an empty red box in this way, with some shipping address,
set box [make-box color red content {} shipaddr $addr]to add a new flower inside the box we need the following commands:
set l [alget $box content] lappend content [make-flower color blue type tulipan] alset box content $content
In order to make it more simple, the alist library provides the allappend command that works like lappend but against alist fields. So we can rewrite the above three lines of code into:
allappend box content [make-flower color blue type tulipan]
Every time an alist is created by the [make-<name>] command, the generated alist contains all the keys the user specified in the alist definition of that name, plus an additional key __alisttype__ that has as default value the name of the alist's type.
To make it simpler, if we create an alist, “point”, with:
alist point x y
and we create a point:
set p [make-point x 1 y 2]
then the following command will return the string "point":
alget $p __alisttype__
Instead to directly get the __alisttype__ key, there is the command altype that does just this. So the above code is equivalent to:
altype $p
Programmers can use the type information in different ways: for function overloading, type checking, and so on.
The following is an example of function overloading using alist's type information.
alist string value
alist list value
alist int value
proc + {a b} {
set A [alget $a value]
set B [alget $b value]
switch -- [altype $a] {
string {make-string value $A$B}
list {make-list value [concat $A $B]}
int {make-int value [expr {$A+$B}]}
default {error "don't know how to add '[altype $a]'"}
}
}
set a [make-string value 10]
set b [make-string value 20]
lappend res [+ $a $b]
set a [make-list value 10]
set b [make-list value 20]
lappend res [+ $a $b]
set a [make-int value 10]
set b [make-int value 20]
lappend res [+ $a $b]
foreach r $res {puts [alget $r value]}The output will be 1020, 10 20 and 30
alincr increments the integer at the specified alist's key. Example:
alincr alistVarName x.y -3
The last argument (the increment) can be omitted and defaults to 1.
alsappend is like allappend but append strings to the specified string instead to elements to the specified list.
it's called ‘sappend’ because append strings. Since allappend is similar to lappend, and alsappend is similar to append you may wonder why the name of this command is not just alappend. That's because it's too simple to write “alappend” instead of “allappend”.
Happy nesting.
# Alists - Lisp-like alist data structures. # Copyright (C) 2004 Salvatore Sanfilippo <[email protected]>. # Under the same license as Tcl/Tk 8.4 namespace eval ::alist {} # Return the index of the specified key. # -1 is returned if the alist key is not found. proc alist::alindex {alist key} { set i 1 foreach {f _} $alist { if {$f eq $key} {return $i} incr i 2 } return -1 } # Return a list of list idexes that can be used as arguments # to lset or lindex to access to the list element identified # by the 'keys' list. proc alist::alpath {alist keys} { set l $alist set path {} foreach f $keys { if {[string is integer -strict $f]} { set i $f } else { set i [::alist::alindex $l $f] } if {$i == -1} { error "No such key '[join $keys ->]' in alist" } set l [lindex $l $i] lappend path $i } return $path } # Get the value of the alist's key 'field'. # Example: alget $l foo.bar proc alist::alget {alist field} { set path [::alist::alpath $alist [split $field .]] switch -- [llength $path] { 1 {lindex $alist [lindex $path 0]} 2 {lindex $alist [lindex $path 0] [lindex $path 1]} 3 {lindex $alist [lindex $path 0] [lindex $path 1] [lindex $path 2]} 0 {error "No key specified"} default {eval [list lindex $alist $path]} } } # Set the value of one ore more alist's keys. # Example: alset $l foo 5 bar 6 attrib.color 10 proc alist::alset {alistVar args} { upvar $alistVar alist foreach {field val} $args { set path [::alist::alpath $alist [split $field .]] switch -- [llength $path] { 1 {lset alist [lindex $path 0] $val} 2 {lset alist [lindex $path 0] [lindex $path 1] $val} 3 {lset alist [lindex $path 0] [lindex $path 1] [lindex $path 2] $val} 0 {error "No key specified"} default {eval [list lset alist $path $val]} } } return $alist } # Define a new alist. As side effect, a command [make-<name>] to # create new alists of the specified type is created. proc alist::alist {name args} { set template [list __alisttype__ $name] foreach slot $args { set initializer {} if {[llength $slot] > 1} { set initializer [lindex $slot 1] set slot [lindex $slot 0] } lappend template $slot $initializer } proc ::make-$name args [format { set s %s foreach {slot val} $args { alset s $slot $val } return $s } [list $template]] return $args } # Return the list of (non nested) keys of the specified alist. proc alist::alkeys alist { set fields {} foreach {f _} $alist { lappend fields $f } return $fields } # Return the alist's type name proc alist::altype alist { ::alist::alget $alist __alisttype__ } # Increment the (integer) value of the specified key. proc alist::alincr {alistVar field {increment 1}} { upvar $alistVar alist set int [::alist::alget $alist $field] incr int $increment ::alist::alset alist $field $int } # Lappend the arguments to the list at the alist's key. proc alist::allappend {alistVar field args} { upvar $alistVar alist set list [::alist::alget $alist $field] ::alist::alset alist $field {} ;# May reduce the $list refcount to 1 foreach e $args { if {[catch {lappend list $e} err]} { # Restore the alist state ::alist::alset alist $field $list # Propagate the error error $err } } ::alist::alset alist $field $list } # append the arguments to the string at the alist's key. proc alist::alsappend {alistVar field args} { upvar $alistVar alist set str [::alist::alget $alist $field] ::alist::alset alist $field {} ;# May reduce the $str refcount to 1 foreach e $args { append str $e } ::alist::alset alist $field $str } namespace eval alist { namespace export alget alset alist alkeys altype alincr allappend alsappend }
kruzalex With some changes in the code it is possible to use also name of the keys to get values by nesting. See below modified code and attached examples:
proc alist::alindex {alist key} {
upvar path p
set i 1
foreach {f _} $alist {
if {$f eq $key} {
return $i
}
if {[string is integer -strict $p]} {
set i [lsearch [lindex $alist $p] $key]
incr i
return $i
}
incr i 2
}
return
proc alist::alpath {alist keys} {
set l $alist
set path {}
foreach f $keys {
if {[string is integer -strict $f]} {
set i $f
} else {
set i [::alist::alindex $l $f]
}
lappend path $i
}
return $path
}
proc alist::allappend {alistVar field args} {
upvar $alistVar alist
set list [::alist::alget $alist $field]
::alist::alset alist $field {} ;# May reduce the $list refcount to 1
foreach arg $args {
foreach e $arg {
if {[catch {lappend list $e} err]} {
::alist::alset alist $field $list
error $err
}
}
}
::alist::alset alist $field $list
}
#Example1
alist someflower petals color
set rose [make-someflower]
alset rose petals 5
alset rose color red
proc print-flower flower {
puts "This flower is a with [alget $flower petals] [alget $flower color] petals"
}
print-flower $rose
#Example2
alist someflower petals color
set rose [make-someflower petals 0 color red]
proc print-flower flower {
puts "This flower is a with [alget $flower petals] [alget $flower color] petals"
}
print-flower $rose
#Example3
alist aflower color petals type
alist addr street number city
alist box color content shipaddr
set aflower [make-aflower color red petals 10 type rose]
set addr [make-addr street Appia number 40 city Rome]
set box [make-box color red shipaddr $addr]
puts [alget $box shipaddr.city]
#Example4
alist aflower color petals type
alist addr street number city
alist box color content shipaddr
set aflower [make-aflower]
alset aflower color red
alset aflower petals 10
alset aflower type rose
set addr [make-addr]
alset addr street Appia
alset addr number 40
alset addr city Rome
set box [make-box]
alset box color red
alset box content $aflower
alset box shipaddr $addr
#puts [alget $box shipaddr.7]
puts [alget $box shipaddr.city]
#Example5
alist aflower color petals type
alist addr street number city
alist box color content shipaddr
set aflower [make-aflower color red petals 10 type rose]
set addr [make-addr street Appia number 40 city Rome]
set box [make-box color red content {} shipaddr $addr]
allappend box content [make-aflower color blue type tulipan]
#puts [alget $box content.3]
puts [alget $box content.color]There's "ihash" if you want to speed up things for 8.4 (not sure you're aiming at large alists) - see [L1 ] and Adding a hashed datatype -jcw
I've not a lot of experience with them, but are these alists similar to Tclx's keyed lists? Also, they seem, in layout, to be similar to the values returned from an array get command - is that a valid understanding?
DKF: They're similar to dicts and the lack of property duplication can be construed to be a good thing. :^) Oh, and yes, they are similar semantically to keyed lists, though different syntactically.