Striding a list

Richard Suchenwirth 2001-05-23 - Striding is understood here as splitting a list into sublists of fixed length, e.g.

 % lstride {a b c d e f g h i j k l} 4
 {a b c d} {e f g h} {i j k l}
 % lstride {a b c d e f g h i j k l} 3
 {a b c} {d e f} {g h i} {j k l}
 % lstride {a b c d e f g h i j k l} 2
 {a b} {c d} {e f} {g h} {i j} {k l}

So here's how I would write a list stride:

 proc lstride {L n} {
   set t [list]; set res [list]
   foreach i $L {
      lappend t $i
      if {[llength $t]==$n} {
         lappend res $t
         set t [list]
      }
   }
   if [llength $t] {lappend res $t] ;# maybe keep the rest
   set res
 }

I follow some simple rules:

• foreach is better than for (because it's simpler)
• short variable names (L is uppercase to distinguish from digit One)
• empty lists are slightly more efficiently initialized by [list] - {} is still a string, albeit empty!
• Finally returning a result looks nicer with "set res"

Here's a brain-twisting variation, which generates numeric variable names with "iota" (e.g. iota 5 => {0 1 2 3 4}) as first foreach argument, and retrieves them by eval-ling a transformed list $0 $1 $2 $3 $4:

 proc iota n {
   for {set i 0;set res [list]} {$i<$n} {incr i} {
      lappend res $i
   }   
   set res
 }
 proc lstride2 {L n} {
   set vars [iota $n]
   set cmd "list \$[join $vars { $}]"
   set res [list]
   foreach $vars $L {lappend res [eval $cmd]}
   set res
 } ;# RS

Lars H: Here's a version that's twisted a bit further:

 proc lstride2b {L n} {
   set vars [iota $n]
   set res [list]
   foreach $vars $L "lappend res \[list \$[join $vars { $}]\]"
   set res
 }

RS in Feb. 2005 prefers this simpler version:

 proc lstride {list n} {
    set res {}
    while {[llength $list]} {
        lappend res [lrange $list 0 [expr {$n-1}]]
        set list [lrange $list $n end]
    }
    set res
 }
 % lstride {a b c d e f g h i} 3
 {a b c} {d e f} {g h i}

Lars H: Note however that it runs in quadratic time. The other versions above manage to run in linear time. - RS: Time? You mean because partial lists are copied on every turn? - Lars H: Rather because the tail of the list is copied on every turn. The following runs in linear time:

 proc lstride {list n} {
    set res {}
    for {set i 0; set j [expr {$n-1}]} {$i < [llength $list]} {incr i $n; incr j $n} {
       lappend res [lrange $list $i $j]
    }
    return $res
 }

Andreas Kupries - People without fear of using a C extension can use listx [L1 ] and write:

 % ::listx split -group {a b c d e f} 2
 {a b} {c d} {e f}

 % ::listx split -group {a b c d e} 2
 {a b} {c d} {e {}}

Or

 % ::listx split {a b c d e f} 2
 {a c e} {b d f}

Arts and crafts of Tcl-Tk programming Additional list functions