'''lreverse''' ''list''

Returns a list containing the elements of its argument, ''list'', in reverse order.

http://www.tcl.tk/man/tcl8.5/TclCmd/lreverse.htm

----
Implemented in the [changes in Tcl/Tk 8.5] as part of [TIP] #272[http://tip.tcl.tk/272.html].

Downward compatible [pure-Tcl] version:
 proc lreverse list {
    set res {}
    set i [llength $list]
    while {$i > 0} {lappend res [lindex $list [incr i -1]]}
    set res
 } ;# RS

----
[LEG]: List reversion is used e.g. in functional programming [map] and [reduce] or [fold] respectively.
Therefore execution time and memory requirements are important issues.

In fact the above Tcl version is the fastest implementation.  To make backwards compatible code
with lreverse you can use the following boilerplate code, which squeezes out some more microseconds
by reducing one bracket evaluation in the loop.

 if {[info command lreverse] == ""} {
     proc lreverse l {
         set r {}
         set i [llength $l]
         while {[incr i -1]} {lappend r [lindex $l $i]}
         lappend r [lindex $l 0]
     }
 }

At the moment of this writing there are little references to [lreverse] in the wiki, which indicates
that until now, everybody has reverted his/her list 'by hand'.

The following is an ad nauseam exploration of [pure-Tcl] lreverse.  You can just skip to the section
''Consolidated timing results'' for some numbers.  There you find all implementations listed in order
of execution time for a small list.  It is very interesting to see, that the ordering by the second
column - reverting a longer list - would be different. Obviously the builtin version wins by magnitudes,
on long lists, since no function calls are needed between iterations.
The main surprise however is, that the dumb [concat]/[list] implementation of ''lreverse2'' scales much better
on longer lists than [lset] and, worse, [linsert] which are used in ''lreverse6'' and ''lreverse5'' respectively.
The big winner, however is the countdown while loop, which given in the above form is even slightly faster.

It would be interesting to time the tail recursive implementations ''lreverse7'' and ''lreverse8'' with [Tail call optimization].

