Round and Round We Go OR How to Stop Circular References in AutoFixture

"That many things, having full reference"
-- Shakespeare, Henry V
Act I, Scene II, Line 205

I love to use AutoFixture to setup the the arrange part of my tests.  I find that working without worrying about the arrange allows me to focus more on the task at hand.  A possible downside of working this way is that AutoFixture is mindlessly setting up all the test data.

Having AutoFixture setup your test data is fine when working with green field classes but when working with legacy code and third party code you getting into cases in which you have circular references.  What do I mean?  Compare the following:

Case 1:

class A has members with type B
type B has member with type C
type C is a primitive

Case 2:

class X has members with type Y
type Y has member with type Z
type Z has member with type X

In case 1 we have a termination point with type C, AutoFixture can happily go about and create an instance of A and populate all the members in the hierarchy with data.

In case 2 we do not have a termination point, Z has a member of type X which a member of type Y which a member of type Z which goes back to X and so on.  Case 2 has a circular reference and AutoFixture is unable to give us back an instance of X without going into an endless loop.  Luckily AutoFixture is smart enough to figure out that it is in an endless loop and will error out telling us about the issue.

What do we do if we have a class like X in legacy code or third party code?  We'll we can tell AutoFixture that we will have classes like X but that it is fine to just terminate the repeating hierarchy with a null or empty.  We use the following to do that:

	[TestInitialize]
	public void BeforeEach()
	{
	_fixture = new Fixture();
	// client has a circular reference from AutoFixture point of view
	_fixture.Behaviors.Remove(new ThrowingRecursionBehavior());
	_fixture.Behaviors.Add(new OmitOnRecursionBehavior());
	}

view raw setup.cs hosted with ❤ by GitHub

I normally put this in my TestInitialize for the test class of the offender, but I can see putting in the arrange of a test class if you are mixing old and new.  There you have it, a way to use AutoFixture with dirty old classes.

AutoFixture for the Win

"What have I kept back?"
-- Shakespeare, Antony and Cleopatra
Act V, Scene II, Line 147.2

Anyone who has paired with me while working in C# knows that I am addicted to AutoFixture.  Now I do not try to add it to everything that I am working, but usually it finds its way into whatever I am working on.  Why?  Simply put, using AutoFixture allows me to focus on the task at hand.

