Version 4 of deep list

Updated 2019-10-14 13:06:31 by pooryorick

A deep list is a data format for representing an ordered tree: Each item in the list can be identified as either a simple value or a sequence of values. Because a simple value might look like a standard Tcl list, some care is needed.

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.

Description

Built-in Tcl list routines provide no grammar to distinguish between a list item that is a simple value and a list 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. If the data format is rich enough, this structure could be discoverable.

For an ordered tree the standard list notation provides information about the order. Information about whether an item is a single value or sequence of values is also needed. This additional information can be encoded as additional structure. A simple value is encoded as a list containing only one item. A value that doesn't look like a list containing only one item is itself interpreted as a deep list. The following example is a list containing two items:

one
{
    {{two three}}
    {two three}
}

The first item is the simple value one. The The second item is a list in which the first item is the value two three and the second item is a deep list containing the values two and three.

Looking again at that second item:

{{two three}}
{two three}

The first item is a list containing only one item, so its value is the value of that one item, e.g. two three. It is easily distinguishable from the second item, which is another deep list.

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

lappend tree [list $item]

means "this is not a nested structure", whereas

lappend tree $item

means "this is a nested structure if it looks like one."

Implementations such as ycl list deep that understand this structure supply routines that automatically unlist simple values when they are retrieved.