It is a well-known engineering principle, that you should always use the weakest technology capable of solving your problem - the weakest technology is likely the cheapest, easiest to maintain, extend or replace and there are no sane arguments for using anything else.

The main problem with this principle is marketing - few people would sell you a 10$ product that can solve your problem for ever, when they can sell you a 1000$ product, with 10$ per month maintenance cost, that will become obsolete after 10 years. If you listen to the “experts” you would likely end up not with the simplest, but with the most advanced technology.

And with software the situation is particularly bad, because the simplest technologies often cost zero, and so they have zero marketing budget. And since nobody would be benefiting from convincing you to use something that does not cost anything, nobody is actively selling those. In this post, I will try to fill that gap by reviewing some technologies for web publishing that are based on plain text and putting forward their benefits. Read on to understand why and how you should write everything you write in plain text files and self-publish them on your own website.

The if statement (or if expression) is the cornerstone of every modern programming language - it is so pervasive that we rarely think about how exactly should we use it, or how it is meant to be used. But despite its popularity, if wasn’t always there, and it wasn’t as pervasive as nowadays, so its role is, I’d argue, still somewhat misunderstood. So in this article, I will examine some mistakes that we can easily avoid in order to improve on our code.

I really am not the best person to author such an article (I am not that into programming anymore, and I never was a real expert in it), however I am doing it, because I have been waiting for someone else to write it for years and kept noticing the following phenomena:

1. People who understand functional programming, cannot make themselves understood by the general (programming) public.
2. Many of the people who are able to make themselves understood by the public, don’t understand enough for them to be worth listening (all functional programming articles that are understandable don’t go much farther than “You should use pure functions, man!”.

Roughly the same thing has been called “the curse of the monad” by some people: “Once you understand it, you lose the ability to explain it”. It is clear now that monads are not something you get in an afternoon, but I think you can get some idea of what FP (functional programming) is. Or, you know, in a year or so. But in order to spend that time you need some motivation. You probably need someone to tell you why exactly do you need to know about FP? Why is it awesome, so to say. And so my article begins.

Haskell is great. And I want more people to know it, so this is just a quick overview of it’s capabilities, using the code to solve a simple task I saw on Mastodon.

The task is the following:

Return a list of all combinations (i.e. order doesn’t matter) of the given length. Example: Given “abc” and 2 the answer is [“ab”,”ac”,”bc”] but order doesn’t matter at either level.

It’s solution begins with a type signature, which in our case is the following:

combinations :: Show a => [a] -> Int -> [[a]]

A short guide to type signatures

Here are several specifics of Haskell type signatures:

Firstly, you’d notice they go on a separate line from the implementation e.g. instead of:

foo (a : Int) : Int -> a + 1

we do:

foo :: Int -> Int
foo a = a + 1

Secondly, there is no syntactic difference the parameter of the function and the return types i.e. instead of

combinations :: ([a], Int) -> [[a]]

(i.e. combinations accepts a list and an integer and returns a list of lists.)

We usually write

combinations :: [a] -> Int -> [[a]]

(i.e. combinations accepts a list and returns a function that accepts an integer and returns a list of lists.)

You would realize that this isn’t such a huge deal, once you understand that you can easily convert the former to the latter with the following higher-order function:

uncurry :: (a -> b -> c) -> (a, b) -> c
uncurry f = \(a, b) -> (f a) b

Oh, and I forgot one thing — a, b and c are all abstract types, but you don’t have to write stuff like

uncurry <a, b, c> :: (a -> b -> c) -> (a, b) -> c

Haskell figures that out by itself.

So, let’s continue with our task, namely:

Return a list of all combinations (i.e. order doesn’t matter) of the given length. Example: Given “abc” and 2 the answer is [“ab”,”ac”,”bc”] but order doesn’t matter at either level.

You may think you need sets to solve this. Not true! It is enough to use recursion.

A short guide to recursion

Haskell uses recursion to traverse lists, which you might think is more complex than traditional approach, but is actually quite simple. e.g. instead of doing this to sum the elements of a list:

function sumList(list) {
  let total = 0;
  for (let i = 0; i < list.length; i++) {
    total += list[i];
  }
  return total;
}

We do this:

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

Or in English

“The sum of the elements of an empty lists is zero.” “The sum of the elements of a lists is the first element, combined with the sum of the rest of the elements”

(“x:xs” is a pattern match, where “x” is matched by the first element of the list (known as “head”) and “xs” — by the rest of the elements)

The definition is simple, as lists themselves are a recursive (or an inductinve data type, as it is sometimes called). Here is how would you define the list data type in Haskell:

data [a] where
    []  :: List a                   
    (:) :: a -> List a -> List a

Or in short:

data [a] = [] | a : [a]

By the way, this is the actual definition of lists in Haskell (in Haskell, the list construction operator : is a function, like all other operators.

If you understand these definitions, you would realize that list traversal functions like sum use the same pattern as the definition of the list data structure itself.

Base cases

So, back to our task (again).

In a recursive definition, we clear out the base cases first. In our case there are two of them, as we have two values that we operate on: one list (of letters) and one number (the length of the sequence).

We know that there are no combinations of an empty list of letters (we don’t care what the length is, so we use the underscore).

combinations [] _ = []

What about combinations of length 0? You might think that this is also empty, but there is one such combination, namely the empty string (it is important to return it, else the whole thing won’t work):

combinations _ 0 = [[]]

You’d notice that we write those two definitions separately. That’s because…

A short guide to pattern matching

…because Haskell supports multiple functional definitions, that use different pattern matches, so instead of:

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

we can write:

sumList []     = 0               
sumList (x:xs) = x + sumList xs

More, the language would detect if we missed something, making it impossible for a runtime error to occur.

Actual Solution

And now let’s finally solve this task.

Excluding the base cases, the solution is:

combinations (letter : letters) n = 
  combinations letters n
    ++ map (letter :) (combinations letters (n -1))

But what does that mean? Let’s break it down:

combinations (letter : letters) n = 

We take the first letter and the rest of the letters (we are guaranteed that the list is not empty, because we already handled the base case) and we take the length, so, if we use the example data, we would have:

letter = 'a'
letters = ['b', 'c']
length = 3

Now, a combination of letters can either include this letter, like ["ab","ac"], or does not include it, like ["bc"].

We find the combinations that don’t include the letter, letter by calling combinations with the rest of the letters:

  combinations letters n

Now, the most complicated case is finding the combinations that do include the letter. To find them, we take the combinations that do not include it, with length - 1 and then prepend the letter to each of them.

    ++ map (letter :) (combinations letters (n -1))

So, for our data, this be map ('a':) (combinations ['b', 'c'] 1) which would generate ["ab","ac"].

You should know enough to understand what this code does: we use the higher-order function map to prepend the letter, and we feed it the function letter :, which is short (curried) for \a -> letter : a.

Conclusion

We verify that our code leads to the base cases, subtracting 1 from n and taking letters from the letters array, until both are 0.

If we reach the first base case:

combinations [] _ = []

This means our solution is not valid (we ran out of letters and we still don’t have a combination). In this case, the expression would evaluate to map (letter :) [] which would evaluate to [].

If we reach the second one (where the length is zero)

combinations _ 0 = [[]]

In this case, we would have reached a valid solution. The previous clauses would prepend all letters which make up the combination.