Version 2 of deep list

Updated 2019-10-13 13:56:56 by pooryorick

A deep list is a data format for representing an ordered tree: Each item in the list is either a simple 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.

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 itself a list. 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 self-describing data format provides information about the intepretation of the represented data. In a deep list, a simple value is encoded as a list containing only one item. All other values are considered to be sequences. 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 sequence where the first item is the simple value two three and whose second item is itself a sequence containing the values two and three.

Looking again at that second item:

{{two three}}
{two three}

It is clear that although the value of the first item, two three could itself be interpreted as a list, it is tagged as a single value, not a sequence.

Use list to tag each item that that is meant as a single value rather than a nested structure:

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."