Showing posts with label es6. Show all posts
Showing posts with label es6. Show all posts

Sunday, October 18, 2015

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.



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.



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.

Sunday, October 11, 2015

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




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#



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



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



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:



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.

Sunday, October 4, 2015

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




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#




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




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.

Sunday, September 13, 2015

Filter, Guarding You From Fold

"You and your ways; whose wraths to guard you from,"
-- Shakespeare, The Tempest

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



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#



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



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. 

Monday, September 7, 2015

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




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#




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




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.


Saturday, August 29, 2015

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.

Sunday, August 23, 2015

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.

Sunday, August 16, 2015

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.


Sunday, August 9, 2015

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.

Sunday, June 7, 2015

One Data Structure to Rule Them All

"Mark Antony, shall we give sign of battle?"
-- Shakespeare, Julius Caesar
Act V, Scene I, Line 23

Intro


For decades the battle cry of the LISP family of languages has been:

"It is better to have 100 functions operate on one data structure than 10 functions on 10 data structures."
-- Alan J. Perlis
Epigrams on Programming, #9

What is this one data structure to rule them all?  The list?  Well yes and no.  In practice I would say, at least in Clojure, it would be the Map data structure (not to be confused with the Higher Order Function called Map).

Say we have the following data structure:


We can say that a Hobbit is made up of a mappings of name, age, family, and past time to values.

JavaScript


With ECMAScript 6 using Lodash we can use the pick and get functions to work with objects like they were Maps.


In the example above we see that with the pick we can obtain a new Map by selecting the attributes that we want.  If it is not found then it simply want be placed in the resulting Map.

If all that is wanted is one value from the Map then we can use the get function to obtain the value. 

The get function let's us provide default values.

_.get(bilbo, 'none', 'not found')
.should.equal('not found');

_.pick(bilbo, 'none')
.should.eql({});
This helps in being able to tell if the value of the attribute is null or if the attribute does not exist.

Clojure


With Clojure we can use the keyword, get, and select-keys functions (to name a few) to work with Map data structures.


In the example above we see that we can use keywords as functions and that the Map data structure its self can be used as a function.

(is (= "Bilbo" (:name bilbo)))
(is (= "Bilbo" (bilbo :name)))

Like the Lodash get function, the get function let's us provide default values.

(is (= nil (get bilbo :none)))
(is (= :not-found (get bilbo :none :not-found)))

This again helps us in being able to tell if the keyword is not found or if the value of associated with the keyword is nil.

(is (= nil (bilbo :none)))
(is (= nil (:none bilbo)))

While using the keyword as a function for an association that does not exist will return nil.

We see also that select-keys acts much like Lodash's pick, in that it returns a new Map with the keyword associations selected.

Clojure's select-keys

(is (= {:name "Bilbo"}
(select-keys bilbo [:name])))
(is (= {:name "Bilbo" :family ["Baggins" "Took"]}
(select-keys bilbo [:name :family])))

Lodash's pick

_.pick(bilbo, 'name')
.should.eql({name: 'Bilbo'});
_.pick(bilbo, ['name', 'family'])
.should.eql({name: 'Bilbo', family: ['Baggins', 'Took']});

Fin

There you have it, Map,  the one data structure to rule them all.

Saturday, May 30, 2015

Destructuring in Clojure and ES6

"I do not like ‘ But yet;’ it does allay
The good precedence. Fie upon ‘ But yet!’

‘But yet' is as a gaoler to bring forth
Some monstrous malefactor.
"
-- Shakespeare, Antony and Cleopatra
Act II, Scene V, Lines 50 - 53

Intro


Sometimes your cup is over flowing and all you want is a sip.  This is where destructuring comes into play.

Say you have the following data structure.


If you only needed the Hobbit's name and family you could either drill into the data structure to obtain them or you could communicate to future readers of your code (which most likely will be you) that you only need name and family from hobbit by destructuring hobbit in the function which consume it.

JavaScript


In ECMAScript 6 we could do the following:



In the JavaScript above we see that we can destructure Bilbo to get just the name and family (which is renamed to parents) using: let {name, family:parents} = bilbo;

We see also that we can set up a function which will expect data mapping which include a name and family and then use those in its code.

let hobbies = ({name, pastTime:hobbies}) => name + ' enjoys ' + hobbies.join(', ');

The nice thing about using a data map is that we can reuse the method above with different data mappings and as long as they have a mapping for a name and family we are good.  This is what Rich Hickey was talking about in Simple Made Easy.  By using data mappings as our data transfer objects we uncomplect our code and allow for more flexibility.

Clojure


In Clojure destructuring would look like this:



Like the JavaScript code above we see we can rename while destructuring.

(let [{name :name
parents :family} bilbo]
(is (= "Bilbo" name))
(is (= ["Baggins" "Took"] parents)))

We see also that we can define a function which takes a data map in which we expect a keyword of name and another of past-time.

(defn hobbies [{name :name hobbies :past-time}]
(str name " enjoys "
(clojure.string/join ", " hobbies)))

Again we see from the created of Clojure, Rich Hickey, how using a data map in our interface allows us to reuse this function on a differently structured data map as long as it has the keywords of name and past-time.

Extro


There we have it, the ability to sip with destructuring.

Sunday, May 17, 2015

Intro to Higher Order Functions

"Plucking the grass to know where sits the wind"
-- Shakespeare, The Merchant of Venice
Act I, Scene I, Line 19

Intro


Step on up.  Come one, come all. See the amazing function which produces other functions.  See the marvelous function which consumes other functions.  See things which you will tell your grandkids about.

Functions Producing Functions


Our first sight is the amazing function which produces other functions.

function A produces function B


In JavaScript and Clojure we would have the following:



We see in repl.js that we are having a return b which returns the string 'Bilbo'.  Likewise in repl_es6.js we see the first lambda return another lambda which returns the string 'Bilbo'.  In repl.clj we see the function a returns the function b which returns the string "Bilbo".  Three examples of a function producing another function.

Functions Consuming Functions


Our next sight is a function which consumes another function.

function A consumes function B


In JavaScript and Clojure we would have the following:



We see in repl.js that we are having function a consume function b which when invoked returns the string 'Bilbo'.  Likewise in repl_es6.js we see the first lambda consumes the lambda passed in which when invoked returns the string 'Bilbo'.  In repl.clj we see the function a consumes the function b which when invoked returns the string "Bilbo".  Three examples of a function consuming another function.

Pluck


The next sight we see Pluck taking apart a dwarf.



In JavaScript and Clojure we would have the following:



We see in repl.js and repl_es6.js we can use lodash's Pluck function extract the name property from our dwarves.  Likewise in repl.clj we can use the Map function with the :name keyword to extract the name value form our dwarves.

Reduce


This last sight to see is a function which will Reduce its input to a single value.



In JavaScript and Clojure we would have the following:



In repl.js and repl_es6.js we can use lodash's Reduce / Foldl function to sum up the values of 1, 2, 3, and 4 to get the value of 10, we can leave out the seed value and still get 10, or we can use a seed value of 100 to get 110.  Likewise in repl.clj we can use the Reduce function to sum up the values of 1, 2, 3, and 4 to get again 10, we can also not give a seed value or given it a different value just as before.

Fin


Thank you and watch your step on the way out.