morgenthum.dev

Why I prefer functional programming

2019-09-14 19:15

A lot of friends and colleagues ask me why I talk about Haskell. Before I learned Haskell I always used mainstream languages like Java, C and C++ - and still like them. So how could it happen that an imperative style developer converts into a Haskell fan? In this article I want to explain it - especially for developers with less experience in functional programming.

At first I will talk about a few topics to compare functional with object oriented programming, because it's the most popular paradigm. In the first code example I will give you a short introduction into the syntax of Haskell, because I will use it throughout this article.

Control flow

The control flow describes how you can tell your program what to do - formulate algorithms. There are three basic control elements:

Object oriented programming

Here is a simple example using Java that centers a text. The text is passed as an array of strings. Every line is an element of that array:

void alignCenter(String[] text)
{
    int maxLength = 0;
    for (String line : text) {
        if (line.length() > maxLength) {
            maxLength = line.length();
        }
    }

    for (int i = 0; i < text.length; ++i)
    {
        int spaceCount = (maxLength - text[i].length()) / 2;

        StringBuilder builder = new StringBuilder();
        for (int j = 0; j < spaceCount; ++j)
        {
            builder.append(' ');
        }
        builder.append(text[i]);

        text[i] = builder.toString();
    }
}

Functional programming

Here is the same example in Haskell that shows the usage of pattern matching and a recursion:

alignCenter :: [String] -> [String]
alignCenter xs = alignCenter' maxLength xs
    where maxLength = maximum (map length xs)

alignCenter' :: Int -> [String] -> [String]
alignCenter' _ [] = []
alignCenter' n (x:xs) = (replicate spaceCount ' ' ++ x) : alignCenter' n xs
    where spaceCount = div (n - length x) 2

And here is a short version that avoids recursion by using map and a lambda function:

alignCenter :: [String] -> [String]
alignCenter xs = map (\x -> replicate (div (n - length x) 2) ' ' ++ x) xs
    where n = maximum (map length xs)

A brief introduction to Haskell

The first line of a function is the signature. The signature alignCenter :: [String] -> [String] tells us that we have a function named alignCenter which takes a list of strings as input and returns a new list of strings as output (read from left to right).

The first function determines the longest line inside the list of strings and calls the second function. We terminated the first loop of our oop code by a simple expression maximum (map length xs). So how does it work? Let's take a look at the signatures of all involved functions:

length :: [a] -> Int
map :: (a -> b) -> [a] -> [b]
maximum :: [a] -> a

The length function takes a list of whatever type and returns an Int. All lowercase types in a type signature are type variables, similar to the type T in List<T> in Java. I think it's obvious what the function does.

The map function takes two parameters, a function of type a -> b as first and [a] as second parameter and returns [b]. So what does it mean "it takes a function as parameter"? Yes, it's true! You can pass functions as parameters, neither function pointers like in C nor method references like in Java - real functions as first class values. Functions that work with functions as parameters or return new functions as result are called higher order functions. So what does this function do? It passes every element of [a] to the a -> b function which turns the a into a b and collects them into a new list [b].

Now let's resolve the type variables of map length xs, where xs is of type [String]:

map :: (String -> Int) -> [String] -> [Int]

You need to know that String is a type synonym for [Char], which denotes a list of chars. That's the reason why it's compatible to the length function. The expression map length ["Hello", "World!"] will resolve to [5, 6]. We are interested in the length of the longest string inside the list, so we pass the resulting list to maximum which returns the biggest element of the list, which is 6.

Let's take a look at the second function:

alignCenter' :: Int -> [String] -> [String]

You may noticed the ' at the end of its name. There's nothing special about it, it's just another valid character for identifiers in Haskell, because it's an usual notation in mathematics to represent names that are related to a prior identifier. The function works recursive, we go through every line of the text, do the transformation and prepend the transformed line to the recursive call with all remaining elements.

The line alignCenter' _ [] = [] is the base case of the recursion. It means: If the second parameter is an empty list, then return an empty list, because there's nothing to do. In this case we are not interested into the value of the first parameter, so we don't need to name it and leave it with _.

The following lines do the whole work:

alignCenter' n (x:xs) = (replicate spaceCount ' ' ++ x) : alignCenter' n xs
    where spaceCount = div (n - length x) 2

We bind the first parameter to n and pattern match the second parameter, which is a list, against the pattern (x:xs), which means: Bind the first element of the list to x and all remaining elements to xs. We replicate as many spaces as we need, concat them with the current element x and prepend the result with : to the resulting list of the recursive call with all remaining elements xs. That's all.

It's important to declare the base case of the recursion before the reduction step, because the compiler runs top down and takes the first matching pattern it can find.

Conclusion

