On Zipping

"With those legions
Which I have spoke of, whereunto your levy
Must be supplyant: the words of your commission
Will tie you to the numbers and the time
Of their despatch."

-- Shakespeare, Cymbeline

Act III, Scene VIII, Lines 12.2 - 16.1

Zipping is a very simple concept from higher order functions which does not get talked about much.

With a zip you have a number of collection which you wish to apply a function against each matching member in order to produce a single "zipped" collection.

In general:

GIVEN a function f

FOREACH x_i in X, y_i in Y, ...
  r_i = f(x_i, y_i, ..)

GIVING r_i in R

The function f is the "zipper", while X, Y, ... are the collections being zipped with R being the zipped result.

A simple example with 2 collections:

Let's use Add as the "zipper", [1, 2, 3] as the first collection, and [10, 20, 30] as the second collection.

We see that this gives us the resulting collection of [11, 22, 33].

What should happen if the first or second collection has a different number of elements?

OR

We'll look at what C#, Clojure, and Haskell do in these cases.



We see that they each have a resulting collection as large as the smallest input collection and simply just ignore the rest of the input in the larger collection.  There you have it a very simple introduction to Zip.

Bird Watching with Clojure -- The Thrush(y)

"With heigh, with heigh, the thrush and the jay,
Are summer songs for me and my aunts"
Shakespeare, The Winter's Tale
Act IV, Scene III, Lines 10-11

The Thrush

As the wind gently rustles the leaves in the combinator forest.  You sing DO RA and hear sung back to you RA DO.  You sing RA ME and hear ME RA, you sing DO DO and hear DO DO back.  You have just heard the Thrush.

The Thrush or T combinator basically flips your parameters.

T x f = f x

In the Data Aviary Bird package for Haskell it is defined in the following way:

