Category Archives: Haskell

Setting Up A Haskell Development Environment (Mac OS)

Since I started developing in Haskell, I have experimented with a few different setups. I started with Vim with no plugins and that, together with GHC in the terminal was my vanilla setup as I spent my first couple of months learning the basics of Haskell. I like to start off this way when learning a new language as it really forces me to commit the basics of the language and its syntax to memory.

As I learned more about the language and moved on to more advanced topics and more complex problems, I needed to take advantage of Haskell tooling to increase my productivity. Sometimes I find the tooling for Haskell can get a bad rep but I actually find it very good. Tools like ghc-mod,  hlint and stylish-haskell provide a lot of key features that you may be used to from working with IDEs – code completion, documentation, compile error and warnings and even suggestions to make your Haskell code more idiomatic. The tricky thing can be getting these tools integrated into your favourite editor or IDE.

I started with VIM plugins to integrate these tools with VIM and also played around with the Haskforce plugin for Intellij which is an excellent plugin. I finally settled on the Atom editor which makes integrating Haskell tools very simple and it also has a load of really great plugins to enhance your Haskell development experience.

In this post, I’m going to go through step by step how to set up a Haskell development environment using Stack (a Haskell build tool), ghc, ghc-mod and other wonderful Haskell tools, and integrating all this with the Atom editor.

To make this a bit more realistic and to make sure that I don’t miss anything, I’m stripping my laptop of any Haskell, Stack, ghc and other installations related to Haskell tooling. I will leave Atom installed but I’ll remove all my Haskell plugins and start from scratch. As I set up my environment from scratch, I will document everything with command line commands and screenshots. I am using a Mac with macOS Sierra.

Okay here goes…
Firstly, I use Homebrew for installing Stack.

Setting up Stack, Ghc and other Haskell tools

➜  ~ brew install haskell-stack
➜  ~ stack setup

This may take about 10 minutes and you will see something like the following output.

Using latest snapshot resolver: lts-7.13
Writing implicit global project config file to: /Users/tom/.stack/global-project/stack.yaml
Note: You can change the snapshot via the resolver field there.
Downloaded lts-7.13 build plan.
Fetched package index.
Populated index cache.
Preparing to install GHC to an isolated location.
This will not interfere with any system-level installation.
Downloaded ghc-8.0.1.
Installed GHC.
stack will use a sandboxed GHC it installed
For more information on paths, see 'stack path' and 'stack exec env'
To use this GHC and packages outside of a project, consider using:
stack ghc, stack ghci, stack runghc, or stack exec

We can now start up the Haskell compiler, ghc, in interactive mode, ghci
In other words lets crank up a Haskel REPL and try a Haskell expression:

➜  ~ stack ghci
Configuring GHCi with the following packages:
GHCi, version 8.0.1: http://www.haskell.org/ghc/  :? for help
Loaded GHCi configuration from /Users/tom/.ghci
Loaded GHCi configuration from /private/var/folders/tj/mtvt3dv57cq6kbzw8809_gs00000gn/T/ghci78459/ghci-script
ghci>  1 + 1
2

We can quit back out of ghci now

ghci>  :q

We can now use stack to set up the tools that will be the engine behind a lot of our Haskell development experience.

➜  ~ stack install ghc-mod hlint stylish-haskell

You will see something like

[1 of 2] Compiling Main             ( /Users/tom/.stack/setup-exe-src/setup-mPHDZzAJ.hs, /Users/tom/.stack/setup-exe-src/setup-mPHDZzAJ.o )
[2 of 2] Compiling StackSetupShim   ( /Users/tom/.stack/setup-exe-src/setup-shim-mPHDZzAJ.hs, /Users/tom/.stack/setup-exe-src/setup-shim-mPHDZzAJ.o )
Linking /Users/tom/.stack/setup-exe-cache/x86_64-osx/tmp-Cabal-simple_mPHDZzAJ_1.24.0.0_ghc-8.0.1 ...
ghc-paths-0.1.0.9: download

It will continue on and download all the packages it needs. This can take a while.

comonad-5: download
comonad-5: configure
polyparse-1.12: copy/register
cpphs-1.20.2: download
comonad-5: build
...
Progress: 54/71
...

You should eventually see something like

