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

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#

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

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

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#

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)

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

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#

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)

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

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#

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

JavaScript

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

ECMAScript 2015

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.



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).



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