-- | T combinator - thrush.
-- Haskell @(\#)@ in Peter Thiemann\'s Wash, reverse application.
thrush :: a -> (a -> b) -> b
thrush x f = f x

We see that when we call it we pass a value as our first parameter followed by the function we wish to apply the value against.  This is useful when you want to pipe your data through a bunch of functions.

Thrush in F#

In fact in F# this is exactly what the |> (forward pipe) does.  It is defined in the following way:

let (|>) x f = f x

Yep, the forward pipe is nothing more than a Thrush!

Thrush in Joy

In Joy the Thrush goes by the name swap, which makes perfect sense.  It is defined in the following way:

[B] [A] swap == [A] [B]

Thrush in JavaScript

Reg Braithwaite of allong.es fame has a JavaScript library which is perfect for learning combinators called oscin.es.  The Thrush is defined in the following way in oscin.es:

  function Thrush (a, b) {

    return b.call(this, a)

  }

  function T (a) { return function _T (b) {

    return b(a)

  }}

This exactly what we would expect looking at the Haskell and F# code above.

This is very similar to how Reginald defined the Thrush in Ruby in his excellent book, Kestrels, Quirky Birds, and Hopelessly Egocentricity:

thrush.call(a_value).call(a_proc)
  => a_proc.call(a_value)

Thrush(y) in Clojure

Clojure has two macros which are Thrushy (Michael Fogus has an excellent post on why they are Thrushy) the -> and ->> macros.

Say we wanted to do the following:

get the sum of the even integers from 1 to 100

We can break this requirement down into a few steps.

1. get the integers from 1 to 100
2. get the even integers from 1
3. sum the integers from 2

What we see happening is a linking or piping of the results of a step down to the next step.

1 to 100 => evens => sum

Here are two ways to write this in Clojure:



The first way looks like a waterfall, but in order to understand it we need to go all the way to the bottom and work are way back up.  In this example we would start with the (range 101) then move up to the (filter even?) and lastly end at the (reduce +).  We find that reading this, we are going against the left to right flow of the code.

The second, Thrush(y) way, the first thing we see is our (range 101), next we find the (filter even?), and last we find the (reduce +).  This way seems very natural as the flow of data agrees with the reading from left to right.

I personally find the pipeline style used in the second way easier to read and use it as often as I can.  Martin Folwer has written an excellent article which goes into collection pipelines in more detail.  Debasish Ghosh has also written about the Thrush in Clojure (which help me a lot when I was trying to understand the -> and ->>macros).

Try Before You Buy OR REPLs in the Browser

"Now follow – if thou darest – to try whose right"-- Shakespeare, A Midsummer Night's Dream
Act III, Scene II, Line 336

"Can't someone else do it?"
-- Homer Simpsons, Trash of the Titans

One of the hardest things to do is setting up a new programming environment.  Things have improve a lot over the years, but it still be a very daunting task to set up a programming environment for a language you do not even know.  Often in the past I would ask myself, "can't someone else do it?"

Someone else has!  Try a REPL in your browser today!

Luckily many programming environments are waiting for you right now as REPLs in your browser.

A REPL is a Read Evaluate Print Loop, which works how it sounds:

Read input (in the form of code)
Evaluate input
Print result of input
Loop back to top

Today you can now play around with many different programming language from the comfort of your browser by using a REPL.

Here are two that I enjoy:

Clojure instaREPL
Try Haskell!

There is also repl.it which has an impressive collection of languages including: Ruby, Forth, JavaScript, Roy, and even Brainfuck, to name a few.

Clojure instaREPL and Try Haskell! are a bit more like an actual REPL running on your computer than repl.it, but repl.it does offer languages which are not normally associated with REPLs (other than Ruby).

One last thing, while TryAPL is not really a REPL, it is very awesome that you can write APL code with a simulated APL keyboard in your browser!

'Try APL today!'

Leap Year in the Key of C#, F#, Haskell, and Scala

"Shall be their father's bail, and bane to those"
-- Shakespeare, Henry VI Part 2
Act V, Scene I, Line 120

Leap Year

Leap year, one of the time based banes of a programmers' existence.

The rules around if a year is a leap year are simple enough.

if year is divisible by 400 then

   is_leap_year

else if year is divisible by 100 then

   not_leap_year

else if year is divisible by 4 then

   is_leap_year

else

   not_leap_year

Most languages do have a built in check for Leap Years, but the point of the kata is to implement your own in order to learn something.  With that in mind let's look at few ways to solve this problem and see what we can learn.

C#

Note, if we want to do it the most efficient way possible we could just use the built in DateTime.IsLeapYear, but the point of the kata is to implement the algorithm yourself in order to learn something.



Here is an example using C# with NUnit for the testing.

We see that we can just implement the algorithm as a series of conditional statements.  We also see that with NUnit we can use the TestCase attribute which allows us to just give the input along with the expected result.  This kind of testing I feel leads to more readable test cases which focus on the data and not the steps needed.  Having a test case which focuses on the data is the right approach in my opinion for testing a pure calculation based function like this.

Haskell

Note, this looks a lot like the code on Rosetta Code for the TDD Haskell implementation of Leap Year, because it is the same code that I contributed there for that entry.



This Haskell solution uses pattern matching.  If you are new to pattern matching you can think of it as a switch statement.

With this style of pattern matching in Haskell we would get an error message if we call the function without a value which was covered, but the otherwise keyword at the end covers everything else so getting an exception would not happen.  Comparing this to the C# solution with a series of conditional statements the Haskell caller knows that every input is covered by the function whilst the C# call will have to hope that all input cases are covered.

Scala

Note, this is my third Scala kata ever, as such I need to look at this gist form Kingsley Davies in order to do the kata.



With the Scala solution we are again using pattern matching, but this time we are doing all of the testing in a tuple which we are matching against (note, we could have done this in the Haskell and below in the F# solution).  Using this style of pattern matching we are matching against a pattern but in this case I feel that the algorithm is hidden, as such for this function I do not think this is an improvement over the Haskell solution above (note, I did this on purpose to try out this approach with this solution to see what it would look like).

F#

This last solution using F# uses Active Pattern Matching.  Personally I find the Active Pattern Matching with a Maybe Monad very readable.  We can see that the algorithm states if the year is divisible by 400 we have leap year, but if it is divisible by 100 we do not.

Note, you can do this pattern in Scala and Haskell.

Conclusion

We see above 4 somewhat different ways to find if a year is a Leap Year.  All these approaches used unit testing frameworks along with TDD.  None of the solutions are the way to do it, but each look at the problem from a different point-of-view.

Bird Watching with JavaScript -- The Kestrel

"I will entertain Bardolph; he shall draw, he shall tap."
-- Shakespeare, The Merry Wives of Windsor
Act I, Scene III, Line 10

The Forest

In the Combinator Forest we hear the repeating call of the Kestrel.  As we sing out DO RE, we hear the Kestrel sing back DO.  We sing out LA but the Kestrel is still singing back DO.  We try again by singing out DO RE MI FA SO LA TI DO, but the Kestrel sings back DO DO DO DO DO DO DO DO.

Kestrel

The kestrel or K combinator is written as Kxy.x.  Meaning that no matter what value is given as y we always get x back from K.

We see that we always get the first argument back from the combinator K.

Kestrel in Haskell

In the package Data.Aviary.Birds we see the kestrel has the following definition:

kestrel :: a -> b -> a

We find that it is implement in the following way:

-- | K combinator - kestrel - Haskell 'const'.
-- Corresponds to the encoding of @true@ in the lambda calculus.
kestrel :: a -> b -> a
kestrel = const

see also: http://hackage.haskell.org/package/data-aviary-0.2.3/docs/src/Data-Aviary-Birds.html#kestrel

We see that this is calling nothing more than the const function in Prelude, which is implement in the following way:

-- | Constant function.
const                   :: a -> b -> a
const x _               =  x

see also: http://hackage.haskell.org/package/base-4.3.0.0/docs/src/GHC-Base.html#const

This means no matter what we pass as a second argument to const the pattern matching will match it and will simply just return the first argument.  Let's play with this on tryhaskell.org:

λ const 42 "another value"

42

:: Num a => a

λ let only42 = const 42 in only42 [1..5]

42

:: Num a => a

λ let onlyChickens = const "Chicken" in 

map onlyChickens ["Hen", "Rooster", "Cow"]

["Chicken","Chicken","Chicken"]

:: [[Char]]

λ  

We see when we call const no matter what the second argument is only the first argument is returned.

Underscore.js' constant

The K combinator is one of the newly added function in the popular Underscore.js library.  It has been implement as constant.

Here is what the implementation looks like:

  _.constant = function(value) {
    return function () {
      return value;
    };
  };

We see that constant will return a function which always returns value no matter what we call that function with.

Let's do some characterization testing on Underscore's constant.

Is a function

it("Constat will return a function", function(){

expect(_.constant("Hello world")).to.be.a("function");

})

We see that result of calling constant is a function no matter what we call it with.

Always returns the first value given to it

it("Given two values constant will return the first", function(){

var alwaysFirst = _.constant("First");

expect(alwaysFirst("Second")).to.be.equal("First");

})

We also see that when we call the function which constant returns we always get the same value which we initially called constant with.

In fact we can call constant with another function and have that function always returned from the function which constant returns (it is functions all the way down!).

it("Given a function constant will return that function", function(){

var theTruth         = function(){return true;},

nothingButTheTruth = _.constant(theTruth);



expect(nothingButTheTruth()).to.be.a("function");

expect(nothingButTheTruth(false)()).to.be.ok();

expect(nothingButTheTruth(_.identity(42))()).to.be.equal(true);

});

Tap

Constant is a very simple implementation of the K combinator, but it has limit uses.  Tap is another way to implement the K combinator, but unlike constant it has a ton of uses.  In fact it is included in many languages core libraries including Ruby's.

Underscore.js' tap

"The primary purpose of this method is to "tap into" a method chain, in order to perform operations on intermediate results within the chain."
-- tap, Underscore.js documentation

Underscore has an implementation of tap which looks like this.

  _.tap = function(obj, interceptor) {
    interceptor(obj);
    return obj;
  };

Looking at the code above we see that if we call tap with a function we will pass the value through the function before we return the value.

Let's play around with the tap function to see what it is like to work with.

Can be used like constant

We see that give a value and a function which does nothing, the value is returned.

it("Give a string and a function which does nothing the string will be the same", function(){

expect(_.tap("Mr. Jack", function(){})).to.be.equal("Mr. Jack");

}),

and

var array = [1, 2, 3, 4, 5];

beforeEach(function(done){

array = [1, 2, 3, 4, 5];  // to reset before each test case

done();

});



it("Given an array and a function which does nothing array will be the same", function(){

expect(_.tap(array, function(){})).to.be.eql(array);

}),

Can have side effects

We see that we can attach a function to the value so that we have an effect take place when we access it.

it("Given a value and a function which increments ...", function(){

var counter = 0,

increment = function(){counter++;},

peek = function(){return _.tap("Look here", increment);};

expect(counter).to.be.equal(0);

expect(peek()).to.be.equal("Look here");

expect(counter).to.be.equal(1);

peek();

expect(counter).to.be.equal(2);

});

This is very interesting, in fact the most common use of tap is for logging which is very similar to what we have above.

Ciao

It may seem odd to work with a function which "only" returns the same value on each call but we find in fact that the Kestrel is a very useful function.

Currying in JavaScript

"If I had a suit to
Master Shallow, I would humour his men with the
imputation of being near their master; if to his men, I
would curry with Master Shallow that no man could
better command his servants."

-- Shakespeare, Henry IV Part 2

Act V, Scene I, Lines 64.ii - 68.i

What is Currying?

Using the HaskellWiki as a dictionary.

"Currying is the process of transforming a function that takes multiple arguments into a function that takes just a single argument and returns another function if any arguments are still needed."
-- HaskellWiki

In even more detail with historical context.

"Currying has its origins in the mathematical study of functions. It was observed by Frege in 1893 that it suffices to restrict attention to functions of a single argument. For example, for any two parameter function f(x,y), there is a one parameter function f' such that f'(x) is a function that can be applied to y to give (f'(x))(y) = f (x,y)."

-- Graham Hutton, Frequently Asked Questions for comp.lang.functional

In other words currying allows for you to think of your functions in such a way as that they only take one argument while in fact they have many arguments.

Example, say we have the following function f.

f(x, y) = y/x

We can curry f with the argument of 2 giving us a new function h.

h(y) = y/2

We can then call h with arguments obtaining the result of dividing those values by 2.

h(4) = 2

h(10) = 5

h(2) = 1

We could also define the function f in the following way.

f(h(y),x) = y/x

Now we get the following given the argument of 2.

h(y) = y/2

Thus getting same result as above.

In Haskell Everything is Curried

"Every function in Haskell officially only takes one parameter."
-- Miran Lipovača, Learn You a Haskell for Great Good
Chapter 6


When I first read the statement above my mind was blown.  Having read nothing about currying before I could not believe what I was reading.  Everything is curried?!?  If I define a function add which takes two arguments, then that function will be curried by default!?!

Using tryhaskell.org we can do the following.

λ (\x y -> x + y)

:: Num a => a -> a -> a

λ (\x y -> x + y) 2

:: Num a => a -> a

λ (\x y -> x + y) 2 3

5

:: Num a => a

In the first line we see the lambda function(\x y -> x + y)which takes x and y this is defined as a -> a -> a where a is a Number.  If we call the exact same lambda function with one argument we get a new function defined as a -> a.  Lastly if we take the same function and apply two arguments to it we get the value back.

This is currying in action.  All the functions are really just unary functions which will either return a anothing function or a value (which you could think about as a function that does not do anything other than returning the same value every time you call it).

In JavaScript Nothing is Free

How do we curry in JavaScript?  Well JavaScript does not curry by default like Haskell does, so we will have curry our functions ourselves.

Roll Our Own

In the gist above on lines 11-17 a curry add which takes three arguments.

var ownAdd = function(a){

  return function(b){

    return function(c){

      return a + b + c;

    }

  }

};

This function returns functions until it has all three arguments, once it has all three arguments it will return the sum of the arguments.  This will work but it really sucks!  Luckily currying is a well known pattern, so we have our pick of implementations of it in JavaScript like: underscore-contrib, allong.es, lemond, ...

Allong.es

Allong.es has a curry function which when applied to a function will return a curried version of the function.

var addThree = function(a, b, c){return a + b + c;},

  allongesAdd = curry(addThree);

We see another version of add in the gist on lines 19 and 20.  Yes, that is a lot less work.  Even better when we look at the example tests, we see the following on 46 and 47.

      expect(allongesAdd(1)(2)(3)).to.be.equal(6);

      expect(allongesAdd(1, 2, 3)).to.be.equal(6); // for free!

Yes, you get to call the function in a Haskell like curried maner and allong.es does all the hard work for you.

Mapping Fun

I know this is all well and fine, but how does one use this in a typical real world manner?  Glad you asked.  I spend a lot of time in my day job working on collections of data, one way I've used currying is with higher order functions.

Say you have an array which represent the combination to your luggage (not 100% real world, but much funnier than see same thing similar with securities, orders, executions, commissions, ...).

    var luggageCombination = [1, 2, 3, 4, 5],

        luggageMappings = map(luggageCombination);

This works until someone accuses you having an idiots combination for your luggage, so you figured your keep your current combination but will apply a mapping function against it to have a less idiotic combination.  In allong.es every function is curried, so you can apply map against your combination and try out different functions to see which give the best result.

Using this we can square and mod 10 the values to give us the combination of 1, 4, 9, 6, 5.  Now who is the idiot!

      var squared = function(x){return x * x;},

          squaredMod10 = compose(function(x){return x % 10;}, squared); // Who's an idiot now?!?

      expect(luggageMappings(squaredMod10)).to.be.eql([1, 4, 9, 6, 5]);

This example is really good, since we are composing our squaredMod10 function!

Bird Watching with JavaScript -- The Bluebird

"The first sparrow of spring! The year beginning with younger hope than ever! The faint silvery warblings heard over the partially bare and moist fields from the bluebird, the song sparrow, and the red-wing, as if the last flakes of winter tinkled as they fell! What at such a time are histories, chronologies, traditions, and all written revelations? The brooks sing carols and glees to the spring."
-- Henry David Thoreau
Walden, page 160

The Open Woodlands

Music all around.  A slight breeze is gently rustling the grass and leaves.  The song of the bluebird fills the air.  You call out X.  It sings back X.  You call out Y.  It sings back Y and X.  You call out Z.  It sings back Z, Y, and X.

The Bluebird

One of the first higher order functions that people learn is the composite function.

In combinatory logic the composite function is known as the B combinator.

B f g x = f (g x)

It also goes by the name given to it in To Mock a Mocking Bird, the bluebird.

Compose in Haskell

One of the things I love about Haskell is that if you look at a method signature you can pretty much tell what the function does.

Here is the definition of the compose function taken from the Haskell source.

(.)    :: (b -> c) -> (a -> b) -> a -> c
(.) f g = \x -> f (g x)

Looking at the definition we see that we need two functions, one goes from b to c and the other goes from a to b.  When given the value a the output is value c.

Looking at the actual function we see we have f (g x).  Meaning take the 2nd function I gave you (a -> b) and apply that to the argument a that I gave you.  Now take the result of (a -> b) and apply the 1st function I gave you (b -> c) against that.  The result of applying the (b -> c) function is the result I want returned.

Compose in Underscore

We see that compose is built into Haskell but what about JavaScript?  Reading Reginald Braithwaite's excellent book JavaScript Allongé we see a definition of compose but we do find anything built into JavaScript (reading this book is what prompted me to write this post).  Luckily Underscore.js has us covered!

_.compose(*functions) 

Looking at the functional definition we see that we can pass in any number of functions and have compose create a function which applies all of them to the argument given to it.

  _.compose = function() {
    var funcs = arguments;
    return function() {
      var args = arguments;
      for (var i = funcs.length - 1; i >= 0; i--) {
        args = [funcs[i].apply(this, args)];
      }
      return args[0];
    };
  };

In fact looking at the annotation source we see that it applies all of the function we give it to how ever many arguments we give it!

Characterization Test of Underscore's compose

    it("Given a bunch of identity functions it will return the value given", function(){

      var ids = _.compose(_.identity, _.identity, _.identity, _.identity);

      expect(ids("Mike Harris")).to.be.equal("Mike Harris");

    })

We verify that we can apply compose however many times we wish to the identity function, which is also known as the I combinatory or the idiot bird, and we will get the same value back, f(x) = x.

    it("Given an increment function it will return one more", function(){

      var plus1 = _.compose(increment);

      expect(plus1(42)).to.be.equal(43);

    })

We see we can also pass in only one function and have that function applied to the argument we give it.

    it("Given a absolute value and square root functions but used in the wrong order " +

       "we cannot find positive square roots", function(){

        var wrongPosSqrt = _.compose(Math.abs, Math.sqrt);

        expect(_.isNaN(wrongPosSqrt(-4))).to.be.ok();



        // even better

        var failedPosSqrt = _.compose(_.isNaN, wrongPosSqrt);

        expect(failedPosSqrt(-4)).to.be.ok();



        // or

        var showWhenFailed = _.compose(function(x){return !x;}, failedPosSqrt);

        expect(showWhenFailed(2)).to.be.ok();

        expect(showWhenFailed(-2)).to.not.be.ok();

    })

We also verify that the order does matter.  When we use compose we need to think of it as applying the functions given in the order that we would read it if we wrote it out.

function wrongPosSqrt (x) = {return Math.abs(Math.sqrt(x));};

is very different from

function posSqrt (x) = {return Math.sqrt(Math.abs(x));};

The End

The bluebird can be thought of as a gateway to the larger world of functional programming.  With the simple concept of applying function together we see that we can built up simple existing functions to larger more complex functions.  This is one of the core concepts of functional programming.