Folding into Map

"I have forgot the map."
-- Shakespeare, Henry IV Part I
Act III, Scene I, Line 5

Map

Map is the first of the big three Higher Order Function we will looking at Folding using Dr. Hutton's excellent paper, "A tutorial on the universality and expressiveness of fold", as a guide.  The idea of a Map is simple, you have a collection which you wish to apply some translation function against every member of the collection.

We can look at a few simple examples, the first of which would be the identity function.

 Next we can look at a constant function which maps turtle for any value given to it.

Last we can look at a function which shifts everything given to it.

All of this these functions have something in common, they all apply a function against every single member of the collection they are given, thus the resulting collection is the exact same size as the collection given to it.

We can now look at how we would implement Map using a Fold.  We see that Dr. Hutton gives Map the following definition:

map :: (α → β) → ([α] → [β])
map f = fold (λx xs → f x : xs) [ ]

Folding a Map we'll need a collection to seed with then we just apply the given function against each member concatenating it with the seed.

(similar to Reverse from last time)

Let us look at an example of upper casing Mike.

First Memoize has nothing and X has M.

Second Memoize has M and X has i.

Third time Memoize has MI and X has k.

Finally Memoize has MIK and X has e.

Giving the final result of MIKE.  Now let us look at some code examples.

Clojure

	(ns fold-map)
	(defn fold-map
	"map f = fold (λx xs → f x : xs) [ ]"
	[f coll]
	(reduce #(conj %1 (f %2)) [] coll))

view raw fold_map.clj hosted with ❤ by GitHub

	(ns fold-map.tests
	(require
	[clojure.test :refer [deftest testing is are run-tests]]
	[fold-map :as sut]))
	(deftest fold-map-tests
	(testing "Given an empty collection it must return an empty collection"
	(is (empty? (sut/fold-map identity []))))
	(testing "Given the identity function it must return collection given"
	(are [coll] (= coll (sut/fold-map identity coll))
	[]
	[1]
	[1 2 3 4 5]
	["Mike" "Harris" "clojure" "programmer"]
	[\a \b \c]))
	(testing "Given function and an int collection it must return the same as applying map"
	(are [f]
	(are [coll] (= (map f coll) (sut/fold-map f coll))
	[]
	[1]
	[1 2 3 4 5]
	[1 1 2 3 5 8 13 21 34])
	identity
	inc
	#(* %1 %1)
	dec))
	(testing "Given function and string collection it must return same as applying map"
	(are [f]
	(are [coll] (= (map f coll) (sut/fold-map f coll))
	[]
	["Kelsey"]
	["Jack"]
	["Mike" "Harris" "clojure" "programmer"]
	["mIxEd CaSe"])
	identity
	clojure.string/lower-case
	clojure.string/upper-case
	clojure.string/capitalize)))
	(run-tests)

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

In Clojure we use the reduce function to Fold.  We give the reduce a seed of an empty collection and use conj to join applying the function given with the resulting collection.

C#

	using System;
	using System.Collections.Generic;
	using System.Linq;
	namespace Folder
	{
	public class Mapper
	{
	public static IEnumerable<T> Map<T>(
	IEnumerable<T> coll, Func<T, T> func)
	{
	return coll.Aggregate(
	new List<T>(),
	(m, x) =>
	{
	m.Add(func(x));
	return m;
	});
	}
	}
	}

view raw Mapper.cs hosted with ❤ by GitHub

	using System;
	using System.Collections.Generic;
	using System.Linq;
	using Folder;
	using Xunit;
	namespace FolderTests
	{
	public class MapperTests
	{
	[Fact]
	public void GivenEmptyCollectionItMustReturnEmptyCollection()
	{
	Assert.Empty(Mapper.Map<int>(new List<int>(), x => x));
	}
	[Fact]
	public void GivenIdentityFunctionItMustReturnSameCollection()
	{
	Func<int, int> identity = x => x;
	var expected = new List<int> { 1, 2, 3, 4, 5 };
	Assert.Equal(expected, Mapper.Map<int>(expected, identity));
	}
	[Fact]
	public void GivenIncrementFunctionItMustReturnNextValuesInCollection()
	{
	Func<int, int> increment = x => x + 1;
	var collection = new List<int> { 1, 2, 3, 4, 5, 5, 6, 42 };
	Assert.Equal(
	collection.Select(increment),
	Mapper.Map<int>(collection, increment));
	}
	[Fact]
	public void GivenFunctionItMustReturnSameAsSelect()
	{
	var funcs = new List<Func<int, int>>
	{
	x => x,
	x => x + 1,
	x => x*x,
	x => x - 1
	};
	var collection = new List<int> { 1, 1, 2, 3, 5, 8, 13, 21, 34 };
	funcs.ForEach(f => Assert.Equal(
	collection.Select(f),
	Mapper.Map(collection, f)));
	}
	}
	}

view raw MapperTests.cs hosted with ❤ by GitHub

With C# we use the aggregate LINQ function to Fold.  We give the aggregate a List and add the result of applying each member of the given collection against the function we are mapping with.

ECMAScript 2015

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

view raw foldMap.js hosted with ❤ by GitHub

	let sut = require("../src/foldMap"),
	expect = require("expect.js"),
	_ = require("lodash");
	describe("foldMap", () => {
	it("Given an empty collection it must return an empty collection", () => {
	expect(sut.foldMap(_.identity, [])).to.be.empty();
	}),
	it("Given identity function it must return given collection", () => {
	let identity = _.partial(sut.foldMap, _.identity),
	expectSame = (f, coll) => expect(f(coll)).to.eql(coll);
	expect(identity([])).to.be.empty();
	expectSame(identity, [1]);
	expectSame(identity, [1, 2, 3, 4, 5]);
	expectSame(identity,
	["Mike", "Harris", "ECMAScript 2015", "programmer"]);
	expectSame(identity, ['a', 'b', 'c']);
	}),
	it("Given function and an int collection it must return the same as applying map", () => {
	let expectEql = (f, coll) =>
	expect(sut.foldMap(f, coll)).to.eql(_.map(coll, f));
	_.map([_.identity, x => x + 1, x => x * x, x => x - 1],
	f => {
	expectEql(f, []);
	expectEql(f, [1]);
	expectEql(f, [1, 2, 3, 4, 5]);
	expectEql(f, [1, 1, 2, 3, 5, 8, 13, 21, 34]);
	});
	}),
	it("Given function and string collection it must return same as applying map", () => {
	let expectEql = (f, coll) =>
	expect(sut.foldMap(f, coll)).to.eql(_.map(coll, f));
	_.map([_.identity, _.camelCase, _.capitalize, _.snakeCase],
	f => {
	expectEql(f, []);
	expectEql(f, ["Kelsey"]);
	expectEql(f, ["Jack"]);
	expectEql(f, ["Mike", "Harris", "ECMAScript 2015", "programmer"]);
	expectEql(f, ["mIxEd CaSe"]);
	});
	});
	});

view raw foldMapSpec.js hosted with ❤ by GitHub

Using ECMAScript 2015 (aka JavaScript), we use lodash's foldl to Fold.  We give the foldl an empty array and push the result of applying the function given against the member we are mapping against.

To End All

There you have it by folding with an empty collection and applying the given function against each member adding the result against the seed and you have a Map.