Nested Lists

Part I · Module 6 · Chapter 6.11 · Nested Lists

1. A List of Lists

set table {{clk 1} {reset 1} {payload 64}}

puts "rows:     [llength $table]"
puts "row 0:    [lindex $table 0]"
puts "its size: [llength [lindex $table 0]]"

rows:     3
row 0:    clk 1
its size: 2

Three elements, each of which is itself a two-element list. llength counts the outer level — Chapter 6.3 §5.

2. Building One

Because list quotes automatically — Chapter 6.2 — nesting needs no special handling:

set row1 [list clk 1]
set row2 [list "data bus" 64]

set table [list $row1 $row2]

puts "table: $table"
puts "rows:  [llength $table]"
puts "cell:  <[lindex $table 1 0]>"

table: {clk 1} {{data bus} 64}
rows:  2
cell:  <data bus>

The two-word name survived two levels of nesting without a brace written by hand. That is the payoff of building with list rather than gluing text.

Growing the table is lappend:

set table {}

lappend table [list clk 1]
lappend table [list reset 1]

puts "$table -> [llength $table] rows"

{clk 1} {reset 1} -> 2 rows

Each row goes in as one element, which is exactly Chapter 6.6 §10's point about lappend adding one element rather than merging.

3. Reaching a Cell

set table {{clk 1} {reset 1} {payload 64}}

puts "row 2       -> [lindex $table 2]"
puts "row 2, col 0-> [lindex $table 2 0]"
puts "row 2, col 1-> [lindex $table 2 1]"

row 2       -> payload 64
row 2, col 0-> payload
row 2, col 1-> 64

Each index goes one level deeper — Chapter 6.4 §5.

And writing uses the identical indices — Chapter 6.8 §3:

set table {{clk 1} {reset 1} {payload 64}}

lset table 2 1 128

puts [lindex $table 2]

payload 128

4. Walking the Rows

The readable form uses lassign to name the columns — Chapter 6.14:

set table {{clk 1 input} {reset 1 input} {payload 64 output}}

foreach row $table {
    lassign $row name width direction
    puts [format "  %-10s %4d  %s" $name $width $direction]
}

  clk           1  input
  reset         1  input
  payload      64  output

Compare that with the alternative:

set table {{clk 1 input} {reset 1 input} {payload 64 output}}

foreach row $table {
    puts [format "  %-10s %4d  %s" [lindex $row 0] [lindex $row 1] [lindex $row 2]]
}

  clk           1  input
  reset         1  input
  payload      64  output

Same output. The first version names the columns; the second makes a reader count positions.

5. Sorting and Searching by Column

Everything from the previous two chapters applies:

set table {{clk 1} {reset 1} {payload 64}}

puts "by width:  [lsort -index 1 -integer $table]"
puts "find reset:[lsearch -exact -index 0 $table reset]"
puts "that row:  [lindex $table [lsearch -exact -index 0 $table reset]]"

by width:  {clk 1} {reset 1} {payload 64}
find reset:1
that row:  reset 1

-index in both commands means "compare this column".

6. Deeper Nesting

Nothing stops you going further:

set grouped {
    {inputs {{clk 1} {reset 1}}}
    {outputs {{payload 64}}}
}

puts "groups:        [llength $grouped]"
puts "first group:   [lindex $grouped 0 0]"
puts "its rows:      [lindex $grouped 0 1]"
puts "first row name:[lindex $grouped 0 1 0 0]"

groups:        2
first group:   inputs
its rows:      {clk 1} {reset 1}
first row name:clk

lindex $grouped 0 1 0 0 is four levels deep, and it works — and it is also the point at which you should stop and read the next section.

7. When to Stop

Nested lists are the right structure when:

• rows have few columns, and
• the columns are fixed, and
• you mostly iterate rather than look things up.

They become the wrong structure when any of those stops being true, for one reason: the columns are identified by number.

lset table 2 1 128

That line requires you — and every future reader — to know that column 1 is the width. With two columns that is fine. With eight it is a lookup table in your head, and inserting a column at the front silently changes the meaning of every numbered access in the script.

8. Flattening

If you want the cells rather than the rows, concat flattens one level — Chapter 6.12:

set table {{clk 1} {reset 1}}

puts "rows:  [llength $table]"
puts "flat:  [concat {*}$table]"
puts "cells: [llength [concat {*}$table]]"

rows:  2
flat:  clk 1 reset 1
cells: 4

The {*} spreads the rows into separate arguments for concat — Chapter 6.13. Without it, concat $table would have nothing to flatten, because it would receive one argument.

9. Common Mistakes

Using lappend table $row and expecting the cells to merge. It adds one element — which here is correct. §2.

Forgetting the comparison mode with -index. Chapter 6.10 §5.

Numbered lindex calls instead of lassign. §4.

Letting a table grow past about four columns. §7.

Assuming llength counts cells. It counts the top level. §1.

Building rows by gluing text. Chapter 6.2.

10. Exercises

Exercise 1 — build a table. Create a three-row table of name and size using list and lappend, with one name containing a space. Confirm the row count and pull that name out.

Exercise 2 — cells. From {{a 1} {b 2} {c 3}}, print the value 2 using the multi-index form, then change it to 20 with lset.

Exercise 3 — walk it readably. Print a four-column table with foreach and lassign, formatted into columns. Then rewrite it with numbered lindex calls and say which you would rather maintain.

Exercise 4 — sort and find. Sort a table by its numeric second column descending, then find the row whose first column is a given name.

Exercise 5 — deeper. Build a two-level grouping as in §6 and reach a cell four levels down with one lindex.

Exercise 6 — the judgement call. You are storing, for each signal: name, width, direction, clock domain, reset type, and a description. Say whether you would use a list of lists or a dictionary, and give two reasons.

11. Remember

• A nested list is a list whose elements are lists. No special syntax — list quoting makes it work.
• llength counts the top level only.
• lindex $t 2 0 drills one level per index; lset $t 2 0 x writes the same cell.
• lsort -index and lsearch -index operate on a column, and lsort still needs the comparison mode.
• foreach plus lassign is the readable way to walk rows.
• concat {*}$table flattens one level.
• Columns are identified by number, which is fine for a few fixed ones and brittle otherwise.
• Once rows have several fields or fields may be added, use a dictionary — Module 7.

Next: the difference between combining lists and nesting them.