Copying from /Users/tom/.stack/snapshots/x86_64-osx/lts-7.13/8.0.1/bin/hlint to /Users/tom/.local/bin/hlint
Copying from /Users/tom/.stack/snapshots/x86_64-osx/lts-7.13/8.0.1/bin/stylish-haskell to /Users/tom/.local/bin/stylish-haskell

Copied executables to /Users/tom/.local/bin:
- ghc-mod
- ghc-modi
- hlint
- stylish-haskell

Stack has now added executables in /Users/tom/.local/bin (/Users/tom being my home directory or ~)

You can add this to your PATH environment variable. I do this by editing ~/.zshrc as I use Zsh for my shell. If you are using bash, you can edit .bashrc

In the line for export PATH=
add this to the start of your path
“/Users/tom/.local/bin:
except the /Users/tom part needs to be replaced with the path to your home directory.

Setting up Atom

Download and install the Atom editor. It can be downloaded from here

So lets crank up this beautiful and highly configurable editor!

To start adding our Haskell Atom packages, click “Install a Package” and then “Open Installer”

Search for haskell

Click “Install” on the following
language-haskell
haskell-ghc-mod
ide-haskell
autocomplete-haskell

These should be all you need to get going but there are also other great packages that are worth exploring.
For example, haskell-hoogle lets you get documentation from Haskell Hoogle through a context menu.

There shouldn’t be any other configuration needed.
Lets set up a Haskell Stack Hello World project and edit it in Atom.

Close Atom for now.

back in the terminal, we can create a Stack project called hello.

➜  ~ stack new hello

This will show something like this

Downloading template "new-template" to create project "hello" in hello/ ...

The following parameters were needed by the template but not provided: author-email, author-name, category, copyright, github-username
You can provide them in /Users/tom/.stack/config.yaml, like this:
templates:
  params:
    author-email: value
    author-name: value
    category: value
    copyright: value
    github-username: value
Or you can pass each one as parameters like this:
stack new hello new-template -p "author-email:value" -p "author-name:value" -p "category:value" -p "copyright:value" -p "github-username:value"

Looking for .cabal or package.yaml files to use to init the project.
Using cabal packages:
- hello/hello.cabal

Selecting the best among 9 snapshots...

* Matches lts-7.13

Selected resolver: lts-7.13
Initialising configuration using resolver: lts-7.13
Total number of user packages considered: 1
Writing configuration to file: hello/stack.yaml
All done.

You’ll see there that it prints out info about .cabal. Cabal is a Haskell build tool that Stack is built on top of.

So lets open this up in Atom and see what it looks like. My main pain point with Haskell and Atom was getting Atom to play nicely with ghc-mod through Stack. The following way of opening a Stack project in Atom is officially deprecated but I still find it the simplest way to open a Stack project in Atom and have it work with no hassle.

Go into the hello directory.

➜  ~ ls -l hello

Open Atom through Stack

➜  hello stack exec atom

Click on “Open a Project” and the the “Open a Project” button

Select your hello directory and click open.

To open the main.hs file that stack has generated for us:
cmd-p
and type in “main”

Select main.hs
You will see a haskell-ghc-mod warning appear.

This seems to be a side effect of using stack exec to open the Stack project in atom. This warning popup can be closed and ignored. I have found no bad effects of ignoring this warning anyway.

We can now see the main.hs open with our nice Haskell syntax highlighting.
I have gone ahead and typed “i” under the module declaration for and you can see the code complete for importing a module.

If I type “im” and tab, it inserts a template for module import. There a lot of these handy templates including data declarations do syntax, if then else etc

If I start typing out an import for Data.List, you can see auto complete of ghc-mod giving me my options.

I can also go ahead and start typing “put” into main and I get auto complete options again.

If I make a mistake and save, ghc-mod gives me my compile error in the bottom pane and also when I hover over the place where the error occurs.

So lets fix that and print “Hello World”

Now we can go back to our terminal and build this.

