New list commands ... What do you think ?
mou...@igbmc.u-strasbg.fr
TIPs writing is an easy task for our TCL gurus, but not for a simple
guy like me !
So I prefer first to test the ideas on the list before entering the TIP
process. So please tell me what you think about that :
At first glance, Tcl may be characterized by the presence of only three
main data types : strings, lists and arrays. The list type gives an
elegant way to deal with collections.
Nevertheless, some basic functions are not present in the tcl core
commands to perform basic operations on lists like comparison,
uniquifying, reversing.
Inclusion of such commands in the Tcl core would re-enforce the
usefulness of the list datatype and consequently the Tcl identity.
Although these commands can be coded in pure Tcl, their C counterparts
would make them much more efficient.
The guideline of these commands is to emulate operands acting on
ensembles.
Here are the proposed commands:
- lequal $l1 $l2 : returns 1 if each elements of l1 is equal to
- land $l1 $l2 : returns the elements common to l1 and l2
- lor $l1 $l2 (= concat $l1 $l2)
- lxor $l1 $l2 : returns elements present in l1 and not in l2 as well
as those from l2 not in l1
- lcomplement $l1 $l2 returns the elements in l1 not in l2each elements
of l2, 0 if not
- lunique $l1 : returns a list with only unique elements (the first of
the repeated elements is taken with option -first or the last one with
-last)
- lreverse $l1 : return a list with elements in reverse order
- lconcat l1 $l2 (same as eval lappend l1 $l2)
Feel free to answer !!
-----------------------------------------------------------
Luc Moulinier, Ph.D
IGBMC, Laboratoire de Genomique et Biologie Integratives
1, rue laurent Fries
67 404 ILLKIRCH Cedex
Michael Schlenker
> Hello world !
>
>
> TIPs writing is an easy task for our TCL gurus, but not for a simple
> guy like me !
> So I prefer first to test the ideas on the list before entering the TIP
> process. So please tell me what you think about that :
>
> At first glance, Tcl may be characterized by the presence of only three
> main data types : strings, lists and arrays.
> The list type gives an
> elegant way to deal with collections.
> Nevertheless, some basic functions are not present in the tcl core
> commands to perform basic operations on lists like comparison,
> uniquifying, reversing.
> Inclusion of such commands in the Tcl core would re-enforce the
> usefulness of the list datatype and consequently the Tcl identity.
> Although these commands can be coded in pure Tcl, their C counterparts
> would make them much more efficient.
>
> The guideline of these commands is to emulate operands acting on
> ensembles.
> Here are the proposed commands:
Some of those commands already exist in either tcllib or the TclX extension.
>
> - lequal $l1 $l2 : returns 1 if each elements of l1 is equal to
Basically equivalent to either:
proc lequal {l1 l2} {
expr {$l1 == $l2 ? 1 : 0}
}
or more elaborate:
proc lequal {l1 l2} {
if {[llength $l1] != [llength $l2]} {return 0}
foreach a $l1 b $l2 {
if {$a == $b} {return 0}
}
}
This has the semantic problem that == may do the wrong thing for strings
and you would have to specifiy a comparision operator to make this useful.
> - land $l1 $l2 : returns the elements common to l1 and l2
See ::struct::set difference from tcllib
> - lor $l1 $l2 (= concat $l1 $l2)
Whats the difference to concat $l1 $l2 ?
> - lxor $l1 $l2 : returns elements present in l1 and not in l2 as well
> as those from l2 not in l1
see struct::set intersect3 from tcllib
> - lcomplement $l1 $l2 returns the elements in l1 not in l2each elements
> of l2, 0 if not
I don't understand the description.
> - lunique $l1 : returns a list with only unique elements (the first of
> the repeated elements is taken with option -first or the last one with
> -last)
Basically an lsort -unique which keeps ordering..., could be useful
sometimes..., should be added to struct::list
> - lreverse $l1 : return a list with elements in reverse order
struct::list reverese
This could be a good addition to the core, as it would be really fast in
C. (just iterating a C array in reverse and increasing the refcount of
the entries.)
> - lconcat l1 $l2 (same as eval lappend l1 $l2)
Bad name. And no real usecase, especially for Tcl 8.5 where you have
expand and can do:
lappend l1 {expand}$l2
So for i TIP i see lreverse, some of the others would be good in
struct::list.
Michael
MartinLemburg@UGS
I did a kind of lists package with some procedures I need:
More or less numerical/mathmatical/statistical procedures:
syntax: lmin //?-indices? list//
result: the "smallest" list element, or the indices of all "smallest"
list elements
syntax: lmax //?-indices? list//
result: the "largest" list element, or the indices of all largest
list elements
syntax: lleast //list//
result: the least occurrenced element
syntax: lmost //list//
result: the most occurrenced element
syntax: lweight //list ?string string?//
result: the weight of the given string inside the list, or a list
with nested lists containing all (given) strings and their weights
syntax: lcount //list ?string string?//
result: the occurrences count of the given string inside the list, or
a list with nested lists containing all (given) strings and their
weights
syntax: ladd //list value//
result: a list with all list elements of the given list, but in sum
with the given value
syntax: lmult //list value//
result: a list with all list elements of the given list multiplied
with the given value
syntax: lneg //list//
result: a list with all, but negated, list elements of the given list
syntax: ldiv //list value//
result: a list with all list elements of the given list divided by
the given value
syntax: linv //list//
result: a list with all inverted list elements of the given list
syntax: lprod //list//
result: the result of the multiplication of all elements into one
product
syntax: lsum //list//
result: the result of the sum of all elements
syntax: lmean //list//
result: the mean value of all values of the list
syntax: lvar //list//
result: the variance of all values of the list
syntax: lstdev //list//
result: the standard deviation of all values of the list
syntax: lcovar //list//
result: the covariance of all values of the list
syntax: lshortest //?-inline | -length? ?-listlength | -stringlength?
list//
result: the list index of the shortest list element, the shortest
list element itself or its (list) length
syntax: llongest //?-inline | -length? ?-listlength | -stringlength?
list//
result: a list of or a single list index of the longest list element,
the longest list element itself or its (list) length
syntax: ldelta //list value//
result: a list with deltas of each list element to the value
syntax: labsdelta //list value//
result: a list with absolute deltas of each list element to the value
syntax: lnear //list value//
result: the value, that is the nearest to the given value, or the
list values with the same distance to this given value
syntax: lequal //list1 list2//
result: a boolean value with 1 for being and 0 for not being equal -
each element/list is tested recursively
Procedures for reorganizing or boolean operations:
syntax: lunique //list//
result: the list in its original order, but without duplicate
elements
syntax: lreverse //list//
result: the same list elements, but in a reversed order to the
original given list
syntax: lremove //?-all? list pattern ?pattern ...?//
result: the same list like the given, but excluding (all of) the
patterns matching elements
syntax: lsubstract //list list ?list ...?//
result: a list with all the elements of the first list, that are none
of the other lists
syntax: lintersect //list list ?list ...?//
result: the intersection of all given lists, or all list elements of
all lists, that are contained in all lists
syntax: lmix //list1 list2//
result: a new list composed out of the two given lists - **lmix**
//{a b c} {0 1 2}// = {a 0 b 1 c 2}
syntax: lmerge //list ?list ...?//
result: a list without any nested lists (concatenated using all given
lists)
syntax: lsortout //list varName expression//
result: a list with all the list elements qualified by the test
condition or command
A search procedure:
syntax: lrsearch //list element//
result: a list of indices per nest level of the given nested list
being the path to the found elements inside the nested list - to be
used with lindex or lset in tcl 8.4+
A list creating procedure:
syntax: lsequence start test next command
result: a list created by evaluating the given command from the start
to the failed test condition
Working on/or with lists:
syntax: lexpr //list ?indexVarName? elementVarName expression//
result: a list with each element as result of the given lists
elements and the given expression
syntax: lmap //list ?indexVarName? elementVarName command//
result: a list as result of evalualting each given lists element with
the command
syntax: leval //command list ?list ...?//
result: a list as result of evalualting the command with every
element with the same index of the given lists as often as the length
of the longest list
Creating a verbose list output like 'parray' does:
syntax: plist //?channel? listVarName//
result: nothing
Stack like procedures (in memoriam of my HP48):
syntax: lshift //list ?count?//
result: a new list with out the first //count// elements
syntax: lrotate //(-left | -right) list ?count?//
result: a new list where a given count of elements rotated from the
beginning to the end (//-left//) or from the end to the beginning
(//-right//) of the given list
syntax: lswap //list ?position1 ?position2??//
result: a new list where the elements at the given positions are
exchanged
syntax: lswapn //list ?count? ?position1 ?position2??//
result: a new list where the elements of the given count at the given
positions are exchanged
syntax: lcopy //list start end destination//
result: a new list with a duplicated range of the given list
beginning at the given destination
syntax: lcopyn //list start count destination//
result: a new list with a duplicated range of the given list
beginning at the given destination
syntax: lduplicate //list ?start? ?end?//
result: a new list with the duplicated given range of the given list
at the beginning of the given list
syntax: lduplicaten //list ?count? ?start?//
result: a new list with the duplicated given range of the given list
at the beginning of the given list
syntax: lrangen //list start count//
result: a new list containing only the given range
Some of them would really be nice to have them in the core!
But I think this discussion would be endless!
Best regards,
Martin
suchenwi
I'd rather love it if the number of commands in Tcl could be reduced,
without losing functionality. Examples:
[eval] could be just an alias to [uplevel 0]
If [lrange] had an optional "to" index, defaulting to "from" if not
given, it could serve as [lindex] as well (ok, nested indices would
have to be taken care of then).
But in general, every new command added to the Tcl core runs the risk
of conflicting with a user-written one. so I'd suggest to do that very
cautiously. Extending existing commands with new options is more
robust, as was demonstrated in [lsearch] whose switches are on the way
to a data retrieval language in itself :^)
lsearch -inline -all -sorted -increasing -dictionary -start $from
-exact -not $list $element
Gerald W. Lester
TclLib and tell us if you are attempting to describe its functionality.
If I'm reading you correctly, you seem to equate list with sets -- and the
two are not the same. List have order and it is very valid for an element
to be duplicated. Sets have neither of those properties.
On a different note -- NO to lthis and lthat!!!! Make a new command with
subcommands, e.g. listcmds this.
--
+--------------------------------+---------------------------------------+
| Gerald W. Lester |
|"The man who fights for his ideals is the man who is alive." - Cervantes|
+------------------------------------------------------------------------+
Donald Arseneau
> First off, I'd strongly suggest playing with the ::struct::set package in
> TclLib and tell us if you are attempting to describe its functionality.
>
> If I'm reading you correctly, you seem to equate list with sets --
>
> On a different note -- NO to lthis and lthat!!!! Make a new command with
> subcommands, e.g. listcmds this.
Since they are really set-specific operations, he should make a
new omnibus command [set].
;-)
--
Donald Arseneau as...@triumf.ca
Eckhard Lehmann
mou...@igbmc.u-strasbg.fr wrote:
> Nevertheless, some basic functions are not present in the tcl core
> commands to perform basic operations on lists like comparison,
> uniquifying, reversing.
I also would like to have more list commands. Of course, most of the
functionality I frequently need can be obtained by circumstantial use
of existing commands, e.g.
[expr {[lsearch $list $elem] >= 0}]
instead of
[lcontain $list $elem]
But why do it the hard way over and over?
Tclx contains some of the commands you propose, and I think they should
be reviewed and eventually go into the core. In addition to them I'd
propose more commands for functional programming on lists, e.g. an
[lmap] command, that applies a function to every element in the list...
Eckhard
suchenwi
Donald Arseneau schrieb:
> Since they are really set-specific operations, he should make a
> new omnibus command [set].
>
>
> ;-)
Which of course would break just about every Tcl script ever in
existence...
Michael Schlenker
> mou...@igbmc.u-strasbg.fr wrote:
>
>> Nevertheless, some basic functions are not present in the tcl core
>> commands to perform basic operations on lists like comparison,
>> uniquifying, reversing.
>
> I also would like to have more list commands. Of course, most of the
> functionality I frequently need can be obtained by circumstantial use
> of existing commands, e.g.
>
> [expr {[lsearch $list $elem] >= 0}]
>
> instead of
>
> [lcontain $list $elem]
>
> But why do it the hard way over and over?
> Tclx contains some of the commands you propose, and I think they should
> be reviewed and eventually go into the core. In addition to them I'd
> propose more commands for functional programming on lists, e.g. an
> [lmap] command, that applies a function to every element in the list...
Those can be found in tcllib struct::list
Michael
MartinLemburg@UGS
yes - sometimes its about overengineering.
Otherwise it is about readability and modularization of code.
And there is probably the need/force to use as less "external" software
as possible - its about responsibility of maintaince, bugfixes,
reachability of the responsable developers of external software, the
need for performance increasements, etc..
And etc..
For me, there are some real candiates for including into the core. And
for me it is more kind of development/improvement the core would go
through, than a needless extension with the risk to break existing
scripts.
If new core commands breaks existing scripts, and if those commands
offers basic functionality (like lmap), than the developers must live
with this, because they wrote basic functionality (like many do), that
may be introduced by the core later on!
That's the risk of every developer (re)writing basic commands.
Another point is, that I don't want to know how many times the wheel
was reinvented instead of reused!
To use the tcllib is IMHO only second best, if the needed functionality
is so fundamental and basic, that it should be provided by the core,
not by a thirdparty extension.
My first reply was to show how may commands could be needed and to
allow some discussion about some of them, that are really good for core
introduction, like:
lunique - to replace the list order changing "lsort -unique ..."
lremove - deleting all pattern matching elements of a list
lreverse - reversing list order
lintersect - returning the intersection of n lists
lsubtract - subtracting n lists from the first list
lmap - using each element of a list in a script body and
collecting the result of the script body
leval - using each element of n lists (1st of all, 2nd of all, ...)
to evaluate a command with those elements as arguments and
collecting the result of the command evaluation
Some other commands are so near to mathematics, especially to
statistics, that they could be collected e.g. in tcllib, which is
perhabs already done.
But there the questions is ... why not providing binary standard
extensions like already done with "dde" or "registry"? Why not a
"stat(istic)s" extension? Some of the tcllib extensions are very
runtime consuming and could be done more efficiencly in C using the tcl
C API.
(Yes, I know that e.g. md5 falls back to use the critcl variant of the
md5 package, which is very quick. But only if critcl is installed! Why
not providing time critical packages completely in C?)
For me the arguments for integrating more binary extensions, like e.g.
"dde", into the core tcl distribution (not ActiveTcl) are that:
* providing basic mathmatics (expr command) is not enough for many
applications, so everybody reinvents e.g. a new vector/matrix algebra
package. But statstics or vector/matrix algebra are IMHO basic
mathmatic areas too! That's a reason for me to wanting them not in the
core, but with the core.
* some of the mentioned areas of functionality
(vectors/matrices/statistics/...) needs intensive calculations and are
better done in C(++). Let those binary extensions provide a typical tcl
command interface and ship them as standard extensions with the tcl
core
* critcl is for me not a solution in getting binary extensions from
within tcl. It makes the system more complex than needed and is
supports not all OS' and not our compiler/linker system to be used
(VC7.1/8.x).
Perhabs this reply looks a bit confuse ... I was not able to write it
in one turn, so please excuse redundances!
Best regards,
Martin Lemburg
UGS - Transforming the Process of Innovation
MartinLemburg@UGS
> functionality I frequently need can be obtained by circumstantial use
> of existing commands, e.g.
>
> [expr {[lsearch $list $elem] >= 0}]
>
> instead of
>
> [lcontain $list $elem]
>
> But why do it the hard way over and over?
It's not only to be lazy, not wanting the "hard way".
If I have 100 occurrence or more of a complex, hard-to-read tcl
construct, which could have a name, than I prefer to create a procedure
with that name and to provide the complex construct per name.
In the case of a bug or a change of concept, there is then only one
place to change not 100s or more.
So I have such procedures like "lcount", "lweight", etc..
Michael Schlenker
> Hi Richard,
>
> yes - sometimes its about overengineering.
>
> Another point is, that I don't want to know how many times the wheel
> was reinvented instead of reused!
> To use the tcllib is IMHO only second best, if the needed functionality
> is so fundamental and basic, that it should be provided by the core,
> not by a thirdparty extension.
we just install it, nothing would really change (other than one download
instead of two), but you were happy?
>
> My first reply was to show how may commands could be needed and to
> allow some discussion about some of them, that are really good for core
> introduction, like:
>
interp alias {} lremove {} lsearch -all -not -inline
set new [lremove $list $pattern]
>
> Some other commands are so near to mathematics, especially to
> statistics, that they could be collected e.g. in tcllib, which is
> perhabs already done.
Probably, there are quite some math:: packages in Tcllib.
>
> But there the questions is ... why not providing binary standard
> extensions like already done with "dde" or "registry"? Why not a
> "stat(istic)s" extension? Some of the tcllib extensions are very
> runtime consuming and could be done more efficiencly in C using the tcl
> C API.
>
> (Yes, I know that e.g. md5 falls back to use the critcl variant of the
> md5 package, which is very quick. But only if critcl is installed! Why
> not providing time critical packages completely in C?)
This isn't true. Critcl builds a package which is loaded. You don't need
the critcl package to use it, just to build it.
>
> For me the arguments for integrating more binary extensions, like e.g.
> "dde", into the core tcl distribution (not ActiveTcl) are that:
>
> * providing basic mathmatics (expr command) is not enough for many
> applications, so everybody reinvents e.g. a new vector/matrix algebra
> package. But statstics or vector/matrix algebra are IMHO basic
> mathmatic areas too! That's a reason for me to wanting them not in the
> core, but with the core.
> * some of the mentioned areas of functionality
> (vectors/matrices/statistics/...) needs intensive calculations and are
> better done in C(++). Let those binary extensions provide a typical tcl
> command interface and ship them as standard extensions with the tcl
> core
Thats basically a policy problem.
1. Tcllib ships with pure Tcl code to be portable but explicitly allows
accelerator code, _if_ a pure Tcl version is provided. That prohibits
the lazy wrapping of code with swig etc. to enter the standard lib, like
it happens with PHP all the time (see how huge but crude their API is
often).
2. The bundling of more packages with the Tcl core would only fix the
mistakes of packagers which don't include Tcllib (including the built
accelerator packages) or other useful packages with their systems.
So what you propose is changing the core style from 'lean and mean' to
'fat and powerful' aka 'batteries included'. Won't happen. Could also
revive the package repository discussion in this context.
> * critcl is for me not a solution in getting binary extensions from
> within tcl. It makes the system more complex than needed and is
> supports not all OS' and not our compiler/linker system to be used
> (VC7.1/8.x).
>
What is a better and simpler cross platform solution for getting binary
extensions? TEA with the whole auto* toolchain?
You know that you could fix critcl to work with your compiler?
Michael
John Perry
> ...
> And there is probably the need/force to use as less "external" software
> as possible - its about responsibility of maintaince, bugfixes,
> reachability of the responsable developers of external software, the
> need for performance increasements, etc..
> And etc..
>
As I've mentioned before, I prefer the minimalist approach: a
fundamental language stub, and everything else -- expr, most list
commands, most string commands, etc. --in loadable extensions,
including most of what's presently in the core.
Having most of the function in extensions hasn't hurt C or perl, for
instance -- users are simply told up front that most functions are not
in the language, but here's how to get them. From what I've read here,
tcl seems to have started out that way, then swelled to its present size
and shape.
It should also be easier to maintain, since there wouldn't be the
temptation to crosslink between commands to save a few lines of code. A
particular bug in one command could be fixed without worrying about its
possible effect on another command that happens to use the same block of
code.
Yes, the overall size would increase slightly. But it wouldn't be
necessary to include the entire codebase in every program, and it would
be easier to write specialized programs with standard commands optimized
for your own environment.
John Perry
Donal K. Fellows
> For me, there are some real candiates for including into the core. And
> for me it is more kind of development/improvement the core would go
> through, than a needless extension with the risk to break existing
> scripts.
Well, none of them really meet the criteria for the core for me since
they can go in an extension and go just as fast. Even [lreverse] is like
this, and that's the second best candidate as Tcl doesn't currently have
any command to reverse things at all.
> Another point is, that I don't want to know how many times the wheel
> was reinvented instead of reused!
But reinventing the wheel because you won't consider third-party tyres
is more than a bit dumb. :-D
> lmap - using each element of a list in a script body and
> collecting the result of the script body
This one is interesting, but would need careful design. The reason it is
interesting is that it stands the biggest chance of gaining from going
in the core. But it's not certain; it's possible in 8.5a4 to build a
fast version that doesn't need to sit inside the core.
Donal.
suchenwi
>
> But reinventing the wheel because you won't consider third-party tyres
> is more than a bit dumb. :-D
>
organized into some "utility" library - things like
proc K {a b} {set a}
proc in {list element} {expr {[lsearch -exact $list $element]>=0}}
proc every {ms body {eval $body; after $ms [info level 0]}
just because I put high value in self-contained scripts - both because
you don't have to bother for libraries when deploying, and because if
such definitions are in the same file, it's easiest to look them up.
stephan...@yahoo.fr
> Hi,
>
> I did a kind of lists package with some procedures I need:
> Stack like procedures (in memoriam of my HP48):
> syntax: lshift //list ?count?//
> syntax: lrotate //(-left | -right) list ?count?//
> syntax: lswap //list ?position1 ?position2??//
> syntax: lswapn //list ?count? ?position1 ?position2??//
> syntax: lcopy //list start end destination//
> syntax: lcopyn //list start count destination//
> syntax: lduplicate //list ?start? ?end?//
> syntax: lduplicaten //list ?count? ?start?//
> syntax: lrangen //list start count//
Hi,
Stack-like procedures are powerful for a Forth-like language,
a language in which the stack is central to the language.
I am not against Forth-like languages, but since Tcl does not
behave like such, this approach implies something really different.
At some time, I experimented about the concept of what
I called 'Tcl-Rpn'. (see 'Numerical Rpn' on the Tcler's Wiki)
It is mainly inspired by the HP48 RPN.
I thought this could be, when implemented in C, a way
to perform with great speed some binary/vector/matrix ops.
But I did not even the first step to rewrite it in C, although
the language seemed to me the most Tclish way to improve
perfs in the mathematical feature corner.
This is why I say : Tcl is not Forth, Tcl-Rpn could be it enough!
Regards,
Stéphane
Donal K. Fellows
> This is why I say : Tcl is not Forth, Tcl-Rpn could be it enough!
The main problem with going to a RPN form of language is that it makes
doing variadic operations/functions/commands more difficult. Tcl's great
support for such things is one of the nicer features of the language,
and it's just there, quietly being useful to everyone. Compare and
contrast with the mess that many other languages get into one way or
another... :-)
(The RPN concept is still a neat one. It's just not an unalloyed positive.)
Donal.
Neil Madden
> MartinLemburg@UGS wrote:
>> lmap - using each element of a list in a script body and
>> collecting the result of the script body
>
>
> This one is interesting, but would need careful design. The reason it is
> interesting is that it stands the biggest chance of gaining from going
> in the core. But it's not certain; it's possible in 8.5a4 to build a
> fast version that doesn't need to sit inside the core.
If you were going to put just one such function in, I'd vote for a
left-fold operation, as it is possible to implement map, filter, etc all
in terms of foldl (e.g. as shown at http://wiki.tcl.tk/15271). Unlike
the tcllib function, I'd change the argument order to be [lfold $cmd $id
$list], for easy use with interp alias (see http://wiki.tcl.tk/fold).
-- Neil
stephan...@yahoo.fr
> stephan...@yahoo.fr wrote:
> > This is why I say : Tcl is not Forth, Tcl-Rpn could be it enough!
>
> The main problem with going to a RPN form of language is that it makes
> doing variadic operations/functions/commands more difficult. [...]
I don't want to bash Tcl in favor of another language, it is just
an extension for a Rpn language, written using the Tcl C API :-)
Just like [expr], there might be a [rpn] command to handle maths
computations and algorithms. I think about it like if
I had a HP48 calculator as a Tcl command, I guess.
Regards,
Stéphane
Donal K. Fellows
> If you were going to put just one such function in, I'd vote for a
> left-fold operation, as it is possible to implement map, filter, etc all
> in terms of foldl (e.g. as shown at http://wiki.tcl.tk/15271). Unlike
> the tcllib function, I'd change the argument order to be [lfold $cmd $id
> $list], for easy use with interp alias (see http://wiki.tcl.tk/fold).
You don't need it in the core. Seriously. Not with the [apply] machinery
now in 8.5. While [apply] itself isn't byte-compiled, though its first
argument is, and so using Tcl_EvalObjv() should allow the construction
of an efficient solution to the problem purely in non-core code. :-)
Donal.
Joe English
>Neil Madden wrote:
>> If you were going to put just one such function in, I'd vote for a
>> left-fold operation, as it is possible to implement map, filter, etc all
>> in terms of foldl (e.g. as shown at http://wiki.tcl.tk/15271). Unlike
>> the tcllib function, I'd change the argument order to be [lfold $cmd $id
>> $list], for easy use with interp alias (see http://wiki.tcl.tk/fold).
>
>You don't need it in the core. Seriously. Not with the [apply] machinery
>now in 8.5.
[apply] doesn't help a whole lot for the combinator-style
type of programming Neil is talking about.
You could do something like:
proc foldl {proc init list} {
foreach element $list {
set init [apply $proc $init $element]
}
return $element
}
but using this definition of 'foldl' isn't as convenient as it
could be, since the caller needs to construct lambda(like) expressions
whenever calling it:
proc sum {list} { foldl [list {x y} {expr {$x+$y}] 0 }
proc product {list} { foldl [list {x y} {expr {$x*$y}] 1 }
A more useful primitive IMO would be something like
[call $cmd $arg1 ... $argN], which interprets $cmd as
a command prefix, appends $arg1 ... $argN, and invokes
the resulting command.
Implementing [foldl], [map], et al. in terms of [call] instead
of [apply] can yield very concise code -- especially in combination
with TIP#174 ("Math Operators as Commands"):
proc sum {list} { foldl + 0 $list }
proc product {list} { foldl * 1 $list }
or even:
alias sum foldl + 0
alias product foldl * 1
(where 'alias' is a variant of [interp alias] that operates on
the current interp only).
This style of programming is familiar to Haskell and ML users;
once you get the hang of it it makes code much easier to read
and write. Tcl can *almost* support this style very well; all
that's missing is a "call" primitive or something similar.
(In 8.5, this could be "proc call {cmd args} { {expand}$cmd {expand}$args }";
there's really no good way to implement it in 8.4. "[eval]" only
cuts it if you're not worried about safety or efficiency.)
--Joe English
Neil Madden
[...]
> A more useful primitive IMO would be something like
> [call $cmd $arg1 ... $argN], which interprets $cmd as
> a command prefix, appends $arg1 ... $argN, and invokes
> the resulting command.
This would be pretty useful. Possibly being able to specify the level to
call in would also be useful, as in most of these combinators you
usually want the call to occur in either the caller's scope (i.e. same
as [uplevel 1]) or in the global scope.
[...]
> This style of programming is familiar to Haskell and ML users;
> once you get the hang of it it makes code much easier to read
> and write. Tcl can *almost* support this style very well; all
> that's missing is a "call" primitive or something similar.
Well, I'd prefer to have foldl implemented in C as it is likely to be a
critical loop in many places. It's actually not too difficult to
implement reasonably efficiently in C (where Tcl_EvalObjv stands-in for
"call"):
/*
* fold.c --
*
* Fast C implementation of a foldl construct.
*
* Copyright (C) 2006 Neil Madden <n...@cs.nott.ac.uk>
*
* License: Tcl-style.
*
* RCS: @(#) $Id$
*/
#include <tcl.h>
static int
FoldCmd(
ClientData cdata, /* Unused. */
Tcl_Interp *interp,
int objc,
Tcl_Obj *CONST objv[])
{
int itemc, i, cmdLen, newObjc;
int result = TCL_OK;
Tcl_Obj **items;
Tcl_Obj *id;
Tcl_Obj **cmd, **newObjv;
if (objc != 4) {
Tcl_WrongNumArgs(interp, 1, objv, "proc id list");
return TCL_ERROR;
}
id = objv[2];
Tcl_IncrRefCount(id);
/* Extract command prefix. */
if (Tcl_ListObjGetElements(interp, objv[1], &cmdLen, &cmd)
!= TCL_OK)
{
return TCL_ERROR;
}
/* Allocate new array to hold command prefix + id + element */
newObjc = cmdLen + 2;
newObjv = (Tcl_Obj **)
ckalloc((unsigned) (newObjc * sizeof(Tcl_Obj *)));
/* Copy command prefix into new array. */
for (i = 0; i < cmdLen; ++i) {
newObjv[i] = cmd[i];
Tcl_IncrRefCount(newObjv[i]);
}
/* Extract items from list. */
if (Tcl_ListObjGetElements(interp, objv[3], &itemc, &items)
!= TCL_OK)
{
return TCL_ERROR;
}
/*
* Loop through the list, applying the procedure to the current
* item and the accumulator (which is initialised to the "id"
* argument).
*/
for (i = 0; i < itemc; ++i) {
newObjv[cmdLen] = id;
newObjv[cmdLen+1] = items[i];
result = Tcl_EvalObjv(interp, newObjc, newObjv,
TCL_EVAL_GLOBAL);
switch (result) {
case TCL_OK:
case TCL_CONTINUE:
/* Continue to next element. */
Tcl_DecrRefCount(id);
id = Tcl_GetObjResult(interp);
Tcl_IncrRefCount(id);
break;
case TCL_BREAK:
/* Abort loop with current value. */
goto done;
default:
/* Error. */
goto done;
}
}
done:
for (i = 0; i < cmdLen; ++i) {
Tcl_DecrRefCount(newObjv[i]);
}
ckfree((char *) newObjv);
Tcl_DecrRefCount(id);
return result;
}
int
Fold_Init(Tcl_Interp *interp)
{
if (Tcl_InitStubs(interp, "8.4", 0) == NULL) {
return TCL_ERROR;
}
Tcl_CreateObjCommand(interp, "foldl", FoldCmd, NULL, NULL);
Tcl_PkgProvide(interp, "foldl", "0.1");
return TCL_OK;
}
With this compiled and loaded, the other sum, product etc can be defined:
proc def {name = args} {
interp alias {} $name {} {expand}$args
}
foreach op {+ - * /} { proc $op {a b} " expr {\$a $op \$b} " }
def sum = foldl + 0
def prod = foldl * 1
# For comparison:
proc prod2 list {
set id 1
foreach item $list { set id [* $id $item] }
return $id
}
set test [list]
for {set i 0} {$i <= 100} {incr i} { lappend test $i }
time { prod $test } 100 ;# -> 1670.53 us per iteration
time { prod2 $test } 100 ;# -> 1868.18 us per iteration
So, foldl is competitive with a hand-coded foreach solution (slightly
faster even).
Map and filter are easy to define:
proc map {proc list} { foldl [list map-helper $proc] [list] $list }
proc map-helper {proc accum item} {
lappend accum [{expand}$proc $item]
}
proc filter {proc list} {
foldl [list filter-helper $proc] [list] $list
}
proc filter-helper {proc accum item} {
if {[{expand}$proc item]} {
lappend accum $item
}
return $accum
}
These are quite a bit slower than the hand-coded foreach equivalents
though. An extra proc invocation seems to really slow things down.
-- Neil
Sektor van Skijlen
> lunique - to replace the list order changing "lsort -unique ..."
lsort -unique is short enough and searching for duplicates without sorting is
rather hard to imagine ;)
> lremove - deleting all pattern matching elements of a list
And lremove -if ? :)
> leval - using each element of n lists (1st of all, 2nd of all, ...)
> to evaluate a command with those elements as arguments and
> collecting the result of the command evaluation
How does that differ from [foreach]? ;)
--
// _ ___ Michal "Sektor" Malecki <sektor(whirl)kis.p.lodz.pl>
\\ L_ |/ `| /^\ ,() <ethouris(O)gmail.com>
// \_ |\ \/ \_/ /\ C++ bez cholesterolu: http://www.intercon.pl/~sektor/cbx
"I am allergic to Java because programming in Java reminds me casting spells"
MartinLemburg@UGS
Sektor van Skijlen wrote:
> Dnia 7 Jul 2006 01:46:57 -0700, MartinLemburg@UGS skrobie:
> > lunique - to replace the list order changing "lsort -unique ..."
>
> lsort -unique is short enough and searching for duplicates without sorting is
> rather hard to imagine ;)
Really?
I have often to maintain the order in lists of "found" objects, than
can have duplicate occurrences, but should occur only once.
Why is it so hard to imagine to have a "unique" list without the wish
to sort the list?
>
> > lremove - deleting all pattern matching elements of a list
>
> And lremove -if ? :)
Ok - there is in my lists procedure library a duplicate, that is called
lsortout, using conditions/expressions to determine those list
elements, that have to be sorted out/removed.
> > leval - using each element of n lists (1st of all, 2nd of all, ...)
> > to evaluate a command with those elements as arguments and
> > collecting the result of the command evaluation
>
> How does that differ from [foreach]? ;)
It uses no local variables and needs a command/script able to work with
up to n arguments, that are the n elements of n lists. That's different
enough!
Best regards,
Martin
suchenwi
Sektor van Skijlen schrieb:
> Dnia 7 Jul 2006 01:46:57 -0700, MartinLemburg@UGS skrobie:
> > lunique - to replace the list order changing "lsort -unique ..."
>
> lsort -unique is short enough and searching for duplicates without sorting is
> rather hard to imagine ;)
In fact, it's faster without sorting (O(n) vs. O(n**2) iirc),
especially when using a local hash like this:
proc luniq lst {
set res {}
foreach e $lst {
if ![info exists a($e)] {
set a($e) ""
lappend res $e
}
}
set res
}
125 % luniq {hello world and hello again}
hello world and again
> > lremove - deleting all pattern matching elements of a list
>
> And lremove -if ? :)
This can be had with [lsearch] today, waving many flags:
30 % lsearch -all -inline -exact -not {hello foo and foo again} foo
hello and again
> > leval - using each element of n lists (1st of all, 2nd of all, ...)
> > to evaluate a command with those elements as arguments and
> > collecting the result of the command evaluation
>
> How does that differ from [foreach]? ;)
In that it collects, saving the user typing the boring
set res {}
foreach ... {
lappend res ...
}
return $res
Kaitzschu
> Sektor van Skijlen schrieb:
>
>> lsort -unique is short enough and searching for duplicates without
>> sorting is rather hard to imagine ;)
>
> In fact, it's faster without sorting (O(n) vs. O(n**2) iirc), especially
> when using a local hash like this:
>
> proc luniq lst {
> set res {}
> foreach e $lst {
> if ![info exists a($e)] {
> set a($e) ""
> lappend res $e
> }
> }
> set res
> }
> 125 % luniq {hello world and hello again}
> hello world and again
Well, that depends really on what kind of sorting you do. Maybe 8.5 has
turned the tables, that I wouldn't know. My approach was to "unsort" the
"sorted", that can be done since we know that [lsort -unique] gives the
last ones it finds.
[code]
package require Tcl 8.5
proc ulst {lst} {
set s1 -1
set s2 [llength $lst]
while {[incr s1] < [incr s2 -1]} {
set _t [lindex $lst $s1]
lset lst $s1 [lindex $lst $s2]
lset lst $s2 $_t
}
set ulst [list]
foreach i [lsort -integer -decreasing [lsort -unique -indices $lst]] {
lappend ulst [lindex $lst $i]
}
return $ulst
}
proc luniq lst {
set res {}
foreach e $lst {
if ![info exists a($e)] {
set a($e) ""
lappend res $e
}
}
set res
}
proc luniq2 {lst} {
set res [list]
set a [dict create]
foreach e $lst {
if {![dict exists $a $e]} {
dict set a $e 0
lappend res $e
}
}
return $res
}
ulst {}
luniq {}
luniq2 {}
set tlst [list]
for {set i 0} {$i < 250} {incr i} {lappend tlst [expr {int(5*rand())}]}
puts "luniq: [time {luniq $tlst} 250]"
puts "ulst: [time {ulst $tlst} 250]"
puts "luniq2: [time {luniq2 $tlst} 250]"
[/code]
Hashing one is slooow
luniq: 76618.988 microseconds per iteration
when compared to "sorting" one
ulst: 13758.508 microseconds per iteration
and even "hashing done right" is a bit slower,
luniq2: 19068.696 microseconds per iteration
so, what, 2*O(n**2) is better than O(n)? :)
--
-Kaitzschu
Bruce Hartweg
in both cases) you data is for an "n" of 250 - try it with
larger "n"s and see what happens.
Bruce
Kaitzschu
> Kaitzschu wrote:
>> so, what, 2*O(n**2) is better than O(n)? :)
>>
> that depends on the value of n (and the size of the constants in both
> cases) you data is for an "n" of 250 - try it with larger "n"s and see
> what happens.
My confusion arose from that I thought 2*O(n**2) could never be less than
O(n) when n is constant (and greater than one). But I had two things
wrong. First, [lsort] is not O(2**n) but O(n log n). Second, [ulst] isn't
really 2*O(n**2) but more like O(n/2)+O(n log n)+O(u log u)+O(u). Thirdly,
[luniq2] isn't really O(n), either, but it makes no difference.
Combining those two it is somewhat obvious that [ulst] can beat [luniq2],
but only with rather special lists.
My bad, once again.
--
-Kaitzschu
s="TCL ";while true;do echo -en "\r$s";s=${s:1:${#s}}${s:0:1};sleep .1;done