The use of the new (as in Tcl8.5) [{*}] syntax in ''lreverse8'' does not provide better speed, the standard
implemention with [lindex]/[lrange] in ''lreverse7'' is arguably uglier but faster on long lists.
----
 # LEG20081207: list reverse in comparision
 # default quiet version of : 
 proc : args {}
 # verbose version of : proc : args {foreach arg $args {puts $arg}}
 : Introduction {
     This is a comparision of different Tcl implementation of the
     (Tcl 8.5) lreverse command.
 
     Each implementation is tested and timed with the following test
     string:
 }
 set l {1 {2 3} {4 {5 6}} 7}
 : $l
 : lreverse {First we test the builtin lreverse command}
 if {[catch {package require Tcl 8.5}]} {
     : {Sorry, lreverse is available from Tcl 8.5 or later only} {
         it seems, you are running an earlier version:} $tcl_version
 } else {
     puts "testing builtin: lreverse $l => [lreverse $l]"
     # preclude initial delay of time command
     time {lreverse $l} 1
     puts [time {lreverse $l} 10000]
 }
 : lreverse1 {
    Is the implementation given by Richard Suchenwirth on the Tcl'ers
    Wiki http://wiki.tcl.tk/17188
 }
 proc lreverse1 list {
     set res {}
     set i [llength $list]
     while {$i > 0} {lappend res [lindex $list [incr i -1]]}
     set res
 } ;# RS
 puts "testing lreverse1 $l => [lreverse1 $l]"
 time {lreverse1 $l} 1
 puts [time {lreverse1 $l} 10000]
 
 : lreverse2 {
     Is a minimal implementation based only on the basic Tcl list
     operators. Note: it does not use linsert and such looses time with
     an additional function call.
 }
 proc lreverse2 l {
     set r {}; foreach e $l {set r [concat [list $e] $r]}
     set r
 }
 puts "testing lreverse2 $l => [lreverse2 $l]"
 time {lreverse2 $l} 1
 puts [time {lreverse2 $l} 10000]
 
 : lreverse3 {
     Is an implementation using a for loop counting down from the end
     of the list.
 }
 proc lreverse3 l {
     for {set i [llength $l]} {$i} {} {
          incr i -1; lappend r [lindex $l $i]
     }
     set r
 }
 puts "testing lreverse3 $l => [lreverse3 $l]"
 time {lreverse3 $l} 1
 puts [time {lreverse3 $l} 10000]
 
 : lreverse4 {
     Is a recursive version.  Especially for larger lists it would
     not work well.
 }
 proc lreverse4 l {
     if {[llength $l]==1} {return $l}
     concat [lreverse4 [lrange $l 1 end]] [list [lindex $l 0]]
 }
 puts "testing lreverse4 $l => [lreverse4 $l]"
 time {lreverse4 $l} 1
 puts [time {lreverse4 $l} 10000]
 
 : lreverse5 {
     Uses the linsert command to stuff each element on top of the
     result list.
 }
 proc lreverse5 l {
     set r {}
     foreach e $l {set r [linsert $r 0 $e]}
     set r
 }
 puts "testing lreverse5 $l => [lreverse5 $l]"
 time {lreverse5 $l} 1
 puts [time {lreverse5 $l} 10000]
 
 : lreverse6 {
     Uses the lset command, which appeared first in Tcl 8.4.
 }
 if {[catch {package require Tcl 8.4}]} {
     : {Sorry, lreverse is available from Tcl 8.4 or later only} { 
         it seems, you are running an earlier version:} $tcl_version
 } else {
     proc lreverse6 l {
          set i [llength $l]
         foreach e $l {incr i -1; lset l $i $e}
         set l
     }
     puts "testing lreverse6 $l => [lreverse6 $l]"
     time {lreverse6 $l} 1
     puts [time {lreverse6 $l} 10000]
 }
 : lreverse7 {
     Is a tail recursive version, which could gain speed over the
     normal recursion by tail call optimization, and work with
     arbitrary length lists.
 }
 proc lreverse7 {l {r {}}} {
     if {[llength $l]==1} {
         linsert $r 0 $l
     } else {
          lreverse7 \
             [lrange $l 1 end] \
             [linsert $r 0 [lindex $l 0]]
     }
 }
 puts "testing lreverse7 $l => [lreverse7 $l]"
 time {lreverse7 $l} 1
 puts [time {lreverse7 $l} 10000]


 proc _lreverse8 {r f args} {
     if {[llength $args]} {
         _lreverse8 [linsert $r 0 $f] {*}$args
     } else {
         linsert $r 0 $f
     }
 }
 proc lreverse8 l {_lreverse8 {} {*}$l}
 puts "testing lreverse8 $l => [lreverse8 $l]"
 time {lreverse8 $l} 1
 puts [time {lreverse8 $l} 10000]
 puts "testing _lreverse8 {} {*}$l => [_lreverse8 {} {*}$l]"
 time {_lreverse8 {} {*}$l} 1
 puts [time {_lreverse8 {} {*}$l} 10000]

 set l [lrepeat 800 a]; puts "longer list: 800 elements"
 puts "lreverse"
 time {lreverse $l} 1
 puts [time {lreverse $l} 1000]
 puts "lreverse1"
 time {lreverse1 $l} 1
 puts [time {lreverse1 $l} 1000]
 puts "lreverse2"
 time {lreverse2 $l} 1
 puts [time {lreverse2 $l} 1000]
 puts "lreverse3"
 time {lreverse3 $l} 1
 puts [time {lreverse3 $l} 1000]
 puts "lreverse4"
 time {lreverse4 $l} 1
 puts [time {lreverse4 $l} 1000]
 puts "lreverse5"
 time {lreverse5 $l} 1
 puts [time {lreverse5 $l} 1000]
 puts "lreverse6"
 time {lreverse6 $l} 1
 puts [time {lreverse6 $l} 1000]
 puts "lreverse7"
 time {lreverse7 $l} 1
 puts [time {lreverse7 $l} 1000]
 puts "lreverse8"
 time {lreverse8 $l} 1
 puts [time {lreverse8 $l} 1000]
 puts "_lreverse8"
 time {_lreverse8 {} {*}$l} 1
 puts [time {_lreverse8 {} {*}$l} 1000]

 : {Consolidated timing results} {

 small long lreverse               comment
 list  list implementation
 0.59    6  builtin:   obviously the fastest solution
 1.87  116  lreverse1: countdown while loop with lappend
 1.89  118  lreverse3: countdown for loop with lappend
 2.57  245  lreverse6: foreach with lset (Tcl8.4) <- one []
 3.48 3256  lreverse5: foreach with linsert <- two []
 4.58  924  lreverse2: foreach with concat [list $e] $r <- three []
 5.63 9084 _lreverse8: tail recursion with {*} (Tcl8.5)
 5.98 3862  lreverse4: simple recursion
 6.33 9097  lreverse8: tail recursion wrapper (*) (Tcl8.5)
 6.34 7188  lreverse7: tail recursion with lindex/lrange
 } {Timing results} {
 The following is the output of sourcing this file on my laptop, a Dell
 Latitude D630 Notebook with intel core duo and 2GB RAM, and Active
 State Tcl 8.5
 } {
 testing builtin: lreverse 1 {2 3} {4 {5 6}} 7 => 7 {4 {5 6}} {2 3} 1
 0.5942 microseconds per iteration
 testing lreverse1 1 {2 3} {4 {5 6}} 7 => 7 {4 {5 6}} {2 3} 1
 1.8672 microseconds per iteration
 testing lreverse2 1 {2 3} {4 {5 6}} 7 => 7 {4 {5 6}} {2 3} 1
 4.5811 microseconds per iteration
 testing lreverse3 1 {2 3} {4 {5 6}} 7 => 7 {4 {5 6}} {2 3} 1
 1.8902 microseconds per iteration
 testing lreverse4 1 {2 3} {4 {5 6}} 7 => 7 {4 {5 6}} {2 3} 1
 5.9768 microseconds per iteration
 testing lreverse5 1 {2 3} {4 {5 6}} 7 => 7 {4 {5 6}} {2 3} 1
 3.4821 microseconds per iteration
 testing lreverse6 1 {2 3} {4 {5 6}} 7 => 7 {4 {5 6}} {2 3} 1
 2.5686 microseconds per iteration
 testing lreverse7 1 {2 3} {4 {5 6}} 7 => 7 {4 {5 6}} {2 3} 1
 6.3424 microseconds per iteration
 testing lreverse8 1 {2 3} {4 {5 6}} 7 => 7 {4 {5 6}} {2 3} 1
 6.3327 microseconds per iteration
 testing _lreverse8 {} {*}1 {2 3} {4 {5 6}} 7 => 7 {4 {5 6}} {2 3} 1
 5.629 microseconds per iteration
 longer list: 800 elements
 lreverse
 6.204 microseconds per iteration
 lreverse1
 116.202 microseconds per iteration
 lreverse2
 924.386 microseconds per iteration
 lreverse3
 118.412 microseconds per iteration
 lreverse4
 3862.613 microseconds per iteration
 lreverse5
 3255.545 microseconds per iteration
 lreverse6
 244.969 microseconds per iteration
 lreverse7
 7187.639 microseconds per iteration
 lreverse8
 9097.354 microseconds per iteration
 _lreverse8
 9084.144 microseconds per iteration
 }

----
[AMG]: [[lreverse]] can be used to invert a [dict] such that the keys and values exchange places.

This is not very efficient, since the dict has to be converted to a [list] representation before it can be reversed, then a new dict has to be created; however it is convenient.  Often you have the data in a list representation to begin with, so in practice the performance might not be an issue.

Be careful with dicts that have duplicate values, since applying [[lreverse]] results in duplicate keys.  The dict command discards duplicate keys, but normally it keeps the last instance of a duplicate.  When using [[lreverse]] it instead keeps the first instance.

======
set map {a 1 b 1 c 2}
set inv {1 a 1 b 2 c}
dict get $map b          ;# returns 1
dict get $inv 1          ;# returns b
set inv [lreverse $map]  ;# returns "2 c 1 b 1 a"
dict get $map b          ;# returns 1
dict get $inv 1          ;# returns a
======

<<categories>> Command | Performance