➜  hello stack build
Warning: File listed in hello.cabal file does not exist: README.md
hello-0.1.0.0: build (lib + exe)
Preprocessing library hello-0.1.0.0...
[1 of 1] Compiling Lib              ( src/Lib.hs, .stack-work/dist/x86_64-osx/Cabal-1.24.0.0/build/Lib.o )
Preprocessing executable 'hello-exe' for hello-0.1.0.0...
[1 of 1] Compiling Main             ( app/Main.hs, .stack-work/dist/x86_64-osx/Cabal-1.24.0.0/build/hello-exe/hello-exe-tmp/Main.o )
Linking .stack-work/dist/x86_64-osx/Cabal-1.24.0.0/build/hello-exe/hello-exe ...
Warning: File listed in hello.cabal file does not exist: README.md
hello-0.1.0.0: copy/register
Installing library in
/Users/tom/hello/.stack-work/install/x86_64-osx/lts-7.13/8.0.1/lib/x86_64-osx-ghc-8.0.1/hello-0.1.0.0-2MDzoFPW8yDJLgrpJYcMkC
Installing executable(s) in
/Users/tom/hello/.stack-work/install/x86_64-osx/lts-7.13/8.0.1/bin
Registering hello-0.1.0.0...

Stack creates an executable for us called hello-exe. This name is configured in hello.cabal in our hello directory.

We can run this executable now.

➜  hello stack exec hello-exe
hello world

Finally, that ghc-mod warning that was coming up in Atom:
cmd-, will bring up the settings pane.
Go into packages, haskell-ghc-mod and Settings and scroll down and check “Suppress GHC Package Path Warning”. However, due to the warning there, it might be better not to do this and to just close out of the ghc-mod warning popup with you open up a project.

Hopefully this guide has been useful. Enjoy playing with Atom and its packages for Haskell!

Additional Note

For existing projects, if they were built with stack that had a different lts-resolver, you can get problems with atom.Easiest thing there is to delete the .stack-work directory in the root directory of your project. In terminal run this command from the project root directory:

stack init --solver --force

this creates a new stack.yaml file with the lts-resolver for your installed stack. Removing .stack-work may cause a lengthy rebuild if the existing project has a lot of dependencies.
My projects have small numbers of dependencies at the moment so it hasn’t been a problem for me.
Then rebuild your project with

stack build

and open atom with

stack exec atom

from your project’s root directory as before.

Haskell div mod – Cyclical Division, Modulus Visualised

Reading Time: 8 mins
When I first came to integer division and the modulus operation in Haskell, I was thrown a bit of a curve ball, but a good curve ball at that. While Haskell does have two forms of integer division, one of those is a lot different from how I was used to thinking about integer division in other languages like Java and Scala. This actually comes in very handy for algorithms that cycle through ranges of values either left to right or right to left. However, as I was more used to the way it is done in Java and Scala, it took a bit of a mind-shift when I came to Haskell and saw another way to handle integer division and modulus.

One way of doing integer division in Haskell is with the quot and rem functions. They can be put together with the function quotRem and giving a tuple of the result and the remainder and this works like many would be used to from Java or some other languages.

ghci> let x = 8 :: Integer
ghci> let y = 3 :: Integer
ghci> quotRem x y
(2,2)
ghci>
ghci> let x = (-8) :: Integer
ghci> let y = 3 :: Integer
ghci> quotRem x y
(-2,-2)
ghci> let x = (-8) :: Integer
ghci> let y = (-3) :: Integer
ghci> quotRem x y
(2,-2)

ghci> let y = -3 :: Integer
ghci> quotRem x y
(-2,2)
ghci>

I’ve put together  a visualisation and a set of rules that I use to reason about another way that Haskell provides for integer division and along with its modulus operation. First, lets take 8 div 3 and show the results of the different combinations of positive and negative numerators and denominators.
Haskell has a handy function called divMod which returns a tuple with the first element being the integer division result and the second being the remainder (the result of the mod operation).

8 div 3

ghci> let x = 8 :: Integer
ghci> let y = 3 :: Integer
ghci> divMod x y
(2,2)
ghci>

-8 div 3

ghci> let x = (-8) :: Integer
ghci> let y = 3 :: Integer
ghci> divMod x y
(-3,1)
ghci>

-8 div -3

ghci> let x = (-8) :: Integer 
ghci> let y = (-3) :: Integer
ghci> divMod x y 
(2,-2)
ghci>  

8 div -3

ghci> let x = 8 :: Integer
ghci> let y = (-3) :: Integer
ghci> divMod x y
(-3,-1)
ghci>

These can be surprising results especially when compared to, say, Scala. For example, if we take -8 mod 3 in Scala, we get -2 unlike the 1 modulus result we got in our Haskell result (-3,1)

scala> -8 % 3
res2: Int = -2

Visualising Cyclical Integer Division And Modulus

