Sex, drugs and sausage rolls

Tech and Life… as seen by Tallmaris (il Gran Maestro)

Learning Haskell my way

I have recently decided to start this journey in learning functional programming and I have decided to use Haskell, for no particular reason to be honest, but it seemed to be a highly respected language.

I have started with a few tutorials and probably the best introduction is the free online resource from “Learn You a Haskell”: http://learnyouahaskell.com/

I followed the tutorial mainly trying to come up with the solution before reading it. All the examples are very small and it is easy to try and anticipate what is happening and also get into the mindset of recursions, list comprehension and all that surrounds FP.

I often stopped and tried to re-implement some inbuilt functions with some more basic code. I highly recommend that approach as it will make your head think hard about the problem and make you realise that some of the more advanced functions are indeed extremely simple implementations in the end.

I also tried to solve some other problems and today I want to share with you my home made functional solution to the Pascal Triangle problem.

The Pascal Triangle

Pascal's Triangle

Pascal’s Triangle

I won’t bother with the details¬†(which you can read on Wikipedia),¬†and the image to the right will clarify what this is.

My function will take a number N and return the Nth row of the triangle.

My reasoning is as follow:

  1. The first row is just 1
  2. The second row is just [1,1]
  3. The third row is simply [1, sum_of_first_row, 1]

That stopped me in my tracks as I immediately noticed the recursive pattern, which is good!

So I thought, basically every row is composed as follows:

  1. The number 1
  2. The previous row, summed up two elements at a time
  3. The number 1 again

This is great, now I simply need a function that can transform a list of numbers in a list of the same numbers taken two at a time (overlapping); I called it tuplise. This is quite easy in Haskell:

tuplise :: [a] -> [(a,a)]
tuplise [x,y] = [(x,y)]
tuplise (x:y:rest) = (x,y) : (tuplise $ y:rest) 

We should probably add some errors if called with an empty list or a singleton, but this is not interesting now.

Then I have created a simple helper function that will get a tuple and return the sum of the two numbers in it. Maybe this already exists in Haskell but I don’t care since the implementation is really trivial;

tsum :: (Num a) => (a,a) -> a
tsum (x,y) = x + y

If you have GHCi open you can actually rest the output from these two functions quite easily:

*Main> :l main
[1 of 1] Compiling Main             ( main.hs, interpreted )
Ok, one module loaded.
*Main> tuplise [1,2,3,4]
[(1,2),(2,3),(3,4)]
*Main> tsum (3,4)
7
*Main> map tsum $ tuplise [1,2,3]
[3,5]
*Main> 

The last bit is basically a tip on how the full function will work: we use map to run tsum on all the tuples that tuplise has created. With that in mind, the pascal function is as simple as:

pascal :: Int -> [Int]
pascal 1 = [1]
pascal 2 = [1,1]
pascal x = 1 : (map tsum $ tuplise $ pascal (x-1)) ++ [1]

Let’s again have a look at the output in GHCi and then show the full triangle for the first 5 rows; for that, as you can guess, I am not even writing a function but simply running my existing function on the 1 to 5 range, using map:

*Main> pascal 10
[1,9,36,84,126,126,84,36,9,1]
*Main> map pascal [1..5]
[[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]
*Main> 

Beautiful! And if that does not make you fall in love with functional programming I don’t know what will!

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>