Think About Length OR How Fold Can Do Everything, Even Count

"Leave nothing out for length, and make us think"
-- Shakespeare, Coriolanus
Act II, Scene II, Line 47

How Long is It?

I am not sure why but before I start reading a chapter or watching something I've recorded I almost always check to see how long it is.  Today's post will be using Fold to find the length of a collection.  In Dr. Hutton's excellent paper, "A tutorial on the universality and expressiveness of fold", the following definition is given for finding the length:

length :: [α] → Int
length = fold (λx n → 1 + n) 0

We see with this definition we do nothing with the current member of the collection (x above) and instead only act on the memoize (n above).

In the simple example below we will see that the string "Mike" has 4 characters in it.

At the start we have a Seed of 0 and a collection with the members M, i, k, and e.

First time Memoize has 0 in it and X has M.

Second time Memoize has 1 in it and X has i.

Third time Memoize has 2 in it and X has the letter k.

Last time Memoize has 3 and X has e.

There you have it (maybe I should have used my sister Kim name instead).  Let us see some code.

Clojure

	(ns fold-length)
	(defn fold-length
	"length = fold (λx n → 1 + n) 0"
	[coll]
	(reduce (fn [m _] (inc m)) 0 coll))

view raw fold_length.clj hosted with ❤ by GitHub

	(ns fold-length.tests
	(require
	[clojure.test :refer [deftest testing are is run-tests]]
	[fold-length :as sut]))
	(deftest fold-length-tests
	(testing "Given an empty collection it must return 0"
	(is (zero? (sut/fold-length []))))
	(testing "Given a repeated single value it must return the number of times the value is repeated"
	(are [number] (= number (sut/fold-length (repeat number \q)))
	0
	1
	2
	11
	1010))
	(testing "Given a string it must return the number of characters in it"
	(are [s] (= (count s) (sut/fold-length (seq s)))
	"Mike Harris"
	"clojure"
	"something, something, dark side")))
	(run-tests)

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

We see in the clojure example that function we give the reduce must have two parameters, so we call the second one _ to denote that it is not used.

C#

	using System.Collections.Generic;
	using System.Linq;
	namespace Folder
	{
	public class FoldLength<T>
	{
	public static int Of(ICollection<T> collection)
	{
	return collection.Aggregate(0, (m, _) => m + 1);
	}
	}
	}

view raw FoldLength.cs hosted with ❤ by GitHub

	using System;
	using System.Collections.Generic;
	using Folder;
	using Xunit;
	namespace FolderTests
	{
	public class FoldLengthTests
	{
	[Fact]
	public void GivenEmptyCollectionItMustReturn0()
	{
	var actual = FoldLength<object>.Of(new List<object>());
	Assert.Equal(0, actual);
	}
	[Theory]
	[InlineData(0)]
	[InlineData(1)]
	[InlineData(2)]
	[InlineData(11)]
	[InlineData(1010)]
	public void GivenRepeatedSingleValueItMustReturnNumberOfTimeTheValueRepeats(int repeat)
	{
	var collection = new String('q', repeat);
	var actual = FoldLength<char>.Of(collection.ToCharArray());
	Assert.Equal(repeat, actual);
	}
	[Theory]
	[InlineData("Mike Harris")]
	[InlineData("C#")]
	[InlineData("something, something, dark side")]
	public void GivenStringItMustReturnNumberOfCharInIt(string s)
	{
	var actual = FoldLength<char>.Of(s.ToCharArray());
	Assert.Equal(s.Length, actual);
	}
	}
	}

view raw FoldLengthTests.cs hosted with ❤ by GitHub

With the C# code the lambda we give Aggregate has two values of which we give the second one the name of _ to denote not using it.

JavaScript (ECMAScript 2015)

	let _ = require("lodash");
	exports.foldLength = (coll) =>
	_.foldl(coll, m => m + 1, 0);

view raw foldLength.js hosted with ❤ by GitHub

	let sut = require("../src/foldLength"),
	expect = require("expect.js"),
	_ = require("lodash");
	describe("foldLength", () => {
	it("Given an empty collection it must return 0", () => {
	expect(sut.foldLength([])).to.equal(0);
	}),
	it("Given a repeated single value it must return the number of times the value is repeated", () => {
	let expectRangeSizeEqualsLength =
	(size) => expect(sut.foldLength(_.range(size))).to.equal(size);
	expectRangeSizeEqualsLength(0);
	expectRangeSizeEqualsLength(1);
	expectRangeSizeEqualsLength(2);
	expectRangeSizeEqualsLength(11);
	expectRangeSizeEqualsLength(1010);
	}),
	it("Given a string it must return the number of characters in it", () => {
	let expectStringEqualsLength =
	(s) => expect(sut.foldLength(s.split(""))).to.equal(s.length);
	expectStringEqualsLength("Mike Harris");
	expectStringEqualsLength("ECMAScript2015");
	expectStringEqualsLength("somthing, somthing, dark side");
	});
	});

view raw foldLengthSpec.js hosted with ❤ by GitHub

With ECMAScript 2015 we use lodash's foldl and see that the lambda only has to have one value which is the memoize.

Fin

There you have it counting with Fold, showing that you need is Fold.