Comparing C♯ with Haskell on Expressiveness

A Haskell implementation of the algorithm

I recently came across this fairly basic, run-of-the-mill interview question that involves writing algorithms.

Given an array of elements that are positve numbers, write an algorithm to find the second largest element

I personally loathe interview questions involving algorithms because they never reflect what am I expected to actually do on the job, but I reckon it would be fun to use this question to compare the difference between C♯, a popular OOP language, and Haskell, an FP language.

If I were to write it in C♯, I would have probably written it like this:

This seems reasonably well-implemented:

  • It is generic: it works on all number types such as , , and all types of collections, as is the base type of all collections
  • It is reasonably performant: it does not do too many unnecessary allocations without sacrificing readability
  • It is reasonably readable: I took advantage of the latest and greatest language features when I think they improve comprehension, e.g. the use of on line 6

Now contrast the way if I were to write it in Haskell:

Even if we discount the syntactic noise like braces and access modifiers in the C♯ version, the Haskell version still looks way more terse and concise than the C♯ version. Now granted Haskell was designed to be highly adapted to writing number algorithms like this, I cannot help but feel every keystroke I made on the Haskell version was more purposeful than the tedious ceremony I was required to comply with in order to make the C♯ version compile.

The Haskell version is also reasonably well-implemented (pardon my basic knowledge of Haskell that may limit my ability to judge what is well-implemented):

  • It is generic: it works for all number types as well due to the typeclass constraint. It is even more generic than the C♯ version because this function would work on any structure, lists and arrays are just some examples of
  • It is reasonably performant: its usage of means it is strict and tail-recursive, thus avoiding stack overflows and stack frame allocation
  • It is reasonably readable: to untrained eyes, this might look like alien language but I can guarantee this is idiomatic Haskell and it is written professionally

But what makes the Haskell version so elegant and yet so scary to non-FP programmers? I would like to try and break it down in this article.

Deep Dive into Haskell

The first line is an import statement that imports the module. It is synonymous with how C♯’s statements bring in namespaces. Nothing too difficult here.

The third line declares the type signature of the function. It is not strictly necessary because Haskell’s compiler would have been able to figure that out itself but it is nevertheless good practice for human readers to look at the signature and have a vague idea of what the function is trying to achieve.

secondLargest :: (Num a, Ord a, Foldable t) => t a -> a

This means we are declaring a function that has two generic parameters, and , the input to the function is of the type and the output to the function is of the type . The two generic parameters have different kinds.

  • has a kind of , which means it is a type constructor that takes another type to form a proper type. You can think of it as a (open generic type) waiting for a generic argument to form a fully constructed type
  • has a kind of , which means it is already a proper type

There are also a total of three generic constraints applied to and , specified before the fat arrow, .

  • must have a instance, which resembles C♯ generic constraints to require this generic argument to implement interfaces/abstract classes. This requires to implement either or
  • must have both a instance and a instance, meaning the generic argument used must be a ‘number’ and must be able to be ‘ordered’

Let us move on to the actual implementation starting from line 4.

Point-free Style

secondLargest = snd . foldl' ...

We are immediately greeted with a peculiarity. I mentioned in the previous section that this function has one input of type , and one output of type , but line 4 clearly contradicts my statement! Nothing was between and the sign which is where our parameters should have been placed!

This, in fact, is a very common way to write Haskell and is called the point-free style. We achieved this by using the operator between and .

The operator, a.k.a the function composition operator, is the bread-and-butter of functional programming. It is defined as:

It composes two functions and , returning a third function that takes as the input that first runs through , then , returning the result.

Exactly the same is happening with : we compose with , returning a function that takes a new parameter. That is how we are able to say is a function that takes one parameter without explicitly putting that parameter in its definition.

On to the implementation

The Haskell version of the algorithm actually looks very similar to its C♯ counterpart. They both keep track of the largest and second-largest elements found so far while traversing the list.

In Haskell’s case, the traversing is done via using a two-element tuple , with the left element representing the largest element so far and the right element as the second-largest so far, as the starting state. The result is then fed to , which is a built-in function that returns the right element in the tuple, in our case, the second largest element found.

The Left Fold

First, let us examine the type signature of :

foldl' :: (Foldable t) => (b -> a -> b) -> b -> t a -> b

It requires three arguments:

  1. A function of type , which is called every time when the structure is traversed, taking the current state, of type , and the currently traversed element, of type , returning the next state, of type . We passed a helper function named here to make it clearer how the next state is computed
  2. A value of type , which is the starting state. We passed as discussed above
  3. A value of type . This is not explicitly passed in our implementation because we are leveraging currying and function composition to avoid explicitly mentioning this argument.

The fully eta-expanded version can be written as but it is usually good practice to eta-reduce when possible.

The Folder

The folding function passed into as the first argument is . It is very common for Haskllers to suffix an inner helper function with an apostrophe so that is what I have done.

is also used before it is defined. This is allowed in Haskell with the use of the keyword, where the definition of is defined after the keyword.

This helper function is defined using pattern matching and guard clauses. On line 5, we pattern match on the two-element tuple that is passed in (as the state). The elements are aptly named (for the left element), and (for the right element) to allow easy differentiation.

I have then employed guard clauses on lines 6–8 to implement the actual algorithm of determining the next state:

  • On line 6, if the current element is larger than the largest element found so far, obviously is now the largest element and the original becomes , so return as the next state
  • On line 7, else if the current element is larger than the second-largest element found so far, then we keep but take as the second-largest found so far, thus we return as the next state
  • On line 8, otherwise, is smaller or equal to and , no update of state is necessary, we return the original tuple

After is complete, we now have a tuple containing the actual largest and second-largest elements found in the . We can finally move on to the last bit.

The Final Stretch

This part is easy. We have our tuple and we feed it to a function named :

It simply returns the second element of a two-element tuple, i.e. the second-largest element from the , completing the algorithm.

Phew, that was a lot of words to explain 7 lines of Haskell code! I hope you like my explanation and you have learnt yourself some Haskell today!

Programmer | Watch enthusiast