A ''nested list'' is simply a list that occurs as an element of another list (which may of course itself be an element of another list, etc.).

Common reasons nested lists arise are:
   1. They're matrices (a list of rows, where each row is itself a list, or a list of columns where each column is itself a list).
   2. Lists are being used for what in other languages is known as structs, [record]s, or tuples -- collections of data with a fixed structure.
   3. A [tree] is encoded as a list where the subtrees occur as elements (hence lists are nested as deeply as the tree is high).

[[Discuss when using a nested list is important or useful - what are cases where it is a good solution]]

Before Tcl 8.4, nested lists were quite difficult to work with -- getting nested elements required nesting [lindex] commands, and the nightmare of setting elements in nested lists without the help of [lset] is better forgotten -- and as a result older code often uses [array]s even in cases where the first-class data status (being possible to pass by value) of a list would have been very useful. 


[[Discuss which Tcl built in commands can be used to build, search, and maintain the list]]

----
    * [split and join for nested lists]
    * [Trees as nested lists]
    * [Nested list join]
    * [Tables]

----
**[LISP]-style lists**

In [LISP], lists are built by linking "cons cells", which is simply a pair of values (typically implemented close to the hardware, e.g. as a C-struct of two pointers; a [Tcl_Obj] is a higher level concept) where the first (the head) by convention is the first list element and the second (the tail) is the rest of the list; in the last cell of a list the tail pointer is [NULL]. The following is (yet another) implementation of this, with Tcl lists of length 2 serving as cons cells. It is probably not of any practical interest.

'''FM''': Here some procs to build purely nested list which have a constant length of 2, the last member is always {}.

Purely right nested list (constant length of 2):
======
proc ligne args {
    set script {list}
    foreach e [lreverse $args] {
	set script [subst -noc -nob {list "{$e}" [$script]}]
    }
    uplevel $script
}

set L [ligne A B C] ;#	   {{A}} {{{B}} {{{C}} {}}}
llength [lindex $L] ;#	   2
llength [lindex $L 1] ; #       2
llength [lindex $L 1 1]; #      2
llength [lindex $L 1 1 1]; #    0 (so depth of the list = 3)
======
------
''[Lars H], 2008-11-14: You're mixing string and list operations quite wildly here; I strongly suspect it won't work for strange list elements (backslashes, strings not balanced with respect to braces). Also the technique of constructing a script for constructing a list is rather inefficient. Would I be right if I guessed that this is a direct attempt to emulate features of how lists are used in [LISP], e.g. with respect to variable substitution?''

FM, 2008-11-17: Ok, I see the problem. I don't know LISP myself, but if you guess ... 
It's more an exercice to show the properties of purely nested list of constant length of two. 
I used it to emulate a tiny vector, covector, tensor/matrix arithmetic (2D/3D, translation, rotation). 
By this way, it seems possible to distinguish between vector (convention : purely left nested list), covector (purely right nested list) and tensor (vector of covector i.e. purely left nested list of purely right nested list, or covector of vector i.e purely right nested list of purely left nested list). I put only simples strings in it (numbers, in fact). 
So you're right, let's make the precision : It works only for regulary strings, for little nested list, it is intended to be only use by the programmer, not to be feed with user data.

