Tower of Hanoi in Haskell

Before moving into Types in Haskell which is one big chapter in this book I am following I thought of having some more familiarization with the language.

How about solving Tower of Hanoi problem through haskell?

hanoi (0, _, _, _) = []
hanoi (n,from,to,using) =
         hanoi(n-1,from,using,to) ++
         [(from, to)] ++
         hanoi(n-1,using,to,from)

Running the program for n = 3 (3 discs) and 1, 2, 3 as the labels for from, using and to towers –

*Main> dohanoi (3,1,3,2)
[(1,3),(1,2),(3,2),(1,3),(2,1),(2,3),(1,3)]

If you just want the number of moves in the problem, take length of the list

length $ dohanoi (3,1,3,2)

This is equal to 2 ^ n – 1.

Advertisements

Quick Sort – Poster boy for Haskell’s Elegance

Finally I reached to write Quick Sort code in Haskell. This code generally requires ~ 10-12 LOC in imperative languages (I implemented last in C & Perl). In Haskell (and not surprisingly) it is much lesser length and much intuitive than the pivot – if – else code. That beauty is functional programming language’s – You don’t tell “how to do” but “what to do”.

Quick Sort Algorithm is basically:

A sorted list is a list that has all values smaller than the head of the list (sorted values), then comes the head and then come all the values larger than the list (sorted values).

First take care of the edge case i.e. Empty list.

Then handle the list. Use Set comprehensions and get the list of elements < the head and >= the head and then concatenate. We have two smaller list on which the function can be applied recursively. Recursion is such a beauty.

quickSort’ :: (Ord a) => [a] -> [a]
quickSort’ [] = []
quickSort’ (x:xs) = quickSort’ [ y | y <- xs, y < x]
                        ++ [x]
                        ++ quickSort’ [y | y <- xs, y >= x]

Set comprehensions in Haskell

Remember “Set comprehensions” in Mathematics?

Being of mathematical nature Haskell provides the same kind of programming touch feel. It has a notion of list comprehensions i.e. you define a set of answers in a set notation form. For example to convey that you need a list of all integers greater than or equal to 1 and less than or equal to 100 you can write: 

[ x | x <- [1..100] ]

Here we used Range in Haskell to represent the list [1,2,3,4,..100].

A simple problem: get all right triangles whose perimeter is 24 and each of whose sides is less than 10

There is a concept of Tuples in Haskell which is very close to structures in C/C++. We can use a tuple that contains three sides and then apply the transformations (restrictions given above). First is that each side is less 10, second that it should be a right triangle and third that perimeter should be 24,

[ (x,y,z) | x <- [1..10], y <- [1..10], z <- [1..10], x^2 + y^2 == z^2, x+y+z == 24 ]

This one liner looks so cute.

Starting with Haskell

Few days back I started learning Haskell, a purely functional programming language. A functional programming language has a different paradigm altogether from the so called imperative languages (C, C++, Java, Python, Ruby, Perl etc.). Haskell is not a new language and was originated in 1987 undergoing huge changes during the course of time.

As the book “Learn You a Haskell for Great Good” mentions:

In purely functional programming you don’t tell the computer what to do as such but rather you tell it what stuff is. The factorial of a number is the product of all the numbers from 1 to that number, the sum of a list of numbers is the first number plus the sum of all the other numbers, and so on.

Haskell is –

  • Purely functional programming language
  • Lazy
  • Statically Typed
  • Elegant & Concise

I will keep writing further on Haskell and my programming experiences with it.