Filter, Guarding You From Fold

"You and your ways; whose wraths to guard you from,"

-- Shakespeare, The Tempest

Act III, Scene III, Line 80

Filter

Filter is a lot like a higher order functional bouncer, it prevents undesirable elements from getting into the resulting collection.  

A simple example would be a filtering with a function which says if a value is odd or not.

In Dr. Hutton's excellent paper, "A tutorial on the universality and expressiveness of fold", he gives the following definition of Filter in terms of Fold:

filter :: (α → Bool) → ([α] → [α])

filter p = fold (λx xs → if p x then x : xs else xs) [ ]

From the definition above, we see that Filter is just Map but with a predicate clause stating if the element should be placed in the resulting collection or not.

Let us look at an example using my name Mike and a function which will check if a character is lower case.

(similar to Map last time)

First Memoize has nothing and X has M.

Next Memoize still has nothing (since M is upper case) and X has i.

Now Memoize has i and X has k.

Then Memoize has i and k while X has e.

Now the Filter will return the result of "ike".

Now what we all came to see, some code examples.

Clojure

	(ns fold-filter)
	(defn fold-filter
	"filter p = fold (λx xs → if p x then x : xs else xs) [ ]"
	[pred coll]
	(reduce #(if (pred %2) (conj %1 %2) %1) [] coll))

view raw fold_filter.clj hosted with ❤ by GitHub

	(ns fold-filter.tests
	(require
	[clojure.test :refer [deftest testing is are run-tests]]
	[fold-filter :as sut]))
	(deftest fold-filter-tests
	(testing "Given empty collection it must return empty"
	(is (empty? (sut/fold-filter (constantly true) []))))
	(testing "Given always true predicate it must return collection given"
	(are [coll] (= coll (sut/fold-filter (constantly true) coll))
	[]
	[1]
	[1 2 3]
	[1 1 2 3 5 8 13 21 34]
	["Mike" "Harris" "is" "a" "clojure" "programmer"]))
	(testing "Given integer collection and related predicates it must return same as filter"
	(are [pred]
	(are [coll] (= (filter pred coll) (sut/fold-filter pred coll))
	[]
	[1]
	[1 2 3]
	[1 1 2 3 5 8 13 21 34])
	even?
	odd?
	zero?
	pos?
	(partial identical? 2)
	(partial > 7)))
	(testing "Given string collection and related predicates it must return same as filter"
	(are [pred]
	(are [coll] (= (filter pred coll) (sut/fold-filter pred coll))
	["" "" ""]
	["Hello"]
	["Mike" "Harris" "is" "a" "clojure" "programmer"]
	["mIxEd" "CaSe"]
	["all" "lower" "case"])
	clojure.string/blank?
	#(.endsWith "r" %)
	#(= (clojure.string/lower-case %) %)
	#(< (count %) 5)))
	)
	(run-tests)

view raw fold_filter.tests.clj hosted with ❤ by GitHub

In Clojure we can use the reduce function to move through the collection checking the predicate condition with the if macro guard against undesirable elements.

C#

	using System;
	using System.Collections.Generic;
	using System.Linq;
	namespace Folder
	{
	public class Filters
	{
	public static IEnumerable<T> Filter<T>(
	Func<T, bool> pred, IEnumerable<T> coll)
	{
	return coll.Aggregate(
	new List<T>(),
	(m, x) =>
	{
	if (pred(x)) m.Add(x);
	return m;
	});
	}
	}
	}

view raw Filters.cs hosted with ❤ by GitHub

	using System;
	using System.Collections.Generic;
	using System.Linq;
	using Xunit;
	using Folder;
	using static System.Char;
	namespace FolderTests
	{
	public class FiltersTests
	{
	[Fact]
	public void GivenEmptyCollectionItMustReturnEmpty()
	{
	Assert.Empty(Filters.Filter(_ => true, new List<int>()));
	}
	[Theory]
	[InlineData(new[] { 1 })]
	[InlineData(new[] { 1, 2, 3 })]
	[InlineData(new[] { 1, 1, 2, 3, 5, 8, 13, 21, 34 })]
	public void GivenAlwaysTrueItMustReturnCollectionGiven(int[] coll)
	{
	Assert.Equal(coll, Filters.Filter(_ => true, coll));
	}
	[Theory]
	[InlineData(new[] {1})]
	[InlineData(new[] {1, 2, 3})]
	[InlineData(new[] {1, 1, 2, 3, 5, 8, 13, 21, 34})]
	public void GivenIntegersAndPredicateItMustReturnSameASWhere(int[] coll)
	{
	var predicates = new List<Func<int, bool>>
	{
	x => x%2 == 0,
	x => x%2 != 0,
	x => x == x*x,
	x => x > 5
	};
	predicates.ForEach(f => Assert.Equal(
	coll.Where(f),
	Filters.Filter(f, coll)));
	}
	[Fact]
	public void GivenStringsAndPredicateItMustReturnSameAsWhere()
	{
	var colls = new List<string[]>
	{
	new[] {"Hello"},
	new[] {"Mike", "Harris", "is", "a", "C#", "programmer"},
	new[] {"mIxEd", "CaSe"},
	new[] {"all", "lower", "case"}
	};
	var predicates = new List<Func<string, bool>>
	{
	s => s.EndsWith("r"),
	s => s.All(IsLower),
	s => s.Length < 5
	};
	colls.ForEach(coll =>
	predicates.ForEach(f => Assert.Equal(
	coll.Where(f),
	Filters.Filter(f, coll))));
	}
	}
	}

view raw FiltersTests.cs hosted with ❤ by GitHub

With the C# code we'll need to create some type of collection with the seed value which will allow us to add elements to it, we'll use the collection class of List.  We'll simply iterate through the collection using Aggregate and add elements to the memoize List if they pass the predicate clause.

ECMAScript 2015

	let _ = require("lodash");
	exports.foldFilter = (pred, coll) =>
	_.foldl(coll, (m, x) => { if(pred(x)) m.push(x); return m; }, []);

view raw foldFilter.js hosted with ❤ by GitHub

	let sut = require("../src/foldFilter"),
	expect = require("expect.js"),
	_ = require("lodash");
	describe("foldFilter", () => {
	it("Given an empty collection it must return empty", () => {
	expect(sut.foldFilter(_.constant(true), [])).to.be.empty();
	}),
	it("Given always true predicate it must return collection given", () => {
	let alwaysTrue = _.partial(sut.foldFilter, _.constant(true));
	_.map([
	[],
	[1],
	[1, 2, 3],
	[1, 1, 2, 3, 5, 8, 13, 21, 34],
	["Mike", "Harris", "is", "a", "ECMAScript 2015", "programmer"]
	],
	coll => expect(alwaysTrue(coll)).to.eql(coll));
	}),
	it("Given integer collection and related predicates it must return same as filter", () => {
	_.map([
	x => x % 2 === 0,
	x => x % 2 !== 0,
	_.partial(_.eq, 0),
	_.partial(_.gt, 0),
	x => x === 2,
	_.partial(_.gt, 7)
	],
	pred => _.map([
	[],
	[1],
	[1, 2, 3],
	[1, 1, 2, 3, 5, 8, 13, 21, 34]
	],
	coll =>
	expect(sut.foldFilter(pred, coll))
	.to.eql(_.filter(coll, pred))));
	}),
	it("Given string collection and related predicates it must return same as filter", () => {
	_.map([
	_.partial(_.eq, ""),
	s => _.endsWith(s, "r"),
	s => s.toLowerCase() === s,
	s => s.length === 5
	],
	pred => _.map([
	["", "", ""],
	["Hello"],
	["Mike", "Harris", "is", "a", "ECMAScript 2015", "programmer"],
	["mIxEd", "CaSe"],
	["all", "lower", "case"]
	],
	coll =>
	expect(sut.foldFilter(pred, coll))
	.to.eql(_.filter(coll, pred))));
	});
	});

view raw foldFilterSpec.js hosted with ❤ by GitHub

In the code above that we'll use the build in JavaScript array method of push to add an element which gets past the guarding predicate function to the array at the end.  We are simply move through the collection we are filtering, pushing elements into the memoize array.

Fin

There you have it we are able to keep the riffraff elements out using Fold.