If you find a way two construct this with respect of all imaginable strings, and more efficently, you're welcome. 
Something like that, maybe ?
======
proc ligne args {
   set L [list ""]
   set i 0
   foreach e $args {
      lset L {*}$i [list [list $e] ""]
      lappend i 1
   }
   lindex $L 0
}
======
------
FM, We can test if a list is of this kind 
======
proc estLigne L {
    set res 1
    if {[llength $L]==2} {
	if {[llength [lindex $L 0]] == 1} {
	    set res [estLigne [lindex $L 1]]
	} else {
	    set res 0
	}
    } elseif {[llength $L] != 0} {
	if {[llength $L]==1 && $L eq ""} {
	    set res 1
	} else {
	    set res 0
	}
    }
    set res
}
estLigne $L;# 1
======
We can look at the depth
======
proc largeur L {
    if {[estLigne $L]} {
	set index [list]
	set l 0
	while {[llength [lindex $L $index]] == 2} {
	    set index [linsert $index 0 "1"]
	    incr l
	}
	set l
    } elseif {[estColonne $L]} {
	set res 1
    }
}
largeur $L; # 3
======
Purely left nested list (constant length of 2):
======
proc colonne args {
    set script {list}
    foreach e [lreverse $args] {
	set script [subst -noc -nob {list [$script] "{$e}"}]
    }
    uplevel $script
}
set C [colonne A B C]; #	{{{} {{C}}} {{B}}} {{A}}
llength [lindex $C]; #	  2
llength [lindex $C 0]; #	2
llength [lindex $C 0 0]; #      2
llength [lindex $C 0 0 0]; #    0 (so depth of the list = 3)
======
We can also test if a list is of this kind
======
proc estColonne C {
    set res 1
    if {[llength $C] == 2} {
	if {[llength [lindex $C 1]] == 1} {
	    set res [estColonne [lindex $C 0]]
	} else {
	    set res 0
	}
    } elseif {[llength $C] != 0} {
	if {[llength $C]==1 && $C eq ""} {
	    set res 1
	} else {
	    set res 0
	}
    }
    set res
}
estColonne $L; # 0
estColonne $C; # 1
======
We can look at the depth of the left nested list
======
proc hauteur L {
    if {[estColonne $L]} {
	set index ""
	set h 0
	while {[llength [lindex $L {*}$index]] == 2} {
	    set index [linsert $index 0 "0"]
	    incr h
	}
	set h
    } elseif {[estLigne $L]} {
	set res 1
    }
}
hauteur $L ;#   1
hauteur $C ;#   3
======
Now we should be able to search in those two kind of list (indexation to improve)
======
proc nlindex {L args} {
    set Res [list]
    foreach i $args {
	if {![string is digit $i]} {
	    puts stderr "index $i de format non valide dans nlindex $L {*}$args"
	    return
	}
    }
    if {[estLigne $L]} {
	#ligne
	set index 0
	if {[llength $args] == 0} {
	    # Tout afficher
	    for {set i 0} {$i < [largeur $L]} {incr i} {
		lappend Res {*}[lindex $L {*}$index]
		set index [linsert $index 0 "1"]
	    }
	    set Res [list $Res]
	} else {
	    # Afficher la coordonnée désirée
	    for {set i 0} {$i < $args} {incr i} { 
		set index [linsert $index 0 "1"]
	    }
	    set Res [lindex $L {*}$index]
	}
    } elseif {[estColonne $L]} {
	#colonne
	set index 1
	if {[llength $args] == 0} {
	    # Tout afficher
	    for {set i 0} {$i < [hauteur $L]} {incr i} {
		lappend Res {*}[lindex $L {*}$index]
		set index [linsert $index 0 "0"]
	    }
	    set Res [list $Res]
	} else {
	    # Afficher la coordonnée désirée
	    for {set i 0} {$i < $args} {incr i} { 
		set index [linsert $index 0 "0"]
	    }
	    set Res [lindex $L {*}$index]
	}
    } else {
	puts stderr "Objet $L non reconnu"
	return
    }
    return [lindex $Res 0]
}
puts "[nlindex $L]" ; # A B C
puts "[nlindex $L 0] [nlindex $L 1] [nlindex $L 2]" ;# A B C
puts "[nlindex $C]"; # A B C
puts "[nlindex $C 0]; # A
# ..etc
======
Of course we can mix up this two kinds of nested list :
======
set M [colonne [ligne a00 a01 a02] \
	       [ligne a10 a11 a12] \
	       [ligne a20 a21 a22] ]

