Map in functional programming

map is function mapping, a classic primitive in functional programming - apply a function to all elements of a list, and return the resulting list:

 proc map {fun list} {
    set res {}
    foreach element $list {lappend res [$fun $element]}
    set res
 } ;# RS

 proc addTax x {expr {$x*1.16}}   

 % map addTax {1 10 5 2 1.95}
 1.16 11.6 5.8 2.32 2.262

IL Fun implementation I just threw together to demo...

 ### the map function and test proc. (yes i know eval is evil)
 proc map { fn list } {
    if { [llength $fn] > 1 } {
        foreach value $list { lappend tcl "[subst $fn];" }
        eval [join $tcl]; return
     }
        
    foreach value $list { $fn $value }
 }

 proc cap { value } {
        puts [string totitle $value]
 }

 ### test code
 set items { a b c "this is a long var" 1 2 3 }
 map { puts "$value" } $items
 map cap { "john" "mary" }
 map { puts [expr ($value + 5)] } { 1 2 3 4 5 }

Lars H: Since IL's map doesn't return anything (other than the empty string), it doesn't really qualify as a map in the functional programming sense. Rather, the above procedure is a contorted subequivalent of foreach that sends any user straight to Quoting Hell.

IL Sheesh, I've rarely been called a subequivalent! here's map2 which returns the value (and thus looks more like richards.)

 proc map2 { fn list } {

    if { [llength $fn] > 1 } {
        foreach value $list { 
            set r [eval [subst $fn]]; lappend res $r
        }
        return $res
    }

    foreach value $list { lappend res [$fn $value] }
    return $res
 }
 
 # test line, is this really so hellish?  the second argument is just a list of lists...
 map2 { string length "$value" } {{Tcl'ers Wiki} Wikipedia {The ServerSide} }

Lars H: Well, consider the following:

 map2 { string length "$value" } {{Tcl'ers Wiki} {[exit]} {The ServerSide} }

It should return "12 6 14", but you never get that far, due to the quoting problems.

SS 29Oct2004. I'm going to submit a TIP for the inclusion of a map command in Tcl. The semantic is very similar to foreach, with three main differences:

: map varname list body
: map varlist1 list1 ?varlist2 list2 ...? body

map raises an error if the length of every list is not multiple of the number of variables passed.
map raises an error if the number of iterations needed to consume all the lists passed is not the same.
map returns a list composed appending to every iteration the result of the script passed.

Some usage example:

 % map x {1 2 3 4} {expr $x*$x}
 1 4 9 16
 % map {x y} {1 2 3 4} {expr $x+$y}
 3 7
 % map x {1 2 3 4} y {5 6 7 8} {expr $x+$y}
 6 8 10 12
 % map x {pela mera arancia limone} {string toupper $x}
 PELA MERA ARANCIA LIMONE

Rationale

I've a strong feeling that the semantic I proposed for map is the best we can have in relation to the rest of Tcl, and the following are the reasons.

The formal command structure is very similar to foreach. map and foreach are also very similar in the Scheme Lisp dialect. Every Tcl programmer that can understand foreach will be able to use map in 1 minute.
There is no need for lambda, that's missing in Tcl. A more idiomatic way in Tcl is to pass a function direcly as a string.
It shares the power of foreach about the ability to map multiple lists in different ways, with commands having different arity (see examples).

Do you need lambda? If you can see there is the following pattern in your programs, you need it:

 set res {}
 foreach x $mylist {
   lappend res [foobar $x]
 }
 use $res

(You probably also need Filter in functional programming, that will be probably covered in the same TIP).

Implementation

I wrote the following reference implementation, that's released under the BSD license:

 proc map args {
     set argc [llength $args]
     # Check arity
     if {$argc < 3 || ($argc % 2) != 1} {
         error {wrong # args: should be "map varList list ?varList list? script"}
     }
     set listNum [expr {($argc-1)/2}]
     set numIter -1
     # Check if number of vars matches the length of the lists
     # and if the number of iterations is the same for all the lists.
     for {set i 0} {$i < $listNum} {incr i} {
         set varList [lindex $args [expr {$i*2}]]
         set curList [lindex $args [expr {$i*2+1}]]
         if {[llength $curList] % [llength $varList]} {
             error "list length doesn't match varList in arg # [expr {$i*2+1}]"
         }
         set curNumIter [expr {[llength $curList]/[llength $varList]}]
         if {$numIter == -1} {
             set numIter $curNumIter
         } elseif {$numIter != $curNumIter} {
             error "different number of iterations for varList/list pairs"
         }
     }
     # Performs the actual mapping.
     set script [lindex $args end]
     set res {}
     for {set iter 0} {$iter < $numIter} {incr iter} {
         for {set i 0} {$i < $listNum} {incr i} {
             set varList [lindex $args [expr {$i*2}]]
             set curList [lindex $args [expr {$i*2+1}]]
             set numVars [llength $varList]
             set listSlice [lrange $curList [expr {$numVars*$iter}] \
                                             [expr {$numVars*$iter+$numVars-1}]]
             uplevel 1 [list foreach $varList $listSlice break]
         }
         lappend res [uplevel 1 $script]
     }
     return $res
 }

DKF: All the above is over elaborate (and classic map doesn't do striding). Here's a simple version that leverage's Tcl 8.5's apply command:

 proc map {lambdaExpression list} {
    set res {}
    foreach element $list {lappend res [apply $lambdaExpression $element]}
    return $res
 }

Demonstrating...

 % map {x {expr {$x*1.16}}} {1 10 5 2 1.95}
 1.16 11.6 5.8 2.32 2.262
 % map {x {expr {$x*1.16}}}
 wrong # args: should be "map lambdaExpression list"

See? Even the error message is informative!

Given the simplicity of coding involved, writing a fancy version isn't really justified.

EG: In 8.6 you can use tailcall to avoid looping, for more functional appeal:

proc lmap {lambdaexpr list {acc {}}} {
    if {![llength $list]} {
        return $acc
    }
    tailcall lmap \
        $lambdaexpr \
        [lrange $list 1 end] \
        [lappend acc [apply $lambdaexpr [lindex $list 0]]]
}

Demonstrating ...

 % lmap {x {expr {$x*$x}}} {1 2 3 4 5}
 1 4 9 16 25

See also in tcllib: struct::list map, struct::list filter and struct::list fold.

NEM notes that the tcllib versions take their arguments in an inconvenient order: taking the sequence (list) before the command. This makes it awkward to use them with interp alias. My own map is this:

 proc map {func list} {
     set result [list]
     foreach elem $list {
         lappend result [uplevel #0 [linsert $func end $elem]]
     }
     return $result
 }

Demo:

 % proc + {a b} { expr {$a + $b} }
 % map {+ 1} {1 2 3 4 5}
 2 3 4 5 6
 % interp alias {} succs {} map {+ 1}
 succs
 % succs {1 2 3 4 5}
 2 3 4 5 6

I like DKF's version, which leverages Tcl 8.5's apply. However, sometimes you want to map multiple arguments to your function, and sometimes you don't. So here's a version of map that gives you the choice:

  proc ::map {lambda ls} {
    set result {}
    foreach el $ls {
      lappend result [eval apply [list $lambda] $el]
      }
    return $result
    }

Now, you can do what you like so long as the number of arguments agrees:

  % map {{a b} {eval {$a +$b}}} {{1 2} {3 4} {5 6}}
  3 7 11

  % map {args {puts $args}} {{People I like:} Roark Tera Freddy Veronica}
  People I like:
  Roark
  Tera
  Freddy
  Veronica
  {} {} {} {} {}

This is just a small happiness I can give you.

01-05-2007 Duoas

RS As you use apply, you might as well use {*} which comes in the same bag :^)

 proc ::map {lambda ls} {
    set result {}
    foreach el $ls {lappend result [apply $lambda {*}$el]}
    return $result
 }

NEM I prefer not to use apply in the implementation of map, but leave it to callers. This means you can pass normal commands just as easily as lambdas. It's simple to create a constructor for lambdas that adds the apply for you (and anything more exotic you feel like):

 proc lambda {params body} { list ::apply [list $params $body ::] }
 proc func   {params body} { list ::apply [list $params [list expr $body] ::] }
 map [func x {$x**2}] {1 2 3 4 5}

I'd also stick to the basic single-list/element version of map.

Sarnold I made my own lmap for Pdf canvas:

 proc lmap {var body list} {
        set o {}
        foreach $var $list {lappend o [eval $body]}
        set o
 }

The nice thing in 'foreach $var' is that you can map tuples (like option-values pairs). The following code is used to put the assertion that the user does *not* put a -fill option:

 lmap {option value} {assert {$option ne "-fill"}} {-opt val ...}

wdb Here's my version of map which recognizes both -- procedures and applyable expressions:

 proc map {function list} {
    set result {}
    if {[llength $function] < 2} then {
        foreach e $list {
            lappend result [$function $e]
        }
    } else {
        set vals [lindex $function 0]
        foreach x $vals {
            append vars " $$x"
        }
        foreach $vals $list [subst -nocommand {
            lappend result [apply {$function} $vars]
        }]
    }
    set result
 }

Test with a predefined command, e.g. puts:

 % map puts {a b c}
 a
 b
 c
 {} {} {}
 %

Test with applyable expression, e.g. {{x y} {list $x and $y}}:

 % map {{x y} {list $x and $y}} {a b c}
 {a and b} {c and {}}
 %

AMG: Implementation using lcomp:

proc map {func list} {
    lcomp $func for x in $list
}

Test:

% map {$x * 2} {1 2 3 4 5}
2 4 6 8 10
% map {[string length $x]} {mary had a little lamb}
4 3 1 6 4
% map {"$x$x"} {double up each word}
doubledouble upup eacheach wordword

Category Algorithm

Category Functional Programming