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:
[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 arrays 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]
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;# 1We 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; # 3Purely 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; # 1We 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 ;# 3Now 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
# ..etcOf 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 ;# 1We 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 3Searching 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; # a00We 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]; # 1It's seems like if we can encode in the structure a distinction between vectors, covectors and matrix, no ?