The visualisation works as follows:

  • We have a denominator block in blue which has a length equal to the denominator.
  •  We have a denominator range that we are trying to move the block into which ranges from the denominator , inclusive, to the 0 boundary, exclusive.
  •  We move the denominator block until it partially or completely enters the denominator range.
  •  We have a Divisions accumulator which gets incremented or decremented.
  • If our block moves so that it approaches the denominator range without passing through the 0 boundary, we increment our Divisions accumulator with each move.
  •  Otherwise, the denominator block passes over the 0 boundary and we decrement our Divisions accumulator with each move.
  •  The final Divisions accumulator is the division result and the difference between the top of the denominator block and the 0 boundary gives the remainder.

8 div 2

0 Boundary

1
2
3
4
5
6
7
8

Divisions 0

0 Boundary

1
2
3
4
5
6
7
8

Divisions 1

0 Boundary

1
2
3
4
5
6
7
8

Divisions 2

0 Boundary

1
2
3
4
5
6
7
8

Divisions 3

0 Boundary

1
2
3
4
5
6
7
8

Divisions 4

Our last move brings the denominator block fully into the denominator range so we have no remainder.
So, 8 div 2 is 4 remainder 0.

8 div 3

0 Boundary

1
2
3
4
5
6
7
8

Divisions 0

0 Boundary

1
2
3
4
5
6
7
8

Divisions 1

0 Boundary

1
2
3
4
5
6
7
8

Divisions 2

Our last move brings the denominator partially into the denominator range. Our Divisions accumulator is 3 and the difference between the top of the denominator block and the 0 boundary is 2.
So, 8 div 3 is 2 remainder 2.

Changing division direction -8 div 3

Our Divisions accumulator gets decremented this time because we will be crossing the 0 boundary.

-8
-7
-6
-5
-4
-3
-2
-1

0 Boundary

1
2
3

Divisions 0

-8
-7
-6
-5
-4
-3
-2
-1

0 Boundary

1
2
3

Divisions -1

-8
-7
-6
-5
-4
-3
-2
-1

0 Boundary

1
2
3

Divisions -2

-8
-7
-6
-5
-4
-3
-2
-1

0 Boundary

1
2
3

Divisions -3

Our last move brings the denominator partially into the denominator range. Our Divisions accumulator is -3 and the difference between the top of the denominator block and the 0 boundary is 1.
So, -8 div 3 is -3 remainder 1.

Making the denominator negative, -8 div -3

We can visualise the integer division in the same way. Except, this time the denominator range that we move the denominator block into is -3, inclusive to -1, inclusive.

-8
-7
-6
-5
-4
-3
-2
-1

0 Boundary

1
2
3

Divisions 1

-8
-7
-6
-5
-4
-3
-2
-1

0 Boundary

1
2
3

Divisions 2

Our last move brings the denominator partially into the denominator range. Our Divisions accumulator is 2 and the difference between the top of the denominator block and the 0 boundary is -2.
So, -8 div -3 is 2 remainder -2.

8 div -3

-3
-2
-1
1
2
3
4
5
6
7
8

Divisions 0

0 Boundary


-3
-2
-1
1
2
3
4
5
6
7
8

Divisions -1

0 Boundary

-3
-2
-1
1
2
3
4
5
6
7
8

Divisions -2

0 Boundary

-3
-2
-1
1
2
3
4
5
6
7
8

Divisions -3

0 Boundary

Our last move brings the denominator partially into the denominator range. Our Divisions accumulator is -3 and the difference between the top of the denominator block and the 0 boundary is -1.
So, 8 div -3 is -3 remainder -1

Conclusion

So integer division, when treated like it is with div and mod in Haskell, is different to what many developers would be used to from Java or Scala. The modulus operation is really a way to restrict elements to a certain range as dictated by the denominator. This is why the denominator blocks in the above visualisation are always trying to get into the denominator range without moving past it. It also makes sense to me that, when the denominator block arrives in the denominator range, the remainder is the difference between its top and the 0 boundary.

There are a lot of ways to visualise and think about these cyclical division and modulus operations. I hope this blog may help others reason about the these operations and explore other ways of thinking about them.

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

Reading Time: 15 mins
Reading Time with hands on trying of the examples: 30 mins approx

Haskell Warm Water

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, lets 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:

