## 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}```

 Category Algorithm Category Functional Programming