Functional Patterns Part 1

It’s that time of the week. I finally have some free time to produce some content. Before I get started, shout out to all the people who started following, liking and recommending my stuff. You guys are the best! I’m glad I could share some knowledge with you guys and I hope I made you a little smarter!

Back to business.

If you are a coder, you have definitely heard of design patterns. If you have not, you might be a beginner, so no worries. If you’re not, don’t freak out, I got you. I’m gonna do an article on OOP patterns as well at some point, so be on the lookout for that. Design Patterns are extremely important. They let you write some really good, clean and reusable code. now, they are very different from design principals. DO NOT GET THE TWO MIXED UP. People like to ask the difference between the two during interviews and getting this wrong is a surefire way to get rejected.

Design Pattern

A design pattern is a general repeatable solution to a commonly occurring problem. The purpose of a design pattern is to leverage the wealth of knowledge of developers who came before you in order to solve old problems that you may encounter easily. It also makes communicating problems and solutions very easy. For example: creational, structural, or behavioral patterns.

Design Principal

A design principal is an established idea or best practice that facilitates the software design process. They are not language specific, so you can use them anywhere. For example: encapsulation, creating JavaBeans, is-a vs has-a relationships, object composition, etc.

I wouldn’t say memorize this word for word, but make sure you know the difference between the two and examples of each.

Seriously, getting this wrong is a rookie mistake.
Don’t get this wrong

Anyways, without further ado, you’re previously scheduled programming will commence.

Tail Recursion

Tail recursion lets you repeat computations without using mutable state and without overflowing the stack.

This patterns is used to replace iteration. Iteration is an imperative technique that requires a mutable state which goes against the FP principal of immutability. Recursion lets you iterate without immutability. But, recursion creates a new frame on the program call stack on each call. In other words, our solution takes memory proportional in size of the sequence you’re operating on (i.e Memory of O(n)). It would be insane to iterate over a million items using recursion.

We can get around this using tail recursion, which is optimized to use a single frame on the stack. This process is called tail call optimization or TCO.

As with any recursive method, you need a base case and recursive case. The base case pertains to what happens when you reach the terminal case of a recursive operation. Next is the recursive case, and this is where things get a little hairy.

The reason we have a stack that grows with each recursive call is because we need the result of the recursive call to finish the overall computation. This means that the runtime has to store intermediate values on the stack. But, if we can eliminate these intermediate values and make sure that the recursive call is the last thing that happens, we can eliminate this problem. All you have to do is pass the intermediate values in the recursive call. This takes advantage of TCO.

You can write programs like this in Java, but the JVM does not support TCO directly. Scala optimizes tail recursive calls at compile time so you get the same bytecode as iteration. You have to make sure to use the @tailrec annotation.

The structure usually goes as follows (I will try to be language agnostic):
methodName(input, accumulator){
base case: ….
recursive case: methodName(input, accumulator)

Example Usage

An example of a tail recursive method
Output for example code

As you can see, we used tail recursion to combine values from two lists and create objects from them.

Why would I use this when I can still use iteration?

Tail recursion eliminates a source of mutability. You no longer have an extra index variable. Your code explicitly states what data structures are being operated on and generated because they are both passed as parameters. Also, there are a lot of library functions available that can help you save time by shortening your code. For example: the above code can be shortened into a single line by doing the following.

Mutual/Indirect Recursion

This is really useful for some complex algorithms. Tail Recursion is considered to be self-recursive, which is great for solving some problems. But, when you get to traversing tree-like structures, you need something more complex.

In mutual recursion, instead of making the calls directly, we return a function that would make the desired call. The rest is up to the compiler or runtime. This is called a trampoline.

Scala hides a lot of details of this process and gives us two methods: tailcall() to make the mutually recursive calls and done() to call when we’re done with recursion.

Let’s look at a simple example:

Simple example

This seems to make sense. You have two methods that call each other to back and forth to solve a problem. Sure, there are better options, but just bear with me here. Everything seems to work fine, until you get to a really large number.

Output for code sample

When we got to a large number, we got a stack overflow exception. Don’t worry, we can fix this with trampolining.

Before we get to the code sample, lets check out what tools are available to us: tailcall(), done() and result().

tailcall(): makes the recursive call
done(): returns final result from recursive calls in a TailRec object
result(): returns the value stored in TailRec object

Mutual Recursion done right

This time it runs without throwing an exception, which is great.

This technique is great when working with State machines, which is an important component in the actor model(i.e. Akka). If you have time, try to use this pattern to model state changes in chemistry(i.e. Solid, Liquid, Gas, etc.).

Filter-Map-Reduce and Chaining Operations

This one should be familiar to a lot of you.

You will be chaining a sequence of operations, which lets you work cleanly with immutable data without storing a lot of intermediate values.
For example: you manipulate a sequential data structure declaratively by chaining filter, map and reduce calls to produce a new one.

The whole point here is to reduce the amount of verbose code we would normally write to process things like lists into a few lines.

filter: select the elements you want
map: transform the selected elements
reduce: combine the results (you can also use fold here)

This approach has the advantage of make code shorter and much easier to read. You can usually figure out what is happening at a glance. The downside is that not everything can be modeled this way and it can be super hard to figure out how to create a proper sequence to accomplish your goals. It takes time and a lot of practice to get this one right.

Sample code

As you can see, we easily filter for anything greater than 7, times it by 2 and sum it all up. All in a single line.

This pattern relies on declarative data manipulation, which is higher level than an iterative approach and sometimes higher level than a recursive one. It’s a lot like writing a SQL statement to search a relational database versus iterating over lines in a flat file with the same data.

Function Builder

This is a Creational Pattern, which should sound familiar to you if you’ve experience with OOP patterns.

The point is to create a function that creates functions dynamically.

Based on the input, you have a higher-order function that will return a custom function to suit your needs. This is great for modeling patterns.

It is also used for when you have static data that you need to use as the basis for some action. For example: calculating percentages.

Calculating Percents

Pretty cool right? There are lot more cool things you can do with this pattern.

Function Transformation

You can use this pattern to transform one function into another. An example of this would be negation. If you have a function that returns true for one thing, you can easily create a function that returns the negated version of it.

Function Chaining

Another cool thing you can do is chain functions. You can take a list of functions and combine them together to create an even larger function. This is similar to the Decorator Pattern, where multiple decorators, each of which does one part of some task, are chained together.

You’ll see these a lot in web application. These chains allow your application to do anything that needs to be done before handling a request(i.e. decryption, decompressing the request, checking authentication credentials, logging to a request log, etc).

Partially Applied Functions

Lastly, this technique is very useful when creating partially applied functions. If you’ve read my earlier articles, you would know that a partially applied function is one where only a subset of the arguments for an input function have been applied. The resulting function has fewer arguments than the original and keeps track of the arguments already passed in when it was created.

Lots to digest. There are still more patterns to go over. But this article is already really long. So, I’ll finish the rest next time.

There’s more to all of this. You can use these patterns with some OOP patterns. You just have to make some modifications first. I will do an article on these changes next. Like with anything in coding, the best way to let this stuff sink in is to use them. And we will. I’m almost done with these intro stuff, and I understand some of you who have read my first article have been a bit restless to get started on the project. I will do a tutorial for building a file management system really soon. It’s not going to be massive or super complicated. But it will display some of these patterns for you.

Before I get to the tutorial on the bidding system, I have to do a few more articles on concurrency, OOP patterns, Akka, Slick and Transaction models. I know. Lots of stuff. But, it will be worth it. So, hang in there.

Don’t hate me.