Displanting a Function OR Folding a Reverse

"Displant a town, reverse a prince's doom"
-- Shakespeare, Romeo and Juliet
Act III, Scene III, Line 60

Reverse

The interesting thing about the Reverse function is that it is not really doing anything.  With a small clerical error in a visit and recombine function you have reverse.

In Dr. Hutton's excellent paper, "A tutorial on the universality and expressiveness of fold", the following definition is given for reversing:

reverse :: [α] → [α]
reverse = fold (λx xs → xs ++ [x]) [ ]

We see that we concat the memoize with the member, in that order, thus reversing the collection.

Since I like advertising myself, let us go through an example with my name (someone has to advertise for me).

First time the Memoize has nothing and X has M.

Second time the Memoize has M and X is i.

Third time Memoize has i and M and X has k.

Fourth time Memoize has k, i, and M while X has e.

Leaving us with ekiM.

Let us look at some code examples.

Clojure

	(ns fold-reverse)
	(defn fold-reverse
	"reverse = fold (λx xs → xs ++ [x]) [ ]"
	[coll]
	(reduce #(cons %2 %1) [] coll))

view raw fold_reverse.clj hosted with ❤ by GitHub

	(ns fold-reverse.tests
	(require
	[clojure.test :refer [deftest testing is are run-tests]]
	[fold-reverse :as sut]))
	(deftest fold-reverse-tests
	(testing "Given an empty collection it must return an empty collection"
	(is (empty? (sut/fold-reverse []))))
	(testing "Given a string it must return the sames as clojure.string/reverse"
	(are [s] (= (clojure.string/reverse s) (->> s sut/fold-reverse (apply str)))
	"Mike Harris"
	"clojure"
	"something, something, dark side"))
	(testing "Given a vector it must return the same as reverse"
	(are [v] (and
	(vector? v)
	(= (reverse v) (sut/fold-reverse v)))
	[]
	[1]
	[1 2]
	[1 2 3]))
	(testing "Given a non-empty vector it must return the same as rseq"
	(are [v] (and
	((comp vector? not-empty) v)
	(= (rseq v) (sut/fold-reverse v)))
	[1]
	[1 2]
	[1 2 3])))
	(run-tests)

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

We see with the Clojure code we are using the cons function to place the current member in the front of the memoize.  We do this for the whole collection thus giving us the collection in reverse.

C#

	using System.Collections.Generic;
	using System.Linq;
	namespace Folder
	{
	public class Reverse
	{
	public static IEnumerable<T> It<T>(IEnumerable<T> coll)
	{
	return coll.Aggregate(
	new List<T>(),
	(m, x) => new List<T> {x}.Concat(m).ToList());
	}
	}
	}

view raw Folder.cs hosted with ❤ by GitHub

	using System;
	using System.Collections.Generic;
	using System.Linq;
	using Folder;
	using Xunit;
	namespace FolderTests
	{
	public class ReverseTests
	{
	[Fact]
	public void GivenAnEmptyCollectionItMustReturnAnEmptyCollection()
	{
	Assert.Empty(Reverse.It(new List<object>()));
	}
	[Theory]
	[InlineData("")]
	[InlineData("Mike Harris")]
	[InlineData("C#")]
	[InlineData("something, something, dark side")]
	public void GivenStringItMustReturnStringEqualToReverseString(string s)
	{
	var expected = String.Concat(s.Reverse());
	var actual = String.Concat(Reverse.It(s));
	Assert.Equal(expected, actual);
	}
	[Theory]
	[InlineData(new [] {1})]
	[InlineData(new [] {1, 2})]
	[InlineData(new [] {1, 2, 3})]
	public void GivenCollectionItMustReturnCollectionEqualToReverse(int[] coll)
	{
	var expected = coll.Reverse();
	var actual = Reverse.It(coll);
	Assert.Equal(expected, actual);
	}
	}
	}

view raw FolderTests.cs hosted with ❤ by GitHub

With the C# code we see that we need to create something to contain the resulting collection, in this case we'll create a List.  We create the reversed collection in an immutable way by creating a new List every time in the lambda.

ECMAScript 2015

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

view raw foldReverse.js hosted with ❤ by GitHub

	let sut = require("../src/foldReverse"),
	expect = require("expect.js"),
	_ = require("lodash");
	describe("foldReverse", () => {
	it("Given an empty collection it must return same", () => {
	expect(sut.foldReverse([])).to.be.empty();
	}),
	it("Given string it must return same as string in reverse", () => {
	let reverse = s => s.split("").reverse().join("");
	expect(reverse("hi")).to.equal("ih");
	let sameAsReverse = s =>
	expect(sut.foldReverse(s.split("")).join(""))
	.to.equal(reverse(s));
	sameAsReverse("Mike Harris");
	sameAsReverse("ECMAScript 2015");
	sameAsReverse("something, something, dark side");
	}),
	it("Given collection it must return same as reverse", () => {
	let sameAsReverse = coll =>
	expect(sut.foldReverse(coll)).to.eql(coll.reverse());
	sameAsReverse([]);
	sameAsReverse([1]);
	sameAsReverse([1, 2]);
	sameAsReverse([1, 2, 3]);
	});
	});

view raw foldReverseSpec.js hosted with ❤ by GitHub

With JavaScript (ECMAScript 2015) we us the unshift method on the array.  Since unshift returns the length of the array after the member is added to the head of the array (which I totally did not expect) we need to manually return the memoize after applying unshift.

Fin

There you have it again, yet another function which can be created using Fold.  Showing once again that all you need is Fold.