My first-time pure functional programming

Yesterday I had my first experience with pure functional programming. I heard this term, functional programming, nearly a year ago. Since then I became fascinated by the concept but I never dug deep into the paradigm.

This semester I decided to enroll in a course on principles of programming languages. I am now learning Haskell, and specifically the pure functional programming paradigm at its core.

Yesterday was my first coding session with functional programming. I report here my experience as a reminder for myself and as a source of inspiration for newcomers.

It was not easy, but it was fun.

Installation

I skip the installation details. I am on Windows. What I did was going to Haskell, in the Downloads section, and follow the instructions. There are also plenty of videos on Youtube, so this should be the easy part.

Coding exercises

I found an interesting website here. It contains 12 weeks of lessons and homework for each week. Every homework is tailored for the knowledge that you should have acquired if you followed the previous weeks' lessons. Perfect, I started from here.

Task 1 - Reasoning as a javascript developer

The first task I tackled is:

Double the value of every second digit beginning from the right. That is, the last digit is unchanged; the second-to-last digit is doubled; the third-to-last digit is unchanged; and so on.

For example, [1, 3, 8, 6] becomes [2, 3, 16, 6].

https://www.seas.upenn.edu/~cis194/spring13/hw/01-intro.pdf

Now, I read somewhere that the first and most important step is to define the input and output types of the function. The types will help you reason on the problem and (hopefully) understand better the solution.

Coming from javascript and dart, I knew of the map function. Specifically, the map with index. I also knew that also Haskell has the map function, but the signature does not provide the index of the element.

My idea was to use the index to compute if the current position is even or odd and applying the doubling when needed. So, my first task became creating a map indexed function in Haskell.

I copied the type signature of the map function in Haskell:

(a -> b) -> [a] -> [b]

I then created a helper function that takes also the initial index as input.

The function has three arguments:

The mapping function, from the element a of the source list and the index position Int to the mapped element b of the resulting list
The initial index as Int
The source list to map [a]

mapIndexedManual :: (a -> Int -> b) -> Int -> [a] -> [b]
mapIndexedManual f n [] = []
mapIndexedManual f n (x : xs) = f x n : mapIndexedManual f (n + 1) xs

Using this function I was able to write the map indexed by passing an initial index value of 0:

mapIndexed :: (a -> Int -> b) -> [a] -> [b]
mapIndexed f [] = []
mapIndexed f l = mapIndexedManual f 0 l

Using this function it becomes easy to complete the first exercise of the homework:

doubleEven :: [Int] -> [Int]
doubleEven n = mapIndexed (\x i -> if i `mod` 2 == 0 then (x + x) else x) n

List of the concepts used:

Task 2 - Function composition

Add the digits of the doubled values and the undoubled digits from the original number.

For example, [2, 3, 16, 6] becomes 2 + 3 + 1 + 6 + 6 = 18.

https://www.seas.upenn.edu/~cis194/spring13/hw/01-intro.pdf

This is a more technical problem. I have some memories of my programming 101 classes in which we reasoned about how to sum the digits of a number.

The first function I wrote is recursive. It sums the digits of a given Int:

sumDigits :: Int -> Int
sumDigits n = if n < 10 then n else ((sumDigits (n `mod` 10)) + (sumDigits (n `div` 10)))

I had some problems with the div function. I tried to use the standard / but it caused problems with the type conversion. It took me some time to end up using the div.

This function is recursive. It sums directly single digits numbers (n < 10) and otherwise extracts each digit in a recursive call.

That was the difficult part of the second exercise. From there I just wrote some more functions to apply the sumDigit to each element of a list and then sum the elements of the list:

sumList :: [Int] -> Int
sumList [] = 0
sumList (x : xs) = x + sumList xs

addDigits :: [Int] -> [Int]
addDigits [] = []
addDigits l = map sumDigits l

addSumDigits :: [Int] -> Int
addSumDigits l = sumList (addDigits l)

Here I noticed one interesting result of the functional programming paradigm. I was forced to write single self-contained functions and reason about each of them. Then the solution would simply be a composition of smaller pure function.

In the example, addSumDigits becomes the composition of sumList and addDigits, that itself used the sumDigits function written above.

List of the concepts used:

div
map
Recursion

Task 3

Calculate the remainder when the sum is divided by 10. For the above example, the remainder would be 8. If the result equals 0, then the number is valid.

https://www.seas.upenn.edu/~cis194/spring13/hw/01-intro.pdf

By this point, I became more accustomed to the process of writing pure functions. Using the functions of task 1 and task 2, the solution to the full problem became straightforward:

checkValid :: Int -> Bool
checkValid n = n `mod` 10 == 0

allInOne :: [Int] -> Bool
allInOne n = checkValid (addSumDigits (doubleEven n))

Once again, we notice how the final complete function is just a composition of the other functions. Since all the functions are pure, the output of allInOne will always be the same given the same input.

Furthermore, everything is type-safe; the compiler will not allow you to pass incompatible parameters. Therefore, we can be sure that the function is correct (given that we did not make any logic mistakes in the other functions).

Conclusion

Writing functional code is not easy. Years of imperative programming makes it even more uncomfortable. Nonetheless, you feel satisfied when you are finally able to complete the puzzle.

It took me about 3 hours to write those functions. Most of the time I spent thinking about what types my function should have based on the solution I had in mind.

It had a lot of fun overall. I know that there is a lot (a lot) more in functional programming and Haskell. Anyhow, I am happy I was able to complete the exercises successfully.