Fold the Zip Up

"They fell together all, as by consent."
-- Shakespeare, The Tempest
Act II, Scene I, Line 207

Zip

Zip can be thought of as the more generic form of Map.  Think of Zip as applying a function against each member of the collections given to it, thus mapping more than one collection to another collection.  It is a lot easier to see than to explain in words.

I believe Zip2 would get the following definition:

zip2 :: (α → β → γ) → ([α] → [β] → [γ])
zip2 f = fold (λx y xs ys → f x y : xs ys) [ ]

This would be if we limit Zip to being used on 2 collections (this is mine definition, Dr. Graham Hutton has nothing to do with this definition, blame me if it is wrong).

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

Next we'll look at a simple example adding the members of two collections together.

First Memoize has nothing and X has 1 while Y has 10 giving the result of 11.

Next Memoize has 11 and X has 2 while Y has 20 giving the result of 11, 22.

Lets see some code examples.

Clojure

	(ns fold-zip)
	(defn fold-zip
	"zip f = fold (λx xs ys → f x y : xs ys) [ ]"
	[f & colls]
	(reduce #(conj %1 (apply f %2)) [] (apply map vector colls)))

view raw fold_zip.clj hosted with ❤ by GitHub

	(ns fold-zip.tests
	(require
	[clojure.test :refer [deftest testing is are run-tests]]
	[fold-zip :as sut]))
	(deftest fold-zip-tests
	(testing "Given empty collections with identity it must return an empty collection"
	(is (empty? (sut/fold-zip identity [] []))))
	(testing "Given collections with vector it must return collection zip together"
	(are [xs ys] (= (map vector xs ys) (sut/fold-zip vector xs ys))
	[1] [1]
	[1 2 3] [1 2 3]
	[1] [1 2]
	[1 2] [1]))
	(testing "Given numerical collections with math operations it must return same as map"
	(are [f]
	(are [xs ys] (= (map f xs ys) (sut/fold-zip f xs ys))
	[1] [1]
	[1 2 3] [1 2 3]
	[1] [1 2]
	[1 2] [1]
	[42.5 41.5] [11.1 16.5])
	+
	/
	*
	-))
	(testing "Given collections with collection operations it must return same as map"
	(are [f]
	(are [coll] (= (map f coll coll coll coll) (sut/fold-zip f coll coll coll coll))
	["Mike" "Harris" "clojure" "programmer"]
	[1 2 3 4 5]
	[true false true false false])
	list
	vector)))
	(run-tests)

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

With Clojure we do not have to worry about the number of collection we'll give our Zip function since we can use destructing to say and everything else.  We can then apply map to create a vector containing all the elements next to each other, we'll see this is common in the other languages since the implementation of reduce is only design to work with a single collection.  From here it is just like Map except that we need to use apply since are members are a collection themselves.

C#

	using System;
	using System.Collections.Generic;
	using System.Linq;
	using System.Text;
	using System.Threading.Tasks;
	namespace Folder
	{
	public class Zip
	{
	public static ICollection<TZ> FoldZip<TX, TY, TZ>(
	Func<TX, TY, TZ> f, ICollection<TX> xs, ICollection<TY> ys)
	{
	return xs.Zip(ys, (x, y) => new Tuple<TX, TY>(x, y))
	.Aggregate(new List<TZ>(), (m, p) =>
	{
	m.Add(f.Invoke(p.Item1, p.Item2));
	return m;
	});
	}
	}
	}

view raw Zip.cs hosted with ❤ by GitHub

	using System;
	using System.Collections.Generic;
	using System.Linq;
	using System.Text;
	using System.Threading.Tasks;
	using Folder;
	using Xunit;
	namespace FolderTests
	{
	public class ZipTests
	{
	[Fact]
	public void GivenEmptyCollectionsItMustReturnAnEmptyCollection()
	{
	var actual = Zip.FoldZip(
	(x, y) => x, new List<int>(), new List<string>());
	Assert.Empty(actual);
	}
	[Theory]
	[InlineData(new[] { 1, 2, 3 }, new[] { 4, 5, 6 })]
	[InlineData(new[] { 1, 2 }, new[] { 4, 5, 6 })]
	[InlineData(new[] { 1, 2, 3 }, new[] { 4, 5 })]
	public void GivenIntegerCollectionItMustReturnSameAsZip(int[] xs, int[] ys)
	{
	var funcs = new List<Func<int, int, int>>
	{
	(x, y) => x + y,
	(x, y) => x * y,
	(x, y) => x - y,
	(x, _) => x * x,
	(_, y) => ++y
	};
	funcs.ForEach(f => Assert.Equal(
	xs.Zip(ys, f), Zip.FoldZip(f, xs, ys)));
	}
	[Fact]
	public void GivenStringCollectionItMustReturnSameAsZip()
	{
	var colls = new List<ICollection<object>>
	{
	new[] {"Mike", "Harris", "C#", "programmer"},
	new[] {new {}, new {}},
	new[] {new {Value = 1}, new {Value = 2}, new {Value = 3}}
	};
	var funcs = new List<Func<object, object, object>>
	{
	(x, y) => new Tuple<object, object>(x, y),
	(x, y) => new List<object> {x, y},
	(x, _) => x,
	(_, y) => y
	};
	colls.ForEach(
	coll => funcs.ForEach(
	f => Assert.Equal(
	coll.Zip(coll, f),
	Zip.FoldZip(f, coll, coll))));
	}
	}
	}

view raw ZipTests.cs hosted with ❤ by GitHub

With C# we have to specify the number of collection we are going to Zip, in this case we'll do two.  We need to Zip the members from the two collections together into a Tuple (which is a bit of cheating but I can find no other way to do it with LINQ).  From there it is just like Map.  With this implementation we do have a limitation in that the two collections must be the same size, since to get around that would be a bit of work and we rather have a readable implementation than perfect code.

ECMAScript 2015

	let _ = require("lodash");
	exports.foldZip = (f, xs, ys) =>
	_.foldl(_.zip(xs, ys), (m, [x, y]) => { m.push(f(x, y)); return m; }, []);

view raw foldZip.js hosted with ❤ by GitHub

	let sut = require("../src/foldZip"),
	expect = require("expect.js"),
	_ = require("lodash");
	describe("foldZip", () => {
	it("Given an empty collections it must return same", () => {
	expect(sut.foldZip(_.identity, [], [])).to.be.empty();
	expect(sut.foldZip(_.constant(7), [], [])).to.be.empty();
	}),
	it("Given integer collections it must return same as zipWith", () => {
	let sameAsZip = (f, xs, ys) =>
	expect(sut.foldZip(f, xs, ys)).to.eql(_.zipWith(xs, ys, f));
	_.forEach([
	[1, 2, 3],
	[4, 5, 6],
	[1, 1],
	[]], (coll) => {
	sameAsZip((x, y) => x + y, coll, coll);
	sameAsZip((x, y) => x - y, coll, coll);
	sameAsZip((x, y) => x * y, coll, coll);
	sameAsZip((x, y) => x / y, coll, coll);
	});
	}),
	it("Given string collections it must return same as zipWith", () => {
	let sameAsZip = (f, xs, ys) =>
	expect(sut.foldZip(f, xs, ys)).to.eql(_.zipWith(xs, ys, f));
	_.forEach([
	["Mike", "Harris", "ECMAScript 2015", "programmer"],
	["Hello"],
	["Hi", "Jack"],
	[]], (coll) => {
	sameAsZip((x, y) => x.concat(y), coll, coll);
	sameAsZip((x, _) => x, coll, coll);
	sameAsZip((_, y) => y, coll, coll);
	});
	});
	});

view raw foldZipSpec.js hosted with ❤ by GitHub

In ECMAScript 2015 (also known as JavaScript ES6), we see an implementation similar to the C# code except we use lodash's zip to place the members in a single collection (lodash's zipWith is like LINQ's Zip).  From there it is just like Map.  With this implementation like the C# implementation we have a limitation in that the two collections must be the same size, and again the work around would be a lot of work so we'll error on keeping the code readable.

Done

There you have it showing once again that all you need is Zip.