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?''

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] |%
!!!!!!