5 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.

 2 
 3 public class Palindrome {
 4 
 5     public static boolean isPalindrome(String str) {
 6 
 7         int strEndIndex = str.length() - 1;
 8 
 9         for(int i = strEndIndex; i > (strEndIndex/2); i--)
10             if(str.charAt(i) != str.charAt(strEndIndex - i))
11                 return false;
12 
13         return true;
14     }
15 }

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:

 1 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"
False
ghci> isPalindromeWithRecursion "racecar"
True
ghci>

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.

 2 
 3 isPalindromeWithRecursion :: String -> Bool
 4 isPalindromeWithRecursion str =
 5   loop strEndIndex where
 6 
 7   strEndIndex = length str - 1
 8   loop i =
 9     if (i <= (div strEndIndex 2)) then True
10     else if (str !! i) /= str !! (strEndIndex - i) then False
11     else loop (i - 1)
12 

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"
False
ghci> isPalindromeWithRecursion "racecar"
True
ghci>

Guard those if then elses!

Instead of building up multiple if then elses, Haskell has this lovely construct called Guards. Using, the | symbol, we can build up boolean conditional expressions with corresponding expressions, one of which will be evaluated if its corresponding boolean expression evaluates to true.

13 isPalindromeWithRecursionAndGuard :: String -> Bool
14 isPalindromeWithRecursionAndGuard str =
15   loop strEndIndex where
16 
17     strEndIndex = length str - 1
18     loop i
19       | i <= (div strEndIndex 2) = True
20       | (str !! i) /= str !! (strEndIndex - i) = False
21       | otherwise = loop (i - 1)
22  

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)

and

 | 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. This is shown in the diagram below.

beginning-haskell-2-001

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
[1,2,3,4,5]
ghci>

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
5
ghci>

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
1
ghci>

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

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

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
[1,2,3,4]
ghci>

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.

52 
53 isPalindrome :: String -> Bool
54 isPalindrome [] = True
55 isPalindrome (x : []) = True
56 isPalindrome (x1 : x2 : []) = x1 == x2 -- this line is not necessary, thanks Szymon 
57 isPalindrome (x1 : xs)  = x1 == last xs && isPalindrome (init xs)
58 

  • 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.
  • Correction, line 56 is not necessary. Thanks for pointing this out Szymon. If a 2 element list has 2 equal values, the init on line 57 will be called on a one element List, xs, returning an empty list and on the next recursive call, line 54 will 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).

Conclusion

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.

Haskell Flavoured Curry

curry

Reading time: 10 minutes
Currying is a very useful pattern in functional programming. It is a way of breaking up a function which takes multiple parameters in to a chain of outer to inner functions, each of which, takes one parameter. It allows arguments which are known at one point in program execution to be captured and used in a later execution of a function requiring more arguments. In some ways, it’s similar to when an Object is instantiated in OO with one or more property values which are used in later function executions involving that object.

I have found that the subject of currying can be confusing for developers who are new to functional programming. It was for me at the start anyway. I used to try and relate everything back to OO but I discovered that using a substitution model approach based on the Lambda Calculus really simplified things. I won’t go into the specifics of Lambda Calculus here but I’ll give a short example of using a substitution approach in the context of understanding currying.

So, we have a function which transforms a String by prepending a certain number, n, of characters to the start of it returning a new String.

So, in pseudocode this could look like:

prepend(n, c, s) = put n c's at the start of s

Now lets execute this function:

prepend(3, 'z', "Tom")

This would result in

"zzzTom"

This function is completely pure in that it has no observable interaction with its outside context. This is extremely useful because it means that anywhere we see this function called in a program, we can substitute the call arguments into the function’s implementation without changing the meaning of our program. Functional programmers love to say “functional programming is easier to reason about” and this isn’t just a catchphrase. It is this ability to substitute arguments for parameters in expressions, along with all the other functional programming goodness like immutability, that does actually make functional programming easier to reason about.

So, using a simple substitution model, when we call

prepend(3, 'z', "Tom")

in our program, we can replace it with its implementation expression by substituting into it the arguments 3, ‘z’ and “Tom” for the parameters n, c and s respectively.

so

prepend(3, 'z', "Tom")

becomes

put 3 'z' 's at the start of "Tom"

For a curried version of this function we can break it up into three one parameter functions: (I’m using

->

here to separate a function name with its parameter and the function’s expression body – again this is pseudocode)

