Version 13 of Function mapping

Updated 2013-12-01 02:30:22 by AMG

Richard Suchenwirth 2002-05-26 - Mapping is understood here as: given a function (which may also be a partial command, as the "string length" test shows) and one or more lists, return a list consisting of applying the function to one element each of the input lists. See Lambda in Tcl for a restricted version that takes only one list.

In writing the generalized version below, a foreach command, where the number of loop variables is only known at runtime, is constructed as a string and finally evaluated. What exactly is going on, may become clearer by putsing the resulting command, which for the first test gives

 map list {1 2} {3 4} {5 6}
 foreach 0 [lindex $args 0] 1 [lindex $args 1] 2 [lindex $args 2] {
        lappend res [list $0 $1 $2]
    }

People familiar with other programming languages may wonder what 0,1,2.. do here - they are just legal variable names in Tcl, since the distinction between a constant and a variable value is unambiguous by the prefixed dollar sign. By the way, what we get from using list as function, is transposing a matrix, provided that is is broken into its rows. If we have a matrix M represented as a list of (row) lists, it is most easily transposed by

 set M' [eval map list $M]

where the eval does the required breaking up into row lists. In Python, they have a special function zip for this transposition (not sure what the name zip is supposed to mean), and in Tcl we can easily have that too by just declaring

 interp alias {} zip {} map list

LEG 2008-12-27: Think of two lists as the two sides of a zipper. When you zip the zipper, you join the adjacent elements. I guess that is what gave zip its name.

 proc map {fun args} {
    set cmd "foreach "
    set fargs {}
    for {set i 0} {$i<[llength $args]} {incr i} {
        append cmd "$i [string map [list @ $i] {[lindex $args @]}] "
        lappend fargs $$i
    }
    append cmd [string map [list @f $fun @a [join $fargs]] {{
        lappend res [@f @a]
    }}]
    set res {}
    eval $cmd
    set res
 }
 #------------------------------------------- self-test
 if {[file tail [info script]]==[file tail $argv0]} {
  proc + args {expr [join $args +]}
  foreach {test expected} {
     {map list {1 2} {3 4} {5 6}} {{1 3 5} {2 4 6}}
     {map + {1 2} {3 4} {5 6}}    {9 12}
     {map "string length" {foo bar grill}} {3 3 5}
  } {
    puts $test
    catch {eval $test} res
    if {$res != $expected} {
        puts *****$res/$expected
    } else {puts OK:$res}
  }
 }

In Lisp, this behaves almost like MAPCAR, except that map above runs until all lists are exhausted, while MAPCAR ends when the shortest list is exhausted.

See Matrix multiplication and encryption for several usage examples.

Fred Nicolier 2006-06-22 - Here is another possibility using apply and {*} (taken from Onlisp by P. Graham):

 proc mapcar {fn args} {
    if {[lsearch $args {}]!=-1} {
        return {}
    } elseif {[llength $args]==1} {
        set res {}
        foreach element [lindex $args 0] {lappend res [apply $fn $element]}
        return $res
    } else {
        concat [apply $fn {*}[mapcar {l {lindex $l 0}} $args]] \
            [mapcar $fn {*}[mapcar {l {lrange $l 1 end}} $args]]
    }
 }

This behaves exactly like MAPCAR.


Tree mapping: The following code evolved in the Tcl chatroom for mapping a simple one-arg function to nested lists, and return a like-structured tree:

 proc tmap {fn tree} {
    set res {}
    foreach node $tree {
        lappend res [expr {[atomic? $node]?
                           [$fn $node] : [tmap $fn $node]
          }]
    }
    set res
 }
 proc atomic? x {expr {$x eq [lindex $x 0]}}

 proc double x {incr x $x}
 
 % tmap double {1 {2 3 {4 5} 6} {7 8} 9}
 2 {4 6 {8 10} 12} {14 16} 18