Version 1 of set operations for Tcl lists

Updated 2008-09-08 23:15:37 by MJ

SS 30Nov2004: The following commands are basic set operations for Tcl lists. They are part of a larger library for functional programming in Tcl that's possible to find at http://wiki.hping.org/133 . The proposed commands try to run in O(M+N) time complexity, and to don't mess with the order of the elements when possible.

 proc lintersect {a b} {
     foreach e $a {
         set x($e) {}
     }
     set result {}
     foreach e $b {
         if {[info exists x($e)]} {
             lappend result $e
         }
     }
     return $result
 }

 proc lunion {a b} {
     foreach e $a {
         set x($e) {}
     }
     foreach e $b {
         if {![info exists x($e)]} {
             lappend a $e
         }
     }
     return $a
 }

 proc ldifference {a b} {
     foreach e $b {
         set x($e) {}
     }
     set result {}
     foreach e $a {
         if {![info exists x($e)]} {
             lappend result $e
         }
     }
     return $result
 }

 proc in {list element} {
     expr {[lsearch -exact $list $element] != -1}
 }

MJ - Using 8.5 ni and in, this can be speeded up quite considerable, for instance:

 proc ldifference2 {a b} {
     set result {}
     foreach e $a {
         if {$e ni $b} {lappend result $e}
     }
     return $result
 }