prependA(n) -> prependB(c) -> prependC(s) -> put n c's at the start of s

Okay, hold a while here! I know this looks kind of weird as we have three functions, starting with the outer prependA function and returning an inner function until we reach the innermost expression. This is where, before, I would have gained initial understanding by thinking about each outer closure returning its inner closure working from the outmost function, prependA to the innermost, prependC – outer to inner functions/closures is the subject of one of my earlier blogs: Closures For OO Developers – 1.
I find that trying to think in this way can start to bend the brain a little bit as higher order functions become more complex. If we look at how this works using the substitution model, things become way easier!

Okay, so lets say we know how many characters we want to prepend to a String but we don’t know what the character is or what the String is just yet. That’s okay!
We can still call our function

prependA(n)

.
So, if n is 3, we call,

prependA(3)

and substituting we 3 for n in its implementation expression, we get

prependB(c) -> prependC(s) -> put 3 c's at the start of s

Okay now, we have a function which can take, as a parameter, the character that we are prepending. At some point, we know that the character we want to prepend is ‘z’, so we call

prependB('z')

substituting z for c in its implementation expression, we get

prependC(s) = put 3 'z' 's at the start of s

Now we have a function which can take a String, s, and prepend three ‘z’ characters to the front of it to produce a new String.

At some point, we find out that the String we want to transform is “Tom” so we call:

prependC("Tom")

Now, we substitute again and this becomes:

put 3 'z' 's at the start of "Tom"

which is back to what we had when we called the original prepend(3, ‘z’, “Tom”)

Haskell likes its Curry

In the above example, I have actually shown, in a simplified way, how the function substitution would work in the Lambda Calculus.
With Haskell being an implementation of the Lambda Calculus, all functions are curried. This doesn’t mean that all functions have to be written as one parameter functions. When a function is declared with multiple parameters, Haskell breaks this up into a series of outer to inner one parameter curried functions underneath the hood. So, our prepend function from above could be declared in Haskell in a way that doesn’t look like its curried.

prepend :: Int -> Char -> String -> String 
prepend n c s = take n (repeat c) ++ s

The expression in the implementation of the prepend function above just says:
take the character, c repeated n times and stick it onto the String s to form a new String (without mutating the original String s).
The type signature is

prepend :: Int -> Char -> String -> String 

Type signatures in Haskell show the curried nature of functions with a series of types separated by

->

with the last being the return type of the function.

The prepend function above takes three parameters, n, c, and s just like the prepend function in our earlier pseudocode. However, just like how I broke this up into a series of outer to inner one parameter functions in the pseudocode, Haskell does this automatically for us.

This allows us to do some really handy stuff!

So, say we want a function to pad a String with a number of characters to the left of the String but we know that we will always want 10 characters. We can declare this as our pad10 function below.

pad10 :: Char -> String -> String 
pad10 = prepend 10

In the above code, we have simply assigned pad10 to prepend but we are only calling the prepend function with one argument, 10. Because the pretend function is automatically curried, when we call pretend 10, we get back another function which takes a character, c which in turn, when called with a character argument, will return the innermost expression which is the expression that actually does the String prepending.

We can continue with this pattern.

So, say we always want to pad a String to the left with 10 white space characters.

pad10WhiteSpaces :: String -> String 
pad10WhiteSpaces = pad10 ' '

In the Haskell code above, we again take advantage of Haskell’s automatic currying and call pad10 with 1 argument, the

' '

character. We can follow a similar substitution to our pseudocode so:

substituting

pad10 ' '

we get

prepend 10 ' '

and substituting this, we get:

take 10 (repeat ' ') ++ s

So when we call

pad10WhiteSpaces "Tom"

this substitutes to

take 10 (repeat ' ') ++ "Tom"

when executed, will produce

"          Tom"

Haskell’s automatic currying can take a bit of getting used to but it makes for beautiful code! It really shines when you want to re-use a multi parameter function to create a function that can only take fewer or even one parameter. For example, if we had a list of Strings and we wanted to produce a list of all the these same String values but with each one padded with 10 spaces. All we need is the original prepend function and this transformation would be as simple as mapping (prepend 10 ‘ ‘) over the list of Strings:

map (prepend 10 ' ') ["I", "like", "curry", "a", "lot"]

Isn’t that handy!

Executing this results in

