deep list

A deep list is a data format for representing an ordered tree: Each item in the list can be identified as either a single value or a sequence of values.

See Also

list and Depth of a List
escargo ruminates about differentiating between a single value and a sequence of values in a list.
ycl list deep, by PYK
An implementation of a deep list. Provides index, insert, is struct, range, and set.


Built-in Tcl list routines provide no grammar to distinguish between a list item that is a single value and an item that is nested structure. The caller of lindex or lset dictates the desired interpetation by passing index arguments. Sometimes, however, the caller would like to discover the structure of the data rather than dictating it. A slightly richer format makes the structure discoverable.

The standard list notation already provides information about the order. To additionally provide Information about the structure of the tree, a single value is encoded as a list containing only one item. If a value is a list containing more than one item, then that value is itself interpreted as a deep list. The following value is a list containing two items:

    {{two three}}
    {two three}

The first item is the single value one. The The second item is a list in which the first item is the value two three encoded as a list containing one item, and the second item is a deep list containing the values two and three, each of which is already formatted as a list containing one value due to the nature of the representtion of a list.

Looking again at that second item in isolation:

{{two three}}
{two three}

The second item, which is a nested list, is easily distinguishable from the first item, which decodes to the single value two three.

When adding values to a list, use list to encode each item that that is meant as a single value rather than a sequence of values.

lappend tree [list $item]

means "$item is a single value", whereas

lappend tree $item

means "$item is a nested structure if it is a list containing more than one value."

Implementations such as ycl list deep that understand this structure supply routines that automatically decode single values as needed.