[SS] 29Oct2004: '''filter''' is a very useful function in [functional programming], that given a list and a predicate (a function with arity of one, returing true or false) creates a new list which contains only the members of the original list meeting the predicate (in the same order they appeared).

I plan to submit a TIP for the addition of this function together with [map in functional programming].

The following is an implementation for Tcl, with this command structure:

    :   '''filter''' ''var list expr''

Some usage example:

======
% filter x {1 2 3 4 5 6 7 8 9} {$x > 4}
5 6 7 8 9
% filter x {1 2 3 4 5 6 7 8 9} {$x % 3}
1 2 4 5 7 8
% filter x {1 2 3 4 5 6 7 8 9} {($x % 3) == 0}
3 6 9
% filter x [list a b {} c d e {} {} f g] {[llength $x]}
a b c d e f g
======

Do you need filter? If you can see the following pattern in your code, you need it:

======
set res {}
foreach x $list {
   if {[foobar $x]} {
       lappend res $x
   }
}
use $res
======

Finally the (very simple) code:

======
proc filter {fvar flist fexpr} {
    upvar 1 $fvar var
    set res {}
    foreach var $flist {
        set varCopy $var
        if {[uplevel 1 [list expr $fexpr]]} {
            lappend res $varCopy
        }
    }
    return $res
}
======

----
[RS] would prefer an argument sequence with the list in the end:

======
filter x {$x > 4} $list
======

so the second and third argument, which form a [lambda], are left together.

----
[SS] Indeed, it's not clear what's the best. I like more what you proposed
from an aesthetic point of view, but to have the same arguments order as
map and [foreach] can be a good point.

There is another option too:

======
filter $list x {$x > 4}
======

that sounds to me slightly better.

----
'''Duoas''' writes his version

======
proc lfilter {ls varName script}
    upvar 1 $varName var
    set result {}
    foreach var $ls val $ls {
        if {[uplevel 1 eval $script]} {
            lappend result $val
        }
    }
    return $result
}
======

and his motive (no expr)

======
% set mixed {1 abc 2.5 twelve Annie -3 0}
% lfilter $mixed x {string is double -strict $x}
1 2.5 -3 0
======

Hope this helps.

[AM] (21 june 2006) But that would fail in circumstances where a numeric
conditions is needed - "$x > 4" would need to become "[expr] {$x > 4}", 
not a pleasant user requirement, IMO

----
True, but I'm still not so sure I'm convinced either way. I don't like being constrained. In any case, with the advent of [apply] in Tcl 8.5, we can use true lambdas instead of the versions we've seen so far:

======
proc ::filter {predicate ls} {
   set result {}
   foreach el $ls {
      if {[eval apply [list $predicate] $el]} {
         lappend result $el
      }
   }
   return $result
}
======

This version is particularly capable because you can choose between lambdas taking each element in the list as a whole or as individual arguments:

======
% filter {{a b} {expr {$a == $b}}} {{2 2} {3 -7} {42 9} {7 7}}
{2 2} {7 7}

% filter {args {expr {[llength $args] == 2}}} {one {two words} only one {three words here} {two again}}
{two words} {two again}
======

01-05-2007 Duoas

----
[RS] Again, here a version that uses [{*}]:

======
proc ::filter {predicate ls} {
   set result {}
   foreach el $ls {
      if [apply $predicate {*}$el] {lappend result $el}
   }
   return $result
}
======

These filters using [apply] look interesting from a theoretical point of view, but they also seem impractical when compared to the [expr] versions.  There are two reasons:  One, expressions are the most commonly form of predicate.  Two, it's easy to run a script from within an expression, but it's a bit more difficult to run an expression from within a script.  Let me show you:

======
# Arbitrary script predicate:
filter_lambda {{x} {string is double -strict $x}} {a b c 1 2 3}
filter_expr   {x} {[string is double -strict $x]} {a b c 1 2 3}
# Expression predicate:
filter_lambda {{x} {expr {$x > 5}}} {1 2 3 4 5 6 7 8 9}
filter_expr   {x}        {$x > 5}   {1 2 3 4 5 6 7 8 9}
======

The [[filter_expr]] procs I demoed take a list of variables into which each element is unpacked, same as the filters by Duoas and [RS].  My point is that [[filter_expr]] takes less typing in the common case and the same amount of typing in the (rarer?) arbitrary script predicate case.

----
[AMG]: Using [lcomp]:

======
proc filter {pred list} {
    lcomp {$x} for x in $list if $pred
}
======

Each element in '''$list''' is assigned to the variable '''$x''' which should be tested by '''$pred''', which is an [expr]ession.

======
% filter {$x > 5} {1 2 3 4 5 6 7 8 9}
6 7 8 9
======

If you need to unpack elements into multiple variables, like in Duoas's example, you can flatten the list.  But you'll have to use lcomp directly; my filter isn't flexible enough.

======
% set list {{2 2} {3 -7} {42 9} {7 7}}
# Duoas's example:
% filter {{a b} {expr {$a == $b}}} $list
{2 2} {7 7}
# My example:
% lcomp {[list $a $b]} for {a b} in [concat {*}$list] if {$a == $b}
{2 2} {7 7}
======

Actually there is a way, but it's complicated.

======
% filter {[apply {{a b} {expr {$a == $b}}} {*}$x]} $list
{2 2} {7 7}
======

As for Duoas's other example, it's better not to do any special tricks.

======
set list {one {two words} only one {three words here} {two again}}
# Duoas's example:
% filter {args {expr {[llength $args] == 2}}} $list
{two words} {two again}
# My example:
% filter {[llength $x] == 2} $list
{two words} {two again}
======

<<categories>> Algorithm | Functional Programming