["          I","          like","          curry","          a","          lot"]

Function Composition Is So Damn Nice in Haskell !

Reading time: 5 minutes

Haskell has some beautiful constructs and really allows for very expressive code along with maintaining strong, static typing and purity. I’ve been taking a deep dive into Haskell and the more I learn about the language, the more I’m falling for it! There are some really beautiful ways to express functional programming concepts in this language.Function composition, especially when used with point free function references, is one of them.

So, what is function composition anyway?

This is a common approach in functional programming to build a pipeline of operations by combining functions to form new functions. Its very useful in reusing existing pure functions to produce a new transformation.

e.g
f(x) = x^2
g(x) = x + 2

Functions f and g can exist on their own but maybe we want a new function which takes a number, squares it and then adds 2 to it. We don’t want to create a whole new implementation for this when the transformation in question can simply be made up of two sub transformations, the functions f and g.
So, we create a new function, call it z, which takes, the number x, calls f on it and calls g on the result of that.
So we get
z(x) = g(f(x))

Simplified expression of composition in Haskell

Functional Programming languages usually each have their own special construct for expressing the composition of functions. This can be especially useful if there are multiple functions being composed as it cuts out the need for multiple groupings of expressions. For example, if we also have the functions,

h(x) = x * 3
k(x) = x / 4

and we decide we want a new transformation to square a number, add 2 to it, then multiply it by 3 and then divide it by 4,
we end up with a composition like this:

z(x) = k(h(g(f(x))))

I know this is just pseudocode but, even still, it is becoming hard to read! And also, bear with me. I know composing transformations as simple as arithmetic is a bit contrived and could be done with just one overall arithmetic expression. The example is deliberately contrived but if you imagine a pipeline with more complex transformations like, say, processing financial trades or something, being able to break an overall transformation up into small composable transformations becomes incredibly useful!

Haskell has a beautifully simple way of expressing function composition. Lets have a look and I’ll explain the Haskell code along the way.

module FunctionComposition where 
 
f x = x^2 
 
g x = x + 2 
 
h x = x * 3 
 
k x = x / 4 
 
 
z x = k . h . g . f $ x

In the Haskell code above I have declared the four functions, f, g, h and k that I showed earlier, along with the function z which is a composition of those four. I would usually write associated type signatures with every function I write in Haskell but I have left typing out of this example to focus on the function composition construct and also an explanation of Haskell typing definitely merits its own blog post!
The function declaration syntax in Haskell is, in itself, very concise and elegant. It is simply the name that the function is being bound to followed by a space and one or more parameters, each separated by spaces, followed by = and then the expression of the function body.
So, in the case of

 f x = x^2

the name that the function is bound to is f, there is only one parameter and this is x and the expression of the function body is after the = and is
x^2

The function composition part is in the declaration of the function, z.
z x = k . h . g . f $ x

The composition is handled by the

.

in between each of the functions being combined together.

.

is in itself a function which takes which takes 2 functions, say (in pseudocode) g(x) and f(x) and returns a new function z(x) = g(f(x)). To compose up multiple functions is so simple and elegant with this simple composition function.

The

$

is just a function which applies what is on its left to what is on its right. It has the lowest precedence though so it means the function composed of f, g, h and k on its left is fully composed before being applied to x.

Also, if you prefer the reading of the sequence of transformations from left to right instead of right to left, you can simply add this just under the module declaration in the above Haskell code.

import Control.Arrow

And now, we can use >>> instead giving

z x = f >>> g >>> h >>> k $ x

What’s this “point free” thing?

Point free means expressing functions without their arguments. This may sound kind of strange for people coming from OOP or other paradigms but it actually makes for code where the reader can concentrate on the transformation that is being expressed without the code being obscured by unnecessary argument names. It is made possible in functional programming because functions can be treated as first class values and they can be bound to names just like any other values.

So, say we compose z just from the functions g and f above, the Haskell function composition would be:
z x = g . f $ x

but the x argument serves no purpose here. All we need to do is bind to z, the function which is composed of g and f. A type signature (left out here as typing is a subject for another blog post) here would serve the purpose of expressing the type of the parameter that z expects when applied. So, using the point free style the functional composition is made even more elegant and can be expressed as:

z = g . f

and composing the 4 functions f, g, h and k simply becomes:

z = k . h . g . f

Now that really is quite beautiful!