Dip your toes in some Haskell, the water is warm here!

So, Haskell sounds quite daunting right? All this talk of monads and functors when all you want to do is just try out some simple problems and see what it’s like to play around with this language! Monads and functors are actually not that scary once you get into functional programming but, for today, I won’t mention them again. So, let’s dip our toes in and see what it’s like.

I often hear newcomers to functional programming sighing to themselves about how difficult it is to retrain their brains to read and write code in this paradigm that is new to them. Don’t get me wrong, the sighing is understandable especially when we have spent years wrapped in our imperative, object oriented comfort blankets with for loops and mutable variables. The sighing is usually witnessed when watching an experienced OO programmer getting to grips with a new codebase written in a functional language and seeing something like this:

isPalindrome (x1 : xs)  = x1 == last xs && isPalindrome (init xs)

Yep, there is a bit in there especially when you may be more used to the imperative way of writing such an algorithm.

public class Palindrome {

    public static boolean isPalindrome(String str) {

        int strEndIndex = str.length() - 1;

        for(int i = strEndIndex; i > (strEndIndex/2); i--)
           if(str.charAt(i) != str.charAt(strEndIndex - i))
               return false;

       return true;

Ah, that’s better. Our old reliable Java for loop with our mutable counter. Let me take you on a small journey to give you a taster for Haskell. We’ll go from Haskell code that actually looks quite similar to that imperative Java code and gradually work towards that previous Haskell code snippet. We’ll use the good old palindrome kata to take us on that journey. The palindrome kata is a task to write a function which checks if a String is the same going from left to right as it is going right to left. Yes, I know, most languages have a library function, reverse, meaning we can simply reverse the String and compare with the original. But lets suspend our disbelief for a while so I can take you on a journey!

Quick setup to follow along

To start dipping your toes in, why not follow along with the Haskell examples in the rest of this post. Haskell quick installers for most types of OS can be found here:

After that, all you need is a text editor and your terminal.

Make a new file called DipYourToesIn.hs and add the declaration for the Haskell module where we will put our functions:

module DipYourToesIn where

Now crank up your favourite command line terminal and go to the directory where you created that file.

Now, simply type: ghci and this will start up the Haskell compiler in interactive mode allowing you to enter and evaluate Haskell expressions. We will use it to simply load and compile our DipYourToesIn.hs Haskell source so that we can call our Haskell functions as we create them to see it them working.

ghci> :l DipYourToesIn.hs 
[1 of 1] Compiling DipYourToesIn ( DipYourToesIn.hs, interpreted ) Ok, modules loaded: DipYourToesIn. 
ghci> isPalindromeWithRecursion "hello" 
ghci> isPalindromeWithRecursion "racecar" 

The Haskell source can be loaded and compiled using :l DipYourToesIn.hs

Once it is compiled, we can now execute functions within that file by simply calling them.

In the next section, we will be creating the function, isPalindromeWithRecursion, but the above just shows how quick it is to start interacting with Haskell code as you write it. In saying that though, this shouldn’t be a substitution for tests. I would still write tests first, and use this interactive approach to experiment with the code that I am writing to make the tests pass.

Imperative Looking Haskell — looks can be deceiving!

So, lets’ start off with some Haskell that models the above Java solution quite closely.

isPalindromeWithRecursion :: String -> Bool
isPalindromeWithRecursion str =
 loop strEndIndex where

 strEndIndex = length str - 1
 loop i =
   if (i <= (div strEndIndex 2)) then True
   else if (str !! i) /= str !! (strEndIndex - i) then False
   else loop (i - 1)

A note about function type signatures

Line 3 in the above example contains the type signature for our function right after the :: after the function name. This specifies that the function takes a String parameter and returns a Bool (a boolean). Parameters and return types are separated by the -> symbol. If there are multiple parameters, they are all separated by -> with the last type being the return type. This is because every function in Haskell is actually a one parameter function. So, when we see a multiple parameter type signature, under the hood we have a series of outer to inner functions — a concept called currying. It is not important to know all about that just yet though if you are just dipping your toes in.

In Haskell there are no mutable variables or for loops but that doesn’t stop us from writing code that looks almost like the imperative Java solution. We define an inner loop function which is called recursively acting like our for loop.

  • On line 5, the where syntax there is a way to give bindings to local values or functions — essentially creating local immutable variables.
  • On line 8, we define the loop function which takes an immutable counter, i, meaning that the counter is “updated” by passing a new version of the counter value into the loop function every time it is called.
  • On line 5, the loop function is called with an initial counter, i, argument being the last index of the String — just like we initialised i in the Java solution.
  • The algorithm remains the same. We check the first and last characters. If they are equal, we continue checking the next 2 inner characters and so on. If we find two that are not equal, we can return False straight away and if we get down to only one or no characters remaining, we know we have a palindrome and return True.
  • This divides the end index of the String by 2 so that we can tell we have gotten to a point of 1 or 0 characters left.
(div strEndIndex 2)

This gets the i’th element of a list, in this case, the i’th character in the String str.

(str !! i)

This is how we compare a character going right to left with its corresponding character going left to right. /= meaning not equal to

(str !! i) /= str !! (strEndIndex — i)

As shown previously, we can load this into our GHCI and look at it in action.

ghci> :l DipYourToesIn.hs [1 of 1] 
Compiling DipYourToesIn ( DipYourToesIn.hs, interpreted ) 
Ok, modules loaded: DipYourToesIn. 
ghci> isPalindromeWithRecursion "hello" 
ghci> isPalindromeWithRecursion "racecar" 

Guard those if then elses!

isPalindromeWithRecursionAndGuard :: String -> Bool
isPalindromeWithRecursionAndGuard str =
 loop strEndIndex where

   strEndIndex = length str - 1
   loop i
     | i <= (div strEndIndex 2) = True
     | (str !! i) /= str !! (strEndIndex - i) = False
     | otherwise = loop (i - 1)

Nothing has changed in our underlying algorithm. Also, not much has changed in the code but it is easier to read right? We still have the same set of conditions and corresponding expressions, one of which will be evaluated.

| i <= (div strEndIndex 2)
| (str !! i) /= str !! (strEndIndex - i)


| otherwise =

otherwise is the default case and its corresponding expression will be evaluated if none of the other boolean expressions have evaluated to True.

A bit about Haskell lists

A List in Haskell is a recursive data structure. A List can be empty and is simply represented as


A List can also be non empty and, in this case, it is represented as a cell containing a value and a link to another List which itself can be empty or contain another cell with a value and a link to a further List. This recursive structure continues until we get an empty list.

The cons function in Haskell, represented with a


is used to create one of these list cells by joining a value together with an existing List which may or may not be empty. Using this function, we can create the List in the above diagram as follows:

1 : 2 : 3 : []

Haskell has a nicer way though with syntactic sugar allowing us to do the same thing with this bit of code:

[1, 2, 3]

A couple of List operations to help the palindrome cause

Haskell like other functional programming languages has very nice high level operations that we can use on lists. Lets try a couple with GHCI.

First lets create a List and bind it to a name, l. This is done in GHCI using the let keyword but, in Haskell source code, the let isn’t required.

ghci> let l = [1,2,3,4,5] 
ghci> l 

We’re going to need to be able to get the last element in the list so we can compare it to the first element. This is no problem though, we can simply use a function called last.

ghci> last l 

We will also need to get the first element in a list. We will be doing this later by refining the code with pattern matching. However, just for completeness, we do this by using a function called head.

ghci> head l 

Be careful though, calling head on an empty list will give an exception.

ghci> head [] *** 
Exception: Prelude.head: empty list 

For reasons that will become apparent soon, we will also need to use a handy function called init. This creates a new list from everything in an existing list except the last value.

ghci> init l 

Polishing it off with pattern matching

Pattern matching is a concept very prevalent in functional programming. It allows you specify patterns to match against a data structure, its value type and by the structure and values of its elements. This allows the data structure to be deconstructed and parts of it extracted.

Function arguments are one place where pattern matching can be used very effectively. This is done in Haskell by redefining the function multiple times to deal with the different possible argument value patterns that can be passed in when the function is called.

isPalindrome :: String -> Bool
isPalindrome [] = True
isPalindrome (x : []) = True
isPalindrome (x1 : x2 : []) = x1 == x2
isPalindrome (x1 : xs)  = x1 == last xs && isPalindrome (init xs)
  • The final example above uses a mixture of pattern matching and the functions we saw earlier that we can use on lists. A String is a list of characters so we can pattern match on a list argument to the isPalindrome function.
  • Line 54 matches on the empty list. So, if an empty list is passed as an argument to the isPalindrome function, we return True straight away.
  • Line 55 pattern matches on a list with one element. We use the cons function, : , to match on a list structure which contains one cons cell with a value and a link to an empty list. The value of the cons cell can be anything and is bound to the value, x, in the pattern. So, with this pattern, we are checking if the list has only one element and, if it does, we can again return True.
  • Line 56 is pattern matching to check if the list argument has only 2 values. We again use the cons function to match against the list structure that we are looking for. We can also bind the first 2 values of the list to the names, x1 and x2. This allows us to check these for equality to determine if the 2 element list is a palindrome.
  • Finally, on line 57, we are back to that piece of code that is likely to make an experienced imperative programmer sigh when trying to get to grips with a functional programming codebase. When pattern matching, the first function expression with a matching pattern for the argument being passed in is the function expression that gets executed. So, if we have gotten this far, there has been no other pattern match so we know that our list argument has more then 2 values. So, now we simply use one cons function to match on a list that has a first element, x1, and a link to the rest of the list, xs. Now we can use our trusty last function to compare x1 to the last element of the list. If they are not equal, we return false as we don’t have a palindrome.
  • However, it they are equal, we need to evaluate the right hand side of the boolean &&. In this case, we literally create a new list made up of all elements of the list minus the first and last element. By calling init on xs, we are omitting the first element, x1, and getting all elements except the last. Then we recursively call isPalindrome on this newly created list so that we can continue checking further and further into the original list until we get to 2 values that are not equal or an empty or 1 element list (after all other outer elements have been “chopped off” so to speak).


I hope all this might encourage more developers to delve into the beautiful language of Haskell. I started dipping my toes in a while back and, pretty quickly, I took the plunge and absolutely love coding in Haskell. I feel at my most relaxed as a developer when I am writing Haskell code. Building up small composable Haskell functions with a type system that protects you but never gets in your way really does lead to a joyful coding experience for me. I will follow up this post with some more dipping of the toes in Haskell to show how we can use the type system to make our isPalindrome function handle lists of any type…well almost any type.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s