Filter in functional programming

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 $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

dbohdan 2014-06-01: Changed uplevel 1 eval $script to uplevel 1 $script in lfilter above. The eval was unnecessary and broke quoting.

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 expression.

% 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}