We saved a lot of code by using pattern matching and abstract functions compared to the OOP version of the same code above. Okay, now you may complain: "Mhh, you are just hiding the whole code behind library functions like replicate, map and maximum" - and I tell you: "Yes, sure! Because I don't need to write the same for loops hundreds of thousands of times!". To be honest, the Java code could use something like leftPad to replicate the spaces, but it's a very concrete function, specially for the purpose to fill up strings, nothing else. In functional programming you are able to abstract common loop cases in a simple way to do tasks like mapping, filtering, folding and unfolding. In OOP you won't achieve a comparable elegant solution without a lot of boilerplate code like interfaces behind the scenes and builtin syntactic sugar.

Concepts

The concepts describe the basic idea how to build up an application. How is code, data and their interaction represented in the respective paradigm?

Object oriented programming

OOP introduced the concept of interfaces, classes, inheritance and objects, which consist of fields as data and methods as code. The methods operate on the fields to mutate the objects state.

Functional programming

The core concept is the function. You can do a lot more things with them as with methods in OOP, for example:

The output of a function evaluation only depends on it's inputs. It means that there are no hidden mutable variables that can influence the outcome of a function. That greatly increases testability.

Data is represented by algebraic data types. In functional programming you don't put data and code together in a container like classes. You build a set of data types and a separate set of functions that operate on these types. The data types don't know what functions they are used by, because they know nothing about functions, and each function doesn't know that there are another functions that also operate on the same data types.

Here a few examples of data types in Haskell, just to give you a taste how it looks like:

data Bool = False | True

data Customer = Customer Int String

data Customer' = Customer' {
    customerId :: Int,
    customerName :: String
}

There's always a data type name and a |-separated list of constructor names with optional parameters. The first example is straight forward. The second example has one constructor with the same name as the type, and two parameters. The last example is equally to the previous, but with named parameters, which is called record syntax.

Data in Haskell is immutable, which means, you can't change the value of the name of a Customer, instead you need to create a new one with the changed name.

Conclusion

Let's say, you have a real world problem that you need to solve. What are your first steps? You try to decompose the problem into smaller problems, and smaller problems, and so on. Then you need to describe your problem, which means that you put your problem into the slang of the programming language of your choice.

In the case of OOP you need to discover classes together with their fields and methods, find similarities, put them into abstract classes and in the end derive them to build concrete classes you can work with.

In FP you start with functions. One function for one very small problem, which works with very small types. In the best case the types contain exactly the information that your function needs, not more or less. That ensures that both, the type and the function, almost never need to change, except your problem changes, even when you completely refactor the rest of your application. It turns out that you also decompose your logical types or business entities into small technical types, which enables painless and safe refactorings.

Coupling

Coupling says how strong components relate to each other and will be effected by changes of one component.

Object oriented programming

Objects that communicate with each other in a direct way are tightly coupled. One way to limit the coupling is to apply principles like dependency inversion, which says you should communicate over abstractions, e.g. interfaces, instead of implementations, e.g. classes.

You define interfaces for the implementations you want to be able to exchange. To prevent big generalized interfaces you should choose only a few high cohesive methods for one interface - that's called interface segregation. If you don't get it right, you will likely end up with dummy interface implementations in the long run, like throwing UnsupportedOperationException or returning dummy values in empty method bodies.

When it comes to interface implementations, you often add abstract classes that implement parts of your interface and leave interface methods untouched to be implemented by concrete implementations - that's the way how inheritance works, which is the tightest coupling in OOP.

The idea of object orientation and inheritance is to bring programming closer to the real world. You all know examples like: "There are two base classes Vehicle and Ship for two derived classes Car and Truck. But what do you do with Amphibian?". It shares characteristics with both base classes - so you would need multiple inheritance, which is a bad idea, because of the diamond problem. To solve those problems developers introduced principles like composition over inheritance, which says you should compose objects out of exchangeable components. Obviously, composition over inheritance strives a bit against one of the original key concepts of OOP - which is inheritance.

As you can see, it's all about the right class and interface structure - and there are a lot more principles, anti-principles and patterns you need to care about to come up with a good software design.

Last but not least, a simple example that shows the use of the dependency inversion principle to loosely couple a sort algorithm to the compare logic, using an interface as abstraction:

interface Comparator<T>
{
    int compare(T o1, T o2);
}

class ArcaneComparator<T> implements Comparator<T>
{
    public int compare(T o1, T o2)
    {
        // Insert arcane compare implementation here
    }
}

class Arrays
{
    static <T> void sort(T[] a, Comparator<? super T> c)
    {
        // Uses comparator c,
        // without knowledge of concrete implementation
    }
}

Functional programming

In FP you compose instead of couple components. Loosely couple functions in FP means abstracting functions by recognizing similarities, factor out details, build higher order functions and parameterize them with details.

Let's take a look at the following situation:

sortById :: [Customer] -> [Customer]
sortByName :: [Customer] -> [Customer]

