Monthly Archives: October 2016

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.