Here is a quick example:

	using System;
	using System.Collections.Generic;
	using System.Linq;
	using System.Text;
	using System.Threading.Tasks;
	namespace Folder
	{
	public static class Mapper
	{
	public static IEnumerable<U> Map<T, U>(this IEnumerable<T> source, Func<T, U> func)
	{
	return source.Aggregate(new List<U>(), (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 System.Text;
	using System.Threading.Tasks;
	using Ploeh.AutoFixture.Xunit2;
	using Xunit;
	using Folder;
	namespace Folder.Tests
	{
	public class MapperTests
	{
	[Theory, AutoData]
	public void GivenIdentityItMustReturnGiven(int[] given)
	{
	var actual = given.Map(x => x);
	Assert.Equal(given, actual);
	}
	[Theory, AutoData]
	public void GivenToStringItMustReturnGivenAsStrings(int[] given)
	{
	var actual = given.Map(x => x.ToString());
	Assert.Equal(given.Select(x => x.ToString()), actual);
	}
	[Theory, AutoData]
	public void GivenCatizeItMustReturnGivenCatize(string[] given)
	{
	var catize = given.Map(x => string.Concat(x, "cat"));
	Assert.All(catize, c => Assert.EndsWith("cat", c));
	}
	}
	}

view raw MapperTests.cs hosted with ❤ by GitHub

In this example I am implementing the higher order function Map using the higher order function Fold (see my other post if this interested you).

What do you not see in the tests?  The setting up of the test data.

Why?  It is not important to the task at hand.  We do not need it to test the behavior of Map.  Map takes a collection and a function and applies the function against every member of the collection producing a new collection.  What we want to verify is the applies part, which only requires a collection and a function, the actual members of the collection (and the function) do not matter for this verification.

Staying focus on the task at hand is the power of a test fixture and having someone else implement the test fixture for you is even better.  Using AutoFixture with xUnit you really do not need to think about setting up test data at all and that is good thing.

Axioms of Equal in Clojure

"In quantity equals not one of yours."
-- Shakespeare, Henry IV Part I
Act III, Scene I, Line 93

In The Little Prover we find the following Axioms of Equal:

(dethm equal-same (x) 
  (equal (equal x x) 't))

(dethm equal-swap (x y) 
  (equal (equal x y) (equal y x)))

(dethm equal-if (x y)
  (if (equal x y
    (equal x y)
    't)))

I learn best by doing, so I showed myself these axioms in Clojure.

	(ns axoims-of-equal
	(require [clojure.test :refer :all]))
	; based on The Little Prover
	(deftest equal-tests
	(testing "(dethm equal-same (x) (equal (equal x x) 't))"
	(let [x 42]
	(is (= true (= x x))))
	(is (= true (= :yep :yep)))
	(is (= true (= false false))))
	(testing "(dethm equal-swap (x y) (equal (equal x y) (equal y x)))"
	(let [x 42
	y 43]
	(is (= (= x y) (= y x))))
	(let [x :yep
	y :yep]
	(is (= (= x y) (= y x))))
	(is (= (= true false) (= false true)))
	(is (= (= :yep :nope) (= :nope :yep))))
	(testing "(dethm equal-if (x y) (if (equal x y (equal x y) 't)))"
	(let [x 42
	y 42]
	(is (true? (if (= x y) (= x y) false))))
	(let [x :yep
	y :nope]
	(is (= :else (if (= x y) (= x y) :else))))
	(is (true? (if (= :yep :yep) (= :yep :yep) (throw (IllegalStateException. "How the hell did we get here?")))))
	(is (thrown? Exception (if (= :yep :nope) (= :yep :nope) (throw (Exception. "Noooooooooooo")))))
	(let [x (repeatedly (constantly 42))
	y x]
	(is (true? (if (= x y) (= x y) false))))
	(let [x (repeat 42)
	y x]
	(is (true? (if (= x y) (= x y) false))))
	(comment
	this will not finish since = is eager in this case
	see: https://github.com/clojure/clojure/blob/master/src/jvm/clojure/lang/APersistentVector.java
	(let [x (repeat 42)
	y (repeat 42)]
	(is (true? (if (= x y) (= x y) false)))))
	)
	)
	(run-tests)

view raw axioms_of_equal.clj hosted with ❤ by GitHub

Looking at equal-same we see that if we have something which is the same then those values are equal.  Nothing shocking, unless you are using reference equivalence which we are not.

Next we look at equal-swap which states that equivalence is commutative meaning x = y is the same as y = x.  Again nothing shocking.

Last we look at equal-if which states that if something is equal once it will be equal again.  Note that this assumes that values are immutable which they are (for the most part) in Clojure.  This axiom is rather interesting when paired with lazy evaluation, as we see with the following:

(is (true? 
  (if (= :yep :yep) 
      (= :yep :yep) 
      (throw 
        (IllegalStateException. "How the hell did we get here?")))))

When the statement is evaluated we do not have the Exception thrown!  This is a great benefit of the if special form in Clojure.  We do see this awesomeness has limits:

(let [x (repeat 42)
      y x]
  (is (true? 
    (if (= x y)
      (= x y)
      false)))) 

but fails when the infinite sequence is not the same "reference"

(let [x (repeat 42) 
      y (repeat 42)]
  (is (true?
    (if (= x y)
        (= x y)
        false)))))

Despite the second example of comparing with an infinite sequence not finishing, the if special form is awesome and shows the power of the equal-if axiom paired with lazy evaluation.

These axioms are very powerful and I would argue are more useful than tests. If this interests you I would recommend reading The Little Prover or working your way through the flying tour of ACL2.

Axioms of If in Clojure

"How if I answer no?"
-- Shakespeare, Hamlet
Act V, Scene II, Line 167

In The Little Prover we find the following Axioms of If:

(dethm if-true (x y)
  (equal (if 't x y) x))

(dethm if-false (x y)
  (equal (if 'nil x y) y)

(dethm if-same (x y)
  (equal (if x y y) y)

(dethm if-nest-A (x y z)
  (if x
    (equal (if x y z) y)
    't))

(dethm if-nest-E (x y z)
  (if x
    't
    (equal (if x y z) z)))

The way I learn best is by trying doing, so I showed myself these axioms in Clojure.

	(ns axioms-of-if
	(require [clojure.test :refer :all]))
	; based on The Little Prover
	(deftest if-tests
	(testing "(dethm if-true (x y) (equal (if 't x y) x))"
	(is (true? (if true true false)))
	(is (= :yep (if true :yep :nope)))
	(is (= :yep (if true
	(if true :yep :nopes)
	:nope))))
	(testing "(dethm if-false (x y) (equal (if 'nil x y) y)"
	(is (true? (if false false true)))
	(is (= :yep (if false :nope :yep)))
	(is (= :yep (if false
	:nope
	(if false :nopes :yep)))))
	(testing "(dethm if-same (x y) (equal (if x y y) y)"
	(is (= true (if true true true)))
	(is (= :yep (if true :yep :yep)))
	(is (=
	(if false :yep :yep)
	(if true :yep :yep)))
	(is (=
	(if false (if false :yep :yep) (if false :yep :yep))
	(if true (if true :yep :yep) (if true :yep :yep)))))
	(testing "(dethm if-nest-A (x y z) (if x (equal (if x y z) y) 't))"
	(is (true? (if true (= (if true :yep :nope) :yep) false)))
	(is (true? (let [x true]
	(if x (if x true false) false))))
	(is (= :yep (let [x true]
	(if x (if x :yep :nope) :nope)))))
	(testing "(dethm if-nest-E (x y z) (if x 't (equal (if x y z) z)))"
	(is (true? (if false false (= (if false :nope :yep) :yep))))
	(is (true? (let [x false]
	(if x false (if x false true)))))
	(is (= :yep (let [x false]
	(if x :nope (if x :nope :yep))))))
	)
	(run-tests)

view raw axioms_of_if.clj hosted with ❤ by GitHub

Looking at if-true we see that if we have a true premise that we always take the answer part of the if.

(if premise answer else)

This is not a shock to anyone, but is very useful.

Moving on we see if-false states that if we have a false premise that we always take the else part of the if.  Again nothing shocking but very useful.

Next we see if-same which states that if the answer and else are the same then the premise does not matter.  This makes complete logical sense, but I'll admit I never really thought of it before.

Now let us look at if-nest-A which states that if the condition is true in the premise then it must be true in the answer part.  This is very awesome, we can now eliminate code by simply looking for redundant ifs.  We see this in the following:

given x is true 

(if x 
  (if x :yep :nope)
  :nope)))))

We see that we have  the(if what-ever in the outside which matches the (if what-ever in the answer part thus we can eliminate it pulling it up (in the code above the :yep), since if the premise is true on the outside it is true on the inside.  This axiom is very useful in refactoring code and I figured it out for myself a long time ago and find myself using it all the time, it is nice to know that it has a solid theoretical basis.

Last we see the anti of if-nest-A, if-nest-E.  if-nest-E states that if the condition is false in the premise then it must be false in the else part.  We see this in the following:

given x is false

(if x
  :nope
  (if x :nope :yep))

We see that we have the (if what-ever in the outside which matches the (if what-ever in the else part thus we can eliminate it pulling it up (in the code above the :yep), since if the premise is false on the outside it is false on the inside.  Again, this is very useful in eliminating code.

These axioms are very powerful and I would argue are more useful than tests.  If this interests you I would recommend reading The Little Prover or working your way through the flying tour of ACL2.

Axioms of Cons in Clojure

"Why then, build me thy fortunes upon the basis"
-- Shakespeare, Twelfth Night
Act III, Scene II, Line 31

I recently finished The Little Prover.  In The Little Prover we find the following Axioms of Con:

(dethm atom/cons (x y) 
  (equal (atom (cons x y)) 'nil)

(dethm car/cons (x y)
  (equal (car (cons x y)) x))

(dethm cdr/cons (x y)
  (equal (cdr (cons x y)) y))

(dethm cons/car+cdr (x)
  (if (atom x)
    't
    (equal (cons (car x) (cdr x)) x)))

The way I learn best is by showing myself that something makes sense, so I went through showing myself these axioms in Clojure.

	(ns axioms-of-cons
	(require [clojure.test :refer :all]))
	; based on The Little Prover
	(deftest cons-tests
	(testing "(dethm atom/cons (x y) (equal (atom (cons x y)) 'nil)"
	(let [atom? (complement sequential?)] ; clojure does not have atom
	(is (false? (atom? (cons 1 [2]))))
	(is (false? (atom? (cons 1 (cons 2 [3])))))
	(is (false? (atom? (cons 1 []))))))
	(testing "(dethm car/cons (x y) (equal (car (cons x y)) x))"
	(is (= 1 (first (cons 1 '(2)))))
	(is (= :first (first (cons :first [2]))))
	(is (= :first (first (cons :first (cons 2 [3]))))))
	(testing "(dethm cdr/cons (x y) (equal (cdr (cons x y)) y))"
	(is (= [2] (rest (cons 1 [2]))))
	(is (= [2 3] (rest (cons 1 [2 3]))))
	(is (= [2 3] (rest (cons 1 (cons 2 [3]))))))
	(testing "(dethm cons/car+cdr (x) (if (atom x) 't (equal (cons (car x) (cdr x)) x)))"
	(let [x [1 2 3]]
	(is (and
	(sequential? x)
	(= x (cons (first x) (rest x))))))
	(let [x (cons 1 '(2))]
	(is (and
	(sequential? x)
	(= x (cons (first x) (rest x)))))))
	)
	(run-tests)

view raw axioms_of_cons.clj hosted with ❤ by GitHub

Looking at atom/cons in the code above we see that Clojure does not have atom but (complement sequential?) is close enough if we are working with sequential collections so we'll use that.  Using the definition that an atom is not a sequential collection we see in the code above that cons "always" yields not an atom.

Next looking at car/cons in the code above we see that using first (Clojure's car) on a cons "always" yields the head of the sequential collection, which makes prefect sense since that is what one expects from first.

The other side of car/cons is cdr/cons.  Looking at the code above we see that using rest (Clojure's cdr) on a cons "always" yields the tail of the sequential collection, which again makes prefect sense since that is what one expects from rest.

Last we look at cons/car+cdr.  Looking at the code we see that if we do not have an atom that first and rest (Clojure's car and cdr) together yield the sequential collection, which again is what one would expect.

So what does any of this give us?  We now have a firm foundation on which to define other theorems and proofs about our statements using these axioms as our basis.  This is very powerful and I would argue that this is better having tests.

If this interests you I would recommend reading The Little Prover or working your way through the flying tour of ACL2.

Showing Map Distributes Over Functional Composition OR Fun With Clojure

"Here by the cheeks I'll drag thee up and down."
-- Shakespeare, Henry VI Part 1
Act I, Scene III, Line 51

I love to try things out for myself.  Whenever I am trying to understand idea I need to show myself that the idea is valid.  Sometimes I will just accept something, but if I really want to understand it I will show myself that it makes sense.

While rereading Dr. Hutton's paper "A tutorial on the universality and expressiveness of fold", I came back across the following statement, "the map operator distributes over function composition".  Being the kind of person which likes to show things to myself I figured I'd show myself this idea in Clojure as part of my daily kata.

	(ns distributes-over-functional-composition-tests
	(require
	[clojure.test :refer [deftest testing are run-tests]]
	[clojure.core.reducers :as r]))
	(deftest map-distributes-over-functional-composition-tests
	(testing "map f · map g = map (f · g)"
	(are [coll]
	(are [f g] (=
	((comp (partial map f) (partial map g)) coll) ; map f · map g
	(map (comp f g) coll)) ; map (f · g)
	identity identity
	inc dec
	#(* % %) (partial * 2)
	(constantly 43) (constantly 42)
	zero? (partial mod 5))
	[1]
	[]
	[1 2 3 4]
	[-1 -2 -3 -4]
	[377 610 987]
	[17711 28657]
	[0.25 0.36 0.42 0.2]
	[1/2 1/3 1/4 1/5]
	[1 -1 2 -3 5 -8]
	[42.0 21.0 10.5 5.25 2.625 1.3125])))
	(deftest reducers-distributes-over-functional-composition-tests
	(testing "map f · map g = map (f · g)"
	(are [coll]
	(are [f g] (=
	((comp (partial map f) (partial map g)) coll) ; map f · map g
	(into [] ((comp (r/map f) (r/map g)) coll)) ; map f · map g
	(map (comp f g) coll)) ; map (f · g)
	identity identity
	inc dec
	#(* % %) (partial * 2)
	(constantly 43) (constantly 42)
	zero? (partial mod 5))
	[1]
	[]
	[1 2 3 4]
	[-1 -2 -3 -4]
	[377 610 987]
	[17711 28657]
	[0.25 0.36 0.42 0.2]
	[1/2 1/3 1/4 1/5]
	[1 -1 2 -3 5 -8]
	[42.0 21.0 10.5 5.25 2.625 1.3125]))
	(testing "reduction f · reduction g = reduction (f · g)"
	(are [coll]
	(are [f g]
	(are [reduct rreduct]
	(=
	((comp (partial reduct f) (partial reduct g)) coll) ; reduction f · reduction g
	(r/foldcat ((comp (rreduct f) (rreduct g)) coll))) ; reduction (f · g)
	take-while r/take-while
	remove r/remove
	filter r/filter
	)
	(constantly true) (constantly true)
	(constantly true) (constantly false)
	(constantly false) (constantly false)
	(constantly false) (constantly true)
	(partial > 2) pos?
	neg? (partial < 1/2)
	)
	[1]
	[]
	[1 2 3 4]
	[-1 -2 -3 -4]
	[377 610 987]
	[17711 28657]
	[0.25 0.36 0.42 0.2]
	[1/2 1/3 1/4 1/5]
	[1 -1 2 -3 5 -8]
	[42.0 21.0 10.5 5.25 2.625 1.3125]))
	)
	(run-tests)

view raw distributes_over_functional_composition_tests.clj hosted with ❤ by GitHub

Looking at the code above we see the following:

• map f · map g = map (f · g)
• r/map f · r/map g = r/map (f · g)
• reduction f · reduction g = reduction (f · g)

So what does this give us?  Having this property we are allowed to improve the performance of our code by composing a series of transformation against a collection to a single transformation of the collection dragged through a series of composed functions.  In fact this is the whole idea behind streams.

Taken straight from Raoul-Gabriel Urma's article in Java Magazine, "[i]n a nutshell, collections are about data and streams are about computations."  Thinking about processing as a series of computation we see how we can naturally think about composing our computations together and then drag the data through using a higher order function like map to preform the series of transformations in one pass.

On the Fusion Property of Fold

"If I break time, or flinch in property"
-- Shakespeare, All's Well That Ends Well
Act II, Scene I, Line 187

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

h · fold g w = fold f v

Great, but what does this mean to me?  Well if we go on in the paper we find the following application of the fusion property of Fold:

(+1) · sum = fold (+) 1

Interesting, we see that adding 1 to the sum (defined as, fold (+) 0) of a collection is the same as folding over that collection with 1 as the seed value.  Further down in the paper we see that we can simplify and generalize the application above as:

(⊕ a) · fold (⊕) b = fold (⊕) (b ⊕ a)

Now this is really cool.  We can apply an associative binary operation with a value against the results of folding that operation against a collection is the same as applying that binary operation with a value against the seed.

As an aside, an associative binary operation is an operation which takes two values from the same type and outputs a value of that type, examples would be +, -, *, /, min, max, ...  We say an operation is associative if and only if:

a ⊕ b = b ⊕ a

This means addition is associative while subtraction is not (2 - 1 != 1 - 2, but 2 + 1 = 1 + 2).

How about looking at some examples of the fusion property?

First we'll look at examples in Clojure.

	(ns fold-fusion-property-tests.clj
	(require [clojure.test :refer [deftest testing are run-tests]]))
	(deftest fusion-property-tests
	(testing "h · fold g w = fold f v"
	(testing " Show: given inc fusioned with sum it must return sum + 1"
	(are [coll] (= (inc (reduce + 0 coll)) (reduce + 1 coll))
	[1]
	[1 1 2 3 5 8]
	[42.0 21.0 10.5 5.25 2.625 1.3125]))
	(testing " Show: (⊕ a) · fold (⊕) b = fold (⊕) (b ⊕ a)"
	(are [coll]
	(are [f a b] (= (f a (reduce f b coll)) (reduce f (f b a) coll))
	+ 1 0
	* 1 100
	min 5 225
	max 9 42)
	[1]
	[1 2 3 4]
	[377 610 987]
	[17711 28657]
	[0.25 0.36 0.42 0.2]
	[1/2 1/3 1/4 1/5]))))
	(run-tests)

view raw fold_fusion_property_tests.clj hosted with ❤ by GitHub

We see in the Clojure example that we are using reduce to fold over a collection of integers (integers are easier to use in examples but this idea is not limited to integers) applying an associative binary operation against each member.  We see that applying the operation with a value against the result is the same as applying that operation and value against the seed.

Next we'll look at examples in ECMAScript 2015 (JavaScript) using Immutable.js.

	let expect = require("expect.js"),
	Immutable = require("immutable");
	describe("h · fold g w = fold f v", () => {
	describe("given inc fused with sum it must return sum + 1", () => {
	Immutable.List([
	[]
	,[1]
	,[1, 1, 2, 3, 5, 8]
	,[42.0, 21.0, 10.5, 5.25, 2.625, 1.3125]
	]).forEach(xs => {
	expect(Immutable.List(xs).reduce((m, x) => m + x, 0) + 1)
	.to.equal(Immutable.List(xs).reduce((m, x) => m + x, 1));
	});
	}),
	describe("(f a) · fold f b = fold f (f b a)", () => {
	Immutable.List([
	[1]
	,[1, 2, 3, 4]
	,[377, 610, 987]
	,[17711, 28657]
	,[0.25, 0.36, 0.42, 0.2]
	]).forEach(xs => {
	Immutable.List([
	[(x, y) => x + y, 1, 0]
	,[(x, y) => x * y, 1, 100]
	,[(x, y) => Math.min(x, y), 5, 225]
	,[(x, y) => Math.max(x, y), 9, 42]
	]).forEach(([f, a, b]) => {
	expect(f(a, Immutable.List(xs).reduce(f, b)))
	.to.equal(Immutable.List(xs).reduce(f, f(b, a)));
	});
	});
	});
	});

view raw foldFusionPropertySpec.js hosted with ❤ by GitHub

We see in the ECMAScript example that we are using Immutable's reduce to fold over a List of integers (again this could be applied against any type) applying the associative binary operation against the members.  Like the Clojure example we see that applying the operation with a value against the result is the same as applying that operation and value against the seed.

We can go further with this idea but I feel this is a good overview of the concept.

Folding Up the Coin Changer Kata

"Whate'er the course, the end is the renown."
-- Shakespeare, All's Well That Ends Well
Act IV Scene IV, Line 36

Coin Changer Kata

The Coin Changer kata has three things which make it a good kata.

1. easy to understand
2. rich set of features
3. lots of realistic possible implementations

Even in today's cashless society, most people understand the idea of handing someone over some money and get change back.  This handing back of change requires the breaking down of the change over coins of different denominations.  Finding which coins to hand back has lots of possible implementations which translate over to things which programmers do every day.

The user story is very simple:

Given a collection of coins of different denominational value
When an amount of change is given
Then it will give back the number of coins for each denomination needed using the least amount of coins possible

A type signature for the function needed could look like the following:

changeFor(coins: int[], amount: int): int[]

We are expecting an array of integers which have different denomination of coins (in the US something like: [25, 10, 5, 1]) and the amount of change needed (something like: 99) giving a resulting array of integers showing how many of each denomination (something like: [3, 2, 0, 4]).

What would we need to be able to do this kata using just Fold?

We'll need to use a tuple (or something like one) to manage the state of the amount of change needed and the resulting array of integers.

Now lets look at an example using a typical full US register with quarters, dimes, nickels, and pennies.  We'll look at getting change for 99 cents.

First Memorize has (99, empty) and X has 25 giving the result of (24, [3]).

Next Memorize has (24, [3]) and X has 10 giving the result of (4, [3, 2]).

Then Memorize has (4, [3, 2]) and X has 5 giving the result of (4, [3, 2, 0]).

Last Memorize has (4, [3, 2, 0]) and X has 1 giving the result of (0, [3, 2, 0, 4]).

Finally obtaining the tuple item with the resulting array of integers to get the change.

Clojure

	(ns fold-coin-changer)
	(defn change-for [coins amount]
	(->> coins
	(reduce
	(fn [{:keys [amount result]} coin]
	{:amount (mod amount coin) :result (cons (quot amount coin) result)})
	{:amount amount :result []})
	:result
	reverse))

view raw fold_coin_changer.clj hosted with ❤ by GitHub

	(ns fold-coin-changer.tests
	(require
	[clojure.test :refer [deftest testing is are run-tests]]
	[fold-coin-changer :as sut]))
	(deftest fold-coin-changer-tests
	(testing "Given register it must return size equal to register size"
	(are [register] (= (count register) (count (sut/change-for register 0)))
	[]
	[1]
	[1 2]
	[1 2 3]))
	(testing "Given pennies it must return amount in pennies"
	(let [pennies (partial sut/change-for [1])]
	(are [amount] (= amount (last (pennies amount)))
	0
	10
	99)))
	(testing "Given full register and amount less than 5 it must return amount as pennies"
	(let [full-register (partial sut/change-for [50 25 10 5 1])]
	(are [amount] (and
	(< amount 5)
	(= amount (last (full-register amount))))
	1
	3
	4)))
	(testing "Given amount and expected with full register it must return expected"
	(let [full-register (partial sut/change-for [50 25 10 5 1])]
	(are [amount expected] (= expected (full-register amount))
	42 [0 1 1 1 2]
	99 [1 1 2 0 4]))))
	(run-tests)

view raw fold_coin_changer_test.clj hosted with ❤ by GitHub

We see with the Clojure code that we seed with a map with a key for the :amount and one for the :result.  We fold over the coins using reduce destructing the memoize value into the amount and result.  We then just calculate the new amount using: amount % coin, follow by inserting the number of coins we get using: amount / coin.  We use cons to show off the coolness that is the thread-last macro (at least that is why I think I coded it this way, it was a little bit ago that I did the gist and I cannot remember why I code with cons over conj).

C#

	using System;
	using System.Collections.Generic;
	using System.Linq;
	using System.Text;
	using System.Threading.Tasks;
	namespace Folder
	{
	public class CoinChanger
	{
	public IEnumerable<int> Coins { get; set; }
	public IEnumerable<int> ChangeFor(int amount)
	{
	return Coins.Aggregate(
	new Tuple<int, List<int>>(amount, new List<int>()),
	(m, coin) =>
	{
	m.Item2.Add(m.Item1/coin);
	return new Tuple<int, List<int>>(m.Item1%coin, m.Item2);
	}).Item2;
	}
	}
	}

view raw CoinChanger.cs hosted with ❤ by GitHub

	using System;
	using System.Collections.Generic;
	using System.Linq;
	using System.Linq.Expressions;
	using System.Text;
	using System.Threading.Tasks;
	using Folder;
	using Xunit;
	namespace FolderTests
	{
	public class CoinChangerTests
	{
	[Fact]
	public void Given0ItMustReturnNoCoins()
	{
	var changer = new CoinChanger
	{
	Coins = new[] {50, 25, 10, 5, 1}
	};
	var actual = changer.ChangeFor(0);
	Assert.All(actual, coin => Assert.Equal(0, coin));
	}
	[Theory]
	[InlineData(new[] { 1 })]
	[InlineData(new[] {5, 1})]
	[InlineData(new[] {50, 25, 10, 5, 1})]
	public void GivenCoinsItMustReturnCollectionWithSameNumber(int[] coins)
	{
	var changer = new CoinChanger
	{
	Coins = coins
	};
	var actual = changer.ChangeFor(0);
	Assert.Equal(coins.Length, actual.Count());
	}
	[Theory]
	[InlineData(1)]
	[InlineData(99)]
	public void GivenPenniesItMustReturnAmount(int amount)
	{
	var changer = new CoinChanger
	{
	Coins = new[] {1}
	};
	var actual = changer.ChangeFor(amount);
	Assert.Equal(amount, actual.Last());
	}
	[Theory]
	[InlineData(1)]
	[InlineData(3)]
	[InlineData(4)]
	public void GivenFullRegisterAndAmountLessThan5ItMustReturnAmountAsPennies(int amount)
	{
	var changer = new CoinChanger
	{
	Coins = new[] {50, 25, 10, 5, 1}
	};
	var actual = changer.ChangeFor(amount);
	Assert.Equal(amount, actual.Last());
	}
	[Theory]
	[InlineData(42, new[] {0, 1, 1, 1, 2})]
	[InlineData(99, new[] {1, 1, 2, 0, 4})]
	public void GivenAmountAndExpectedWithFullRegisterItMustReturnExpected(int amount, int[] expected)
	{
	var changer = new CoinChanger
	{
	Coins = new[] { 50, 25, 10, 5, 1 }
	};
	var actual = changer.ChangeFor(amount);
	Assert.Equal(expected, actual);
	}
	}
	}

view raw CoinChangerTets.cs hosted with ❤ by GitHub

We see with the C# code that we seed using a Tuple (which I think has very ugly syntax in C#).  We then fold over the coins using aggregate just like the Clojure code above.  We calculate the changer results and place them into a new Tuple which we return as the memoize.

ECMAScript 2015

	let _ = require("lodash");
	exports.foldCoinChanger = (coins, amount) =>
	_.foldl(
	coins,
	(m, coin) => {
	m.result.push(_.floor(m.amount / coin));
	m.amount %= coin;
	return m;
	},
	{amount: amount, result: []}).result;

view raw foldCoinChanger.js hosted with ❤ by GitHub

	let sut = require("../src/foldCoinChanger"),
	expect = require("expect.js"),
	_ = require("lodash");
	describe("foldCoinChanger", () => {
	it("Given register it must return size equal to register", () => {
	expect(sut.foldCoinChanger([], 0)).to.have.length(0);
	expect(sut.foldCoinChanger([1, 2], 0)).to.have.length(2);
	expect(sut.foldCoinChanger([1, 2, 3], 0)).to.have.length(3);
	}),
	it("Given pennies it must return amount", () => {
	let pennies = _.partial(sut.foldCoinChanger, [1]);
	expect(_.first(pennies(0))).to.equal(0);
	expect(_.first(pennies(10))).to.equal(10);
	expect(_.first(pennies(99))).to.equal(99);
	}),
	it("Given full register and amount less than 5 it must return amount as pennies", () => {
	let full = _.partial(sut.foldCoinChanger, [50, 25, 10, 5, 1]);
	expect(_.last(full(1))).to.equal(1);
	expect(_.last(full(3))).to.equal(3);
	expect(_.last(full(4))).to.equal(4);
	}),
	it("Given amount and expected with full register it must return expected", () => {
	let full = _.partial(sut.foldCoinChanger, [50, 25, 10, 5, 1]);
	expect(full(42)).to.eql([0, 1, 1, 1, 2]);
	expect(full(99)).to.eql([1, 1, 2, 0, 4]);
	});
	});

view raw foldCoinChangerSpec.js hosted with ❤ by GitHub

In this ECAMScript 2015 example we use lodash's foldl to fold over the coins just like the two examples above.  The seed value is a simple JavaScript object with the members of amount and result given.  We are a bit dirty and mutate the memoize on each call with the changer results but we could argue that this is still "pure" since the mutation happens to an item which is created and used only in side the function.

ECMAScript 2015 and Immutable.js

	let _ = require("lodash"),
	Immutable = require("immutable");
	exports.foldCoinChanger = (coins, amount) =>
	Immutable.List(coins)
	.reduce(
	([result, amount], coin) => [result.push(_.floor(amount / coin)), amount % coin]
	,[Immutable.List(), amount])
	[0].toJS();

view raw foldCoinChanger.js hosted with ❤ by GitHub

	let sut = require("../src/foldCoinChanger"),
	expect = require("expect.js"),
	_ = require("lodash");
	describe("foldCoinChanger", () => {
	it("Given register it must return size equal to register", () => {
	expect(sut.foldCoinChanger([], 0)).to.have.length(0);
	expect(sut.foldCoinChanger([1, 2], 0)).to.have.length(2);
	expect(sut.foldCoinChanger([1, 2, 3], 0)).to.have.length(3);
	}),
	it("Given pennies it must return amount", () => {
	let pennies = _.partial(sut.foldCoinChanger, [1]);
	expect(_.first(pennies(0))).to.equal(0);
	expect(_.first(pennies(10))).to.equal(10);
	expect(_.first(pennies(99))).to.equal(99);
	}),
	it("Given full register and amount less than 5 it must return amount as pennies", () => {
	let full = _.partial(sut.foldCoinChanger, [50, 25, 10, 5, 1]);
	expect(_.last(full(1))).to.equal(1);
	expect(_.last(full(3))).to.equal(3);
	expect(_.last(full(4))).to.equal(4);
	}),
	it("Given amount and expected with full register it must return expected", () => {
	let full = _.partial(sut.foldCoinChanger, [50, 25, 10, 5, 1]);
	expect(full(42)).to.eql([0, 1, 1, 1, 2]);
	expect(full(99)).to.eql([1, 1, 2, 0, 4]);
	});
	});

view raw foldCoinChangerSpec.js hosted with ❤ by GitHub

Last we look at Facebook's open source Immutable.js.  We create an immutable List with the coins which we use to fold over the values using reduce.  The seed value we give it is a simple JavaScript array with an immutable List to hold the results and the amount passed in.  We could use an immutable Map if we wanted to keep it purely immutable.  Like this:

	let _ = require("lodash"),
	Immutable = require("immutable");
	exports.foldCoinChanger = (coins, amount) =>
	Immutable.List(coins)
	.reduce(
	(m, coin) =>
	m.update("result", result => result.push(_.floor(m.get("amount") / coin)))
	.update("amount", amount => amount % coin),
	Immutable.Map({amount: amount, result: Immutable.List()}))
	.get("result")
	.toJS();

view raw foldCoinChanger.js hosted with ❤ by GitHub

	let sut = require("../src/foldCoinChanger"),
	expect = require("expect.js"),
	_ = require("lodash");
	describe("foldCoinChanger", () => {
	it("Given register it must return size equal to register", () => {
	expect(sut.foldCoinChanger([], 0)).to.have.length(0);
	expect(sut.foldCoinChanger([1, 2], 0)).to.have.length(2);
	expect(sut.foldCoinChanger([1, 2, 3], 0)).to.have.length(3);
	}),
	it("Given pennies it must return amount", () => {
	let pennies = _.partial(sut.foldCoinChanger, [1]);
	expect(_.first(pennies(0))).to.equal(0);
	expect(_.first(pennies(10))).to.equal(10);
	expect(_.first(pennies(99))).to.equal(99);
	}),
	it("Given full register and amount less than 5 it must return amount as pennies", () => {
	let full = _.partial(sut.foldCoinChanger, [50, 25, 10, 5, 1]);
	expect(_.last(full(1))).to.equal(1);
	expect(_.last(full(3))).to.equal(3);
	expect(_.last(full(4))).to.equal(4);
	}),
	it("Given amount and expected with full register it must return expected", () => {
	let full = _.partial(sut.foldCoinChanger, [50, 25, 10, 5, 1]);
	expect(full(42)).to.eql([0, 1, 1, 1, 2]);
	expect(full(99)).to.eql([1, 1, 2, 0, 4]);
	});
	});

view raw foldCoinChangerSpec.js hosted with ❤ by GitHub

I am not a huge fan of stringly typed accessors, but I understand why they use them.  Both ways are good and would really come down to to performance and readability.

The End

Thus ends our tour of All You Need is Fold, but this is not the end of the uses of Fold, for Fold is universal.

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.

The Cloud-Capped Towers OR AutoFixture

"The cloud-capped towers, the gorgeous palaces,
The solemn temples, the great globe itself,
Yea, all which it inherit, shall dissolve,
And, like this insubstantial pageant faded,

Leave not a rack behind. We are such stuff"
-- Shakespeare, The Tempest
Act IV, Scene I, Lines 152 -156

In my day-to-day work I do a lot of .Net programming.  It seem at some point in each of the applications I am either enhancing or creating I ended including Mark Seemann's AutoFixture (if it is not already in use).  AutoFixture is an easy way to create a fixture object.  A fixture object is an object which centralizes your helper methods in your test code, like methods which create your system under test and help generate test data.

Fixture objects are great and I often find myself wanting one in my day-to-day work, but I am lazy.  Since I am lazy I do not want to go to all the trouble of creating my own fixture object, to quote Homer Simpson, "Can't someone else do it".  Luckily in the .Net realm someone already has, Mark Seemann.  AutoFixture lets you get the best of all worlds, you get a fixture object and you do not have to write the framework around it!  (working with it for a few years now, I can say it is well thought out and not a big hair ball, see also Simple Made Easy for the full reference)

How about some examples?  (taken from the AutoFixture cheat sheet and rewritten using xUnit)

	using System;
	using System.Collections.Generic;
	using System.Linq;
	using Ploeh.AutoFixture;
	using Ploeh.AutoFixture.Xunit2;
	using Xunit;
	namespace AutoFixtureDemo
	{
	public class Demo
	{
	public class MyClass
	{
	public int Echo(int expected)
	{
	return expected;
	}
	}
	[Fact]
	public void IntroTetFromGitHub()
	{
	var fixture = new Fixture();
	var expected = fixture.Create<int>();
	var sut = fixture.Create<MyClass>();
	var actual = sut.Echo(expected);
	Assert.Equal(expected, actual);
	}
	[Theory, AutoData]
	public void IntroXunitTetFromGitHub(int expected, MyClass sut)
	{
	var actual = sut.Echo(expected);
	Assert.Equal(expected, actual);
	}
	[Theory, AutoData]
	public void CheatSheetTestsForStrings(Fixture fixture)
	{
	Assert.IsType<string>(fixture.Create<string>());
	var seed = "seed";
	Assert.Contains(seed, fixture.Create(seed));
	}
	[Theory, AutoData]
	public void CheatSheetTestsForNumbers(Fixture fixture)
	{
	Assert.IsType<int>(fixture.Create<int>());
	}
	public class ComplexType
	{
	public string Name;
	public int Number;
	}
	[Theory, AutoData]
	public void CheatSheetTestsForComplexTypes(ComplexType complexType)
	{
	Assert.NotNull(complexType.Name);
	Assert.NotNull(complexType.Number);
	Assert.Contains("Name", complexType.Name);
	}
	public abstract class AbstractType {}
	public class MyFakeAbstract : AbstractType { }
	public interface IInterface { }
	public class MyFakeInterface : IInterface { }
	[Theory, AutoData]
	public void CheatSheetTestsForAbstractTypes(Fixture fixture)
	{
	fixture.Register<AbstractType>(() => new MyFakeAbstract());
	fixture.Register<IInterface>(() => new MyFakeInterface());
	Assert.IsType<MyFakeAbstract>(fixture.Create<AbstractType>());
	Assert.IsType<MyFakeInterface>(fixture.Create<IInterface>());
	}
	[Theory, AutoData]
	public void CheatSheetTestsForReplacingDefaultAlgorithms(string replacement, Fixture fixture)
	{
	Assert.NotEqual(replacement, fixture.Create<string>());
	fixture.Register<string>(() => replacement);
	var actual = fixture.Create<string>();
	Assert.Equal(replacement, actual);
	}
	[Theory, AutoData]
	public void CheatSheetTestsSequences(Fixture fixture)
	{
	Assert.Equal(3, fixture.CreateMany<string>().Count());
	Assert.Equal(3, fixture.CreateMany<int>().Count());
	Assert.Equal(3, fixture.CreateMany<int>().Distinct().Count());
	const int expected = 100;
	Assert.Equal(expected, fixture.CreateMany<int>(expected).Count());
	Assert.Equal(3, fixture.CreateMany<MyClass>().Count());
	}
	[Theory, AutoData]
	public void CheatSheetTestsAddManyTo(Fixture fixture)
	{
	var list = new List<int>();
	Assert.Equal(0, list.Count);
	fixture.AddManyTo(list);
	Assert.Equal(3, list.Count);
	}
	public class MyClassWithProperties
	{
	public int Number;
	public string SomeString { get; set; }
	}
	[Theory, AutoData]
	public void CheatSheetTestsSetProperty(Fixture fixture)
	{
	var expected = "my string";
	var actual = fixture
	.Build<MyClassWithProperties>()
	.With(w => w.SomeString, expected)
	.Create();
	Assert.Equal(expected, actual.SomeString);
	actual = fixture
	.Build<MyClassWithProperties>()
	.Without(w => w.SomeString)
	.Create();
	Assert.Null(actual.SomeString);
	var counter = 0;
	fixture
	.Build<MyClass>()
	.Do(_ => ++counter)
	.Create();
	Assert.Equal(1, counter);
	}
	[Theory, AutoData]
	public void CheatSheetTestsCustomizeTypes(Fixture fixture)
	{
	var expected = fixture.Create<int>();
	var counter = 0;
	fixture
	.Customize<MyClassWithProperties>(c => c
	.Do(_ => ++counter)
	.WithAutoProperties()
	.With(w => w.Number, expected));
	var myClass = fixture.Create<MyClassWithProperties>();
	Assert.Equal(1, counter);
	Assert.Equal(expected, myClass.Number);
	}
	}
	}

view raw Demo.cs hosted with ❤ by GitHub

We see in the above lots of wonderful things.

• We can walk up to the fixture object and ask it for some test data.  
• We can use the AutoData attribute and ask for test data.  
• We can register implementation for abstract types.  
• We can create collections of test data.
• We can build specific test data saying what attributes we care about and letting the fixture object set up the rest.
• We can even have a do method to allow for modification outside of the object we are having the fixture object create (this is not good design but sometimes it is needed).

As I work more with AutoFixture I find more and more uses for it.

Another framework I use a lot in my day-to-day .Net programming is Moq.  Guess what, AutoFixture can be uses as an auto-mocking container with Moq (and it has plugins for other mocking frameworks too).

Yet another example.  (using MS Test taken from an overview of AutoFixture I did at work recently)

	using System;
	using Microsoft.VisualStudio.TestTools.UnitTesting;
	using Moq;
	using Ploeh.AutoFixture;
	using Ploeh.AutoFixture.AutoMoq;
	namespace AutoFixtureDemo.MSTest
	{
	public class Echoer
	{
	private ILogger _logger;
	private readonly ISaver _saver;
	public Echoer(ILogger logger, ISaver saver)
	{
	_logger = logger;
	_saver = saver;
	}
	public string Echo(string value)
	{
	_logger.Log(value);
	var result = _saver.Save(value);
	if (result.Result) _logger.Log("Successfully saved!");
	return value;
	}
	}
	[TestClass]
	public class Demo
	{
	private IFixture _fixture;
	private Echoer _sut;
	private Mock<ILogger> _spyLogger;
	private Mock<ISaver> _spySaver;
	[TestInitialize]
	public void BeforeEach()
	{
	_fixture = new Fixture().Customize(new AutoMoqCustomization());
	_spyLogger = _fixture.Freeze<Mock<ILogger>>();
	_spySaver = _fixture.Freeze<Mock<ISaver>>();
	_sut = _fixture.Create<Echoer>();
	}
	[TestMethod]
	public void GivenStringItMustEchoIt()
	{
	var expected = _fixture.Create<string>();
	var actual = _sut.Echo(expected);
	Assert.AreEqual(expected, actual);
	}
	[TestMethod]
	public void GivenNullItMustReturnNull()
	{
	var actual = _sut.Echo(null);
	Assert.IsNull(actual);
	}
	[TestMethod]
	public void GivenStringItMustLogIt()
	{
	var expected = _fixture.Create<string>();
	_sut.Echo(expected);
	_spyLogger.Verify(v => v.Log(expected));
	}
	[TestMethod]
	public void GivenStringItMustSaveIt()
	{
	var expected = _fixture.Create<string>();
	_sut.Echo(expected);
	_spySaver.Verify(v => v.Save(expected));
	}
	[TestMethod]
	public void GivenStringAndSuccessfulSaveItMustLogSuccess()
	{
	_spySaver
	.Setup(s => s.Save(It.IsAny<string>()))
	.Returns(_fixture.Build<SaverResult>().With(w => w.Result, true).Create());
	_sut.Echo(_fixture.Create<string>());
	_spyLogger.Verify(v => v.Log("Successfully saved!"));
	}
	}
	public interface ILogger
	{
	void Log(string message);
	}
	public interface ISaver
	{
	SaverResult Save(string value);
	}
	public class SaverResult
	{
	public bool Result { get; set; }
	}
	}

view raw Demo.cs hosted with ❤ by GitHub

We see in this example that we had a simple class called Echo which got top hatted into having logging and a backup added to it.  The interactions with the logger and back-upper need to be tested, luckily we can tell the fixture object that we would like to get spy objects for the logger and back-upper.  These spies from AutoFixture are Moq mocks which allows us to verify that the behaviors we want.

By using AutoFixture and Moq we can meet all the "needs" of Top Hats everywhere.

(The term Top Hats comes from Uncle Bob's Clean Coder series episode 7, in which there is a scene with an Architect talking about choosing an IDE and Database for a project hence the term Top Hat and top hatting to describe this type of "architecture".)

I find that AutoFixture allows me to simplify my test code (simple as discussed in Simple Made Easy) and allows me to stay focus on what I am actually trying to test.

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. 

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.

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.

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.

If True or False I Know Not

"I idly heard; if true or false I know not."

-- Shakespeare, King John
Act IV, Scene II, Line 124

Welcome Back

This is the next in the series of post on Dr. Graham Hutton's excellent paper, "A tutorial on the universality and expressiveness of fold", this time around we'll look at Oring.  Dr. Hutton has given Oring the following definition:

or :: [Bool] → Bool
or = fold (∨) False

The idea is that we Fold an Or function with a seed value of False.  If one of the members of the collection is True we Or it with False giving us True, else if none of the members of the collection are True we will end up with the value of False.

In the simple example below we'll see that if we have a single value of True then the end result will be True.

At the start we have a Seed value of False with collection containing False, True, and False.

First time the Memorize has False and X has False.

Second time the Memorize has False and X has True.

Third time the Memorize has True and X has False giving use the finally value of True.

Let us now look at this in sweet, sweet code.

Clojure

	(ns fold-or)
	(defn fold-or
	"or = fold (∨) False"
	[& facts]
	(reduce #(or %1 %2) false facts))

view raw Fold_Or.clj hosted with ❤ by GitHub

	(ns fold-or.tests
	(require
	[clojure.test :refer [deftest testing are run-tests]]
	[fold-or :as sut]))
	(deftest fold-or-tests
	(testing "Given all true it must return true"
	(are [truths] (true? (apply sut/fold-or truths))
	[true]
	[true true]
	(repeat 100 true)))
	(testing "Given all false it must return false"
	(are [falsehoods] (false? (apply sut/fold-or falsehoods))
	[false]
	[false false]
	(repeat 100 false)))
	(testing "Given some true and false it must return true"
	(are [facts] (true? (apply sut/fold-or facts))
	[false true]
	[true false]
	[false true false]
	[true false false])))
	(run-tests)

view raw Fold_Or.Tests.clj hosted with ❤ by GitHub

In the Clojure code that we use the or macro and a seed value of false in order to create an Oring function using the higher order function of reduce.  Since reduce is expecting a function and not a macro we need to create a lambda function to wrap the or macro.

C#

	using System.Linq;
	namespace Folder
	{
	public static class Folder
	{
	public static bool Or(params bool[] facts)
	{
	return facts.Aggregate(false, (m, x) => m || x);
	}
	}
	}

view raw Folder.cs hosted with ❤ by GitHub

	using Xunit;
	using static Folder.Folder;
	namespace FolderTests
	{
	public class FolderTests
	{
	[Theory]
	[InlineData(new[] { true })]
	[InlineData(new[] { true, true })]
	[InlineData(new[] { true, true, true })]
	public void GivenOnlyTrueItMustReturnTrue(bool[] truths)
	{
	Assert.True(Or(truths));
	}
	[Theory]
	[InlineData(new[] { false })]
	[InlineData(new[] { false, false })]
	[InlineData(new[] { false, false, false })]
	public void GivenOnlyFalseItMustReturnFalse(bool[] falsehoods)
	{
	Assert.False(Or(falsehoods));
	}
	[Theory]
	[InlineData(new[] { true, false })]
	[InlineData(new[] { false, true })]
	[InlineData(new[] { false, true, false })]
	[InlineData(new[] { false, false, true })]
	public void GivenSomeTrueAndFalseItMustReturnTrue(bool[] facts)
	{
	Assert.True(Or(facts));
	}
	}
	}

view raw FolderTests.cs hosted with ❤ by GitHub

We see in the C# code that we can use the LINQ aggregate method on the collection we are folding.  We give the aggregate a seed value of false and in the lambda we simply takes the memorize and the current member and or them.

JavaScript (ECMAScript 2015)

	let _ = require("lodash");
	exports.foldOr = (...facts) =>
	_.foldl(facts, (m, x) => m || x, false);

view raw foldOr.js hosted with ❤ by GitHub

	let sut = require("../src/foldOr"),
	expect = require("expect.js");
	describe("foldOr", () => {
	it("Given all true it must return true", () => {
	expect(sut.foldOr(true)).to.be.ok();
	expect(sut.foldOr(true, true)).to.be.ok();
	expect(sut.foldOr(true, true, true)).to.be.ok();
	}),
	it("Given all false it must return false", () => {
	expect(sut.foldOr(false)).not.to.be.ok();
	expect(sut.foldOr(false, false)).not.to.be.ok();
	expect(sut.foldOr(false, false, false)).not.to.be.ok();
	}),
	it("Given some true and false it must return true", () => {
	expect(sut.foldOr(true, false)).to.be.ok();
	expect(sut.foldOr(false, true)).to.be.ok();
	expect(sut.foldOr(false, true, false)).to.be.ok();
	expect(sut.foldOr(false, false, true)).to.be.ok();
	});
	});

view raw foldOrSpec.js hosted with ❤ by GitHub

Using lodash's foldl function along with Babel.js we are able to create an Oring function by folding over the collection and passing it to a lambda function which ors the current member of the collection with the memorize value.  We give a seed value of false thus causing the initial value of the memorize to be false.

Until Next Time

There you have it an Oring function using nothing but Fold.  Thus "proving" that all you need is Fold.

Approaching the Fold

"Approach the fold and cull th' infected forth"
-- Shakespeare, Timon of Athens
Act V, Scene IV, Line 43

Welcome

In Graham Hutton's excellent paper, "A tutorial on the universality and expressiveness of fold", the first function that is looked at is And.  Dr. Hutton gives And the following definition:

and :: [Bool] → Bool
and = fold (∧) True

The idea being that we give Fold an And function with a seed value of True.  If one of the members of the collection given is False the Anding it with True will yield a value of False and thus the end result will be False.  If no member of the collection given is False then the end result will be True.

Let us look at this in code.

Clojure

	(ns fold-and)
	(defn fold-and
	"and = fold (∧) True"
	[& facts]
	(reduce #(and %1 %2) true facts))

view raw Fold_And.clj hosted with ❤ by GitHub

	(ns fold-and.tests
	(require
	[clojure.test :refer [deftest testing are is run-tests]]
	[fold-and :as sut]))
	(deftest fold-and-tests
	(testing "Given all true it must return true"
	(are [truths] (true? (apply sut/fold-and truths))
	[true]
	[true true]
	(repeat 100 true)))
	(testing "Given all false it must return false"
	(are [falsehoods] (false? (apply sut/fold-and falsehoods))
	[false]
	[false false]
	(repeat 100 false)))
	(testing "Given some true and some false it must match every's result"
	(are [facts] (= (every? identity facts) (apply sut/fold-and facts))
	[true]
	[false true]
	[true true]
	[false true]
	[false false]
	(repeat 100 true)
	(repeat 100 false))))
	(run-tests)

view raw Fold_And.Tests.clj hosted with ❤ by GitHub

To create an Anding function we'll use reduce along with the and macro with a seed of true.  Since and is a macro, we'll need to wrap it in a function in order to be able to use it in reduce.

C#

	using System.Linq;
	namespace Folders
	{
	public class FoldAnd
	{
	public bool And(params bool[] facts)
	{
	return facts.Aggregate(true, (m, x) => m && x);
	}
	}
	}

view raw FoldAnd.cs hosted with ❤ by GitHub

	using System.Linq;
	using Folders;
	using Xunit;
	namespace FoldersTests
	{
	public class FoldAndTests
	{
	[Theory]
	[InlineData(new[] { true })]
	[InlineData(new[] { true, true })]
	[InlineData(new[] { true, true, true })]
	public void GivenTrueValuesItMustReturnTrue(bool[] truths)
	{
	var sut = new FoldAnd();
	var actual = sut.And(truths);
	Assert.True(actual);
	}
	[Theory]
	[InlineData(new[] { false })]
	[InlineData(new[] { false, false })]
	[InlineData(new[] { false, false, false })]
	public void GivenFalseValuesItMustReturnFalse(bool[] falsehoods)
	{
	var sut = new FoldAnd();
	var actual = sut.And(falsehoods);
	Assert.False(actual);
	}
	[Theory]
	[InlineData(new[] { true })]
	[InlineData(new[] { false, true })]
	[InlineData(new[] { true, true })]
	[InlineData(new[] { false, false })]
	[InlineData(new[] { false, false, false })]
	[InlineData(new[] { false, true, false })]
	[InlineData(new[] { true, true, true })]
	public void GivenSomeTrueAndSomeFalseValuesItMustReturnFalse(bool[] facts)
	{
	var expected = facts.All(a => a);
	var sut = new FoldAnd();
	var actual = sut.And(facts);
	Assert.Equal(expected, actual);
	}
	}
	}

view raw FoldAndTests.cs hosted with ❤ by GitHub

We'll use the LINQ function Aggregate along && and a value of true to create an Anding function.

JavaScript

	var _ = require("lodash");
	exports.foldAnd = function foldAnd(/*facts*/) {
	var facts = _.toArray(arguments);
	return _.foldl(facts, function(m, x) {return m && x}, true);
	};

view raw foldAnd.js hosted with ❤ by GitHub

	var sut = require("../src/foldAnd"),
	expect = require("expect.js"),
	_ = require("lodash");
	describe("foldAnd", function(){
	it("Given all true it must return true", function(){
	expect(sut.foldAnd(true)).to.be.ok();
	expect(sut.foldAnd(true, true)).to.be.ok();
	expect(sut.foldAnd(true, true, true)).to.be.ok();
	}),
	it("Given all false it must return false", function(){
	expect(sut.foldAnd(false)).not.to.be.ok();
	expect(sut.foldAnd(false, false)).not.to.be.ok();
	expect(sut.foldAnd(false, false, false)).not.to.be.ok();
	}),
	it("Given some true and false it must return the same result as every", function(){
	expect(sut.foldAnd(true, false)).to.equal(_.every([true, false]));
	expect(sut.foldAnd(false, true)).to.equal(_.every([false, true]));
	expect(sut.foldAnd(false, true, false)).to.equal(_.every([false, true, false]));
	expect(sut.foldAnd(false, false, true)).to.equal(_.every([false, false, true]));
	})
	});

view raw foldAndSpec.js hosted with ❤ by GitHub

We see that by using lodash's foldl function with && and the value true we can create an Anding function.

ECMAScript 2015

	let _ = require("lodash");
	exports.foldAnd = (...facts) =>
	_.foldl(facts, (m, x) => m && x, true);

view raw foldAnd.js hosted with ❤ by GitHub

	let sut = require("../src/foldAnd"),
	expect = require("expect.js"),
	_ = require("lodash");
	describe("foldAnd", () => {
	it("Given all true it must return true", () => {
	expect(sut.foldAnd(true)).to.be.ok();
	expect(sut.foldAnd(true, true)).to.be.ok();
	expect(sut.foldAnd(true, true, true)).to.be.ok();
	}),
	it("Given all false it must return false", () => {
	expect(sut.foldAnd(false)).not.to.be.ok();
	expect(sut.foldAnd(false, false)).not.to.be.ok();
	expect(sut.foldAnd(false, false, false)).not.to.be.ok();
	}),
	it("Given some true and false it must return the same result as every", () => {
	expect(sut.foldAnd(true, false)).to.equal(_.every([true, false]));
	expect(sut.foldAnd(false, true)).to.equal(_.every([false, true]));
	expect(sut.foldAnd(false, true, false)).to.equal(_.every([false, true, false]));
	expect(sut.foldAnd(false, false, true)).to.equal(_.every([false, false, true]));
	})
	});

view raw foldAndSpec.js hosted with ❤ by GitHub

Since we live in the future, we'll use Babel to allow us to use ECMAScript 2015.  We see again that by using lodash's foldl with && along with the value true we now have an Anding function.

Fin

There you have it the And function using Fold, showing once again that all you need is Fold.

Bro, Do You Even FizzBuzz?!?

"Do you bite your thumb at us, sir?"
-- Shakespeare, Romeo and Juliet
Act I, Scene I, Line 43

FizzBuzz as an interview kata has been getting a lot of bad press lately.  Part of the bad press has been around having to use modulus in the solution.  I am not sure how people have been explaining FizzBuzz in interviews, but you do not have to know anything about the mod operator in order to solve the problem.

Here is a solution in Clojure which does not use modulus.

	(ns fizz-buzz)
	(defn fizz-buzzer [n]
	(let [translation (->
	(map str (cycle ["Fizz" "" ""]) (cycle ["Buzz" "" "" "" ""]))
	(nth n))]
	(if (empty? translation)
	(str n)
	translation)))

view raw Fizz_Buzz.clj hosted with ❤ by GitHub

	(ns fizz-buzz.tests
	(require
	[clojure.test :refer [deftest testing is run-tests]]
	[fizz-buzz :as sut]))
	(deftest fizz-buzz-tests
	(testing "Given a value divisible by 3 result must contain Fizz"
	(is (.contains (sut/fizz-buzzer 0) "Fizz"))
	(is (.contains (sut/fizz-buzzer 3) "Fizz"))
	(is (.contains (sut/fizz-buzzer 9) "Fizz"))
	(is (.contains (sut/fizz-buzzer 15) "Fizz")))
	(testing "Given a value divisible by 5 result must contain Buzz"
	(is (.contains (sut/fizz-buzzer 0) "Buzz"))
	(is (.contains (sut/fizz-buzzer 5) "Buzz"))
	(is (.contains (sut/fizz-buzzer 25) "Buzz"))
	(is (.contains (sut/fizz-buzzer 15) "Buzz")))
	(testing "Given a value divisible by 15 it must return FizzBuzz"
	(is (= "FizzBuzz" (sut/fizz-buzzer 0)))
	(is (= "FizzBuzz" (sut/fizz-buzzer 15)))
	(is (= "FizzBuzz" (sut/fizz-buzzer 225))))
	(testing "Given a value not divisible by 3, 5, or 15 it must return value as string"
	(is (= "1" (sut/fizz-buzzer 1)))
	(is (= "2" (sut/fizz-buzzer 2)))
	(is (= "1111" (sut/fizz-buzzer 1111)))))
	(run-tests 'fizz-buzz.tests)

view raw Fizz_Buzz.Tests.clj hosted with ❤ by GitHub

This solution is using cycles and zip.  The odds are low of someone knowing how to use cycle and zip but not knowing modulus.  The point is that you do not need to know about modulus to do the kata.

In interviews I do, I'll tell the person about modulus if they get stuck.  The point of using a kata in an interview is to make sure that person who claims to be a programmer can actually program and that you can work with the person.

Still if the whole modulus thing has you worried, try the Roman Numeral kata.

Here is a solution in C# I did few minutes before an interview on Thursday (pro-tip, always make sure you can do the kata in short amount of time before you ask someone else to do it in an interview).

	using System;
	using System.Collections.Generic;
	using System.Linq;
	using System.Runtime.InteropServices.ComTypes;
	using System.Text;
	using System.Threading.Tasks;
	using Xunit;
	namespace RomanNumeral
	{
	public class Romanize
	{
	public string ToRoman(int value)
	{
	return new Dictionary<int, string>
	{
	{40, "XL"},
	{10, "X"},
	{9, "IX"},
	{5, "V"},
	{4, "IV"},
	{1, "I"}
	}.Aggregate(string.Empty, (m, _) =>
	{
	while (_.Key <= value)
	{
	value -= _.Key;
	m += _.Value;
	}
	return m;
	});
	}
	}
	public class RomanizeTests
	{
	[Theory]
	[InlineData(0, "")]
	[InlineData(1, "I")]
	[InlineData(2, "II")]
	[InlineData(3, "III")]
	[InlineData(4, "IV")]
	[InlineData(5, "V")]
	[InlineData(9, "IX")]
	[InlineData(39, "XXXIX")]
	[InlineData(49, "XLIX")]
	public void Given0ItMustReturnEmptyString(int value, string expected)
	{
	var sut = new Romanize();
	var actual = sut.ToRoman(value);
	Assert.Equal(expected, actual);
	}
	}
	}

view raw Romanize.cs hosted with ❤ by GitHub

Again, the goal of the interview kata should be to see if the person can actually program and to see what they are like to work with.

"No, sir, I do not bite my thumb at you, sir. But
I bite my thumb, sir."

-- Shakespeare, Romeo and Juliet
Act I, Scene I, Lines 49-50