There are two functions that do quite the same thing - they sort, by some criteria. So why we don't put the similarities into a new function to prevent duplication?

data Ordering = LT | EQ | GT

...

sort :: (Customer -> Customer -> Ordering) -> [Customer] -> [Customer]
compareId :: Customer -> Customer -> Ordering
compareName :: Customer -> Customer -> Ordering

or with a type synonym:

type Compare = Customer -> Customer -> Ordering

sort :: Compare -> [Customer] -> [Customer]
compareId :: Compare
compareName :: Compare

The first parameter of sort is a function of type Customer -> Customer -> Ordering, which means it takes two customers and returns LT, EQ or GT for either less than, equals or greater than. So what's the difference? We factored out the said criteria by which the list gets sorted. Instead of sortById we can now write sort compareId. If you still want to call it sortById you can easily do it:

sortById :: [Customer] -> [Customer]
sortById customers = sort compareId customers

or

sortById :: [Customer] -> [Customer]
sortById = sort compareId

The second version may seems a bit unclear for your new functional brain, so I would suggest to better look at the first one. If you are interested how the second one works, you can read about it, it's called eta conversion.

The sort function still depends on the Customer type, which isn't important anymore, because these details were factored out. Only the compare function is interested in the details of the type. So we can replace it with a type variable:

sort :: (a -> a -> Ordering) -> [a] -> [a]

Conclusion

We were able to express the same functionality in either way. In OOP we were using language features like an interface with a class that implements this interface. In FP we had, well, functions. The type a -> a -> Ordering expresses the interface, and every function that matches this type is a potential implementation of this interface.

What I've left open

A few facts

Final words

For me, personally, feels functional programming much more clean than object oriented programming.

You can write the same functionality

and you get

Thank you for not TLDR-quitting!

Comments

by Edward de Jong at 2019-09-16 10:34

I don't this is a good example of the advantages of functional programming. Firstly, it is far too short a program to exercise anything but the most trivial of features of a language. Secondly, the Haskell example is pretty ugly. String manipulation is not a strong suit of the language. The Beads language example is slightly shorter than Haskell, and only uses the length, pad and max functions, all very standard library kinds of things. It would have been a more interesting example if you stored the length array and then referred to it later so you don't scan the strings two times. Also drawing strings centered with proportional type is not going to work with space padding, so this is a highly unrealistic example, hardly anyone uses monospaced fonts.

by Leif at 2019-09-16 19:17

@Edward: monospace font is used in programming and terminals (in which to pretty-print stuff may well involve centering). And String = [Char] is entirely hidden in this example, things certainly are less "ugly" than in the Java counterpart. But remembering the length is a nice idea! I would otherwise suggest simply writing: aligncenter' n = map (\l -> replicate (div (n - length l) 2) ' ' ++ l) and pointing out (again) that recursion just for traversal of a simple list is readily abstracted with map. If inline lambdas are too much for convertites, put the map in aligncenter and have the lambda be aligncenter' instead, consuming only a single line.

by Mario at 2019-09-16 19:28

@Leif: Yes, it would completely remove the recursion.

by Leif at 2019-09-16 20:14

You say it like that is undesirable, because you want to show off recursion. If so, I have to agree this is not a good example overall because it explicates recursion unnecessarily, it looks just as silly as expanding map length into a lengths (x:xs) = length x : lengths xs.

by Mario at 2019-09-16 21:04

I didn't change it but added it. My original thoughts were to show pattern matching (selection) and recursion (repetition). But it's a good idea to show what's possible. Thank you!

by Leif at 2019-09-16 22:20

Also, the comments appear to be HTML-encoded but not decoded again. Or maybe this only happens inside code? '.'

by Leif at 2019-09-16 23:00

Oh, now the code blocks aren't there anymore, thanks for the hotfix (?) And thanks for adding the concise version. Wasn't really necessary though, for the purposes of the post... but I should just stop bickering. Actually thought it was easy to find a slightly more complicated example where you can't just map or fold but it's hard! Higher-order functions are so powerful, explicit recursion is more for performance and strictness control.

by baverman at 2019-09-19 20:44

> You can write the same functionality > more abstract > in less amount of code > with less boilerplate features

cat /usr/share/doc/bash/README | python3 -c 'import sys; lines=list(sys.stdin); w=max(map(len, lines)) - 1; list(map(print, (it[:-1].center(w) for it in lines)))'

Look ma, Python is better functional language then Haskell.

by C# at 2019-09-20 12:55

        void alignCenter(String[] text)
        {
            var maxLength = text.Select(line => line.Length).Concat(new[] { 0 }).Max();

            for (var i = 0; i < text.Length; ++i)
                text[i] = text[i].PadLeft((maxLength - text[i].Length) / 2);
        }

by Mario at 2019-09-26 18:01

@baverman: But you don't get higher maintainability because of dynamic typing.

Write a comment