======
We can test if a list is of one mixed type
======
proc estMatrice M {
    set res 1
    set dim -1
    if {[estColonne $M]} {
	for {set i 0} {$i < [hauteur $M]} {incr i} {
	    if {[estLigne [set Ligne [nlindex $M $i]]]} {
		if {$dim == -1} {
		    set dim [largeur $Ligne]
		} elseif {$dim != [largeur $Ligne]} {
#		    puts stderr "Objet non homogène en dimension : `$Ligne` est de dimension [largeur $Ligne] alors que $dim était attendu"
		    return 0
		}
	    } else {
#		puts stderr "Ligne $Ligne non valide"
		return 0
	    }
	}
    } elseif {[estLigne $M]} {
	for {set i 0} {$i < [largeur $M]} {incr i} {
	    if {[estColonne [set Colonne [nlindex $M $i]]]} {
		if {$dim == -1} {
		    set dim [hauteur $Colonne]
		} elseif {$dim != [hauteur $Colonne]} {
#		    puts stderr "Objet non homogène en dimension : `$Colonne` est de dimension [hauteur $Colonne] alors que $dim était attendu"
		    return 0
		}
	    } else {
#		 puts stderr "Colonne $Colonne non valide"
		return 0
	    }
	}
    } else {
	return 0
    }
    return "$res"
}
estMatrice $M ;# 1
======
We can look at the dimension of this mixed type (not complete)
======
proc dimension M {
    if {[estMatrice $M]} {
	if {[estColonne $M]} {
	    set dim [hauteur $M]
	    set Ligne [nlindex $M 0]
	    lappend dim [largeur $Ligne]
	} elseif {[estLigne $M]} {
	    set dim [largeur $M]
	    set Colonne [nlindex $M 0]
	    set dim [linsert $dim 0 [hauteur $Colonne]]
	} 
    } elseif {[estColonne $M]} {
	set dim [list [hauteur $M] 1]
    } elseif {[estLigne $M]} {
	set dim [list 1 [largeur $M]]
    } else {
	puts stderr "$M n'est pas une matrice"
	return 0
    }
    return $dim
}
dimension $M ; # 3 3
======
Searching in it this mixed type (to be completed)
======
proc mlindex {M {l {}} {c {}}} { 
    if {![estMatrice $M]} {return}
    lassign [dimension $M] height length
    if {$c eq {} && $l ne {}} {
	# une ligne est recherchée : Should-it be return in the nested form ?
	if {$l >= $height} {return}
	if {[estLigne $M]} {
	    for {set i 0} {$i < [largeur $M]} {incr i} {
		lappend Res [nlindex [nlindex $M $i] $l]
	    }
	    return $Res
	} elseif {[estColonne $M]} {
	    return [nlindex [nlindex $M $l]]
	}
    } elseif {$c ne {} && $l ne {}} {
	# une cellule est recherchée
	if {! ($l < $height && $c < $length) } {return}
	if {[estLigne $M]} {
	    return [nlindex [nlindex $M $c] $l]
	} elseif {[estColonne $M]} {
	    return [nlindex [nlindex $M $l] $c]
	}
    } elseif {$c ne {} && $l eq {}} {
	# une colonne est recherchée : Should-it be return in the nested form ?
	if {$c >= $length} {return}
	if {[estColonne $M]} {
	    for {set i 0} {$i < [hauteur $M]} {incr i} {
		lappend Res [nlindex [nlindex $M $i] $c]
	    }
	    return $Res
	} elseif {[estLigne $M]} {
	    return [nlindex [nlindex $M $c]]
	}
    } elseif {$c eq {} && $l eq {}} {
	# Maybe the list should flatten ?
	lindex $M
    }
}

mlindex $M 0; # a00 a01 a02
mlindex $M {} 0; # a00 a10 a20
mlindex $M 0 0; # a00
======
We can transpose one kind in another
======
proc transpose {L} {
    if {[estMatrice $L]} {
	lassign [dimension $L] h l
	lappend script ligne
	for {set i 0} {$i < $h} {incr i} {
	    lappend script "\[colonne {*}\[mlindex \$L $i\]\]"
	}
	eval $script
    } elseif {[estLigne $L]} {
	set index [list 0]
	for {set i 0} {"1"} {incr i} {	
	    if {[set e [lindex $L {*}$index]] ne {}} {
		lappend plat [join $e]
		set index [linsert $index 0 "1"]
	    } else {
		break
	    }
	    if {$i> 2000} break
	}
	colonne {*}$plat	
    } elseif {[estColonne $L]} {
	set index [list 1]
	for {set i 0} {"1"} {incr i} {	
	    if {[set e [lindex $L {*}$index]] ne {}} {
		lappend plat [join $e]
		set index [linsert $index 0 "0"]
	    } else {
		break
	    }
	    if {$i> 2000} break
	}
	ligne {*}$plat
    }
}

string eq [mlindex $M 0] [mlindex [transpose $M] {} 0]; # 1
string eq $L [transpose $C]; # 1
======
It's seems like if we can encode in the structure a distinction between vectors, covectors and matrix, no ?


----
!!!!!!
%| [Category Data Structure] |%
!!!!!!