PART II OF III
From Objects to Functions
How to Convert Our Functional Design into Code
Continuing from part one, we are now ready to implement a simple URL shortener in Kotlin, following functional programming principles.
In this second post we will use a concrete example to show how to design a functional application in Kotlin. For reference, the whole code is on GitHub:
Imagining a Shorten-URL Service
Let’s imagine a scene in a fictional startup: One morning the CEO comes to our desk and asks us to implement his fantastic idea. He wants a URL shortening service.
Our service — he says — will be the only one that uses mnemonic words instead of just a random set of symbols, so people can easily read and remember the shortened URLs. Afterall, two words are much easier to remember than a random sequence of symbols.
As an example, we can encode a URL calling this API (even from a browser):
/generate?url=https://smile.amazon.com/Objects-Functions-Software-Functional-Programming/dp/1680508458And the answer will be a response with status 200 and the encoded two words in the body: dimes.space
To decode it, we can call this API:
/x/dimes.space
And the answer will be a page with the full Amazon URL, and we all can concur that dimes.space is much easier to remember that the usual URL shortener links, and not much longer. Our CEO is sure that this project will disrupt the industry of URL shorteners!
Enough said. Let’s leave the CEO with his dreams and look at how to design a fully functional solution using type transformations, one step at a time.
Working in Base 2048
Before discussing the functional design of our application, let’s have a quick look at the core algorithm of our application. Feel free to skip this section if you are not particularly interested in the mathematical details.
What we want to do is to convert an integer number to a few common English words in a way that is deterministic and reversible.
First we load a list of 2048 common English words at the start. There is nothing magic with 2048, it’s just that I like powers of two. It cannot be too large a number because we want to use common words only. It cannot be too small; otherwise, we would need to append more words.
Next, we convert our number to a two digit number in base 2048, where each digit is actually an English word. In this way we can cover all numbers up to 4 million (that is 2048 squared). Since this conversion is just a change of base, we can proceed in both ways, from number to words and vice-versa.
To understand how it works, let’s consider the convertInWords function. It will take a number like 12345 and it will split into two numbers between 0 and 2047 using the division and the modulus operation:
12345 % 2048 = 57
and
12345 / 2048 = 6
Then it will look up the word number 57 and the word number 6 from the given list. The result is “area.will.” In this way, we can convert 4 million URLs to a pair of common words.
Since we will generate a new number each time a user asks to shorten a URL, we can serve 4 million requests, enough for the first version. If we ever use all word combinations, we can add a third word to the mnemonic ShortUrl to arrive at 8 billion combinations.
This is the full code:
val base2k = 2048private val words = Words::class.java.getResource(“/word_data.txt”)
.readText().lines()private fun word(x: Int): String = words[x % base2k]fun toShortUrl(id: ShortId): ShortUrl =
ShortUrl(“${word(id.number)}.${word(id.number / base2k)}”)fun toShortId(twoWords: ShortUrl): ShortId? =
twoWords.raw.split(“.”)
.also { if (it.size != 2) return null }
.let { ws -> words.indexOf(ws.first()) to words.indexOf(ws[1])
.let { (x1, x2) -> ShortId(x1 + x2 * base2k) }
Designing with Morphisms
Now let’s approach the main point of this series of posts — how to design an application using a functional approach. Where to start?
When in doubt, a good way to start is by defining the inputs and outputs of what we want to model. In this case, the whole application.
Since we are talking about a web server application as input, we have an HTTP request with the information and either the URL to shorten or the shortened words to decode. The output will be the HTTP response with the answer to the user shown on an HTML page.
We can draw it like this:
Or in Kotlin:
fun twoWords(request: Request): Response = ...Now next step is to look inside the mysterious block in the middle. We have to implement two possible operations, so we need first to determine what the user is asking of us — in other words we need to define our API.
How do we select the best API for the user’s needs? Let’s see how the transformations can guide us. If we try to define the content of the response depending on the request there are three different cases:
- If it is a request to shorten a URL the response will contain the ShortUrl, that is the two-word mnemonic.
- If it is a request to decode a ShortUrl, the response will contain the original URL.
- Any other request will be treated as an error.
Let’s draw all the transformations in a diagram. Functions are represented as arrows that transform types into other types and the vertical lines define a pattern matching block:
The diagram is to help us to visualize what we need to do, the colors are only for making it a bit nicer, without any particular meaning.
📝 Note: My book contains many diagrams like this, where the names correspond to types and each arrow is a function. Horizontal arrows are regular functions; the vertical arrows are functions that return other functions.
Here we are declaring visually that we are considering only the three cases explained above. So there will be three different functions, each with a different signature, but in the end all results will be transformed into a HTTP response.
For this example, to keep things simple, we are using only the HTTP path (and not headers or query params, for example). So the first thing we need is a function that returns the correct function to apply given an HTTP path:
Path -> (Req -> Res )
Or in Kotlin:
fun routeFinder(path: String): (Request) -> Response = …Note that here we are returning a new function as a value. This technique is a higher-order function, which is very common in functional programming.
But before progressing, let’s implement all things discussed so far into code, even though we haven’t yet seen the actual functionality. Kickstarting a project with a kind of HelloWorld to validate our infrastructure choices is a practice called the Walking Skeleton approach, and I’m a big fan of it.
Serving HTTP Requests
Luckily for us, there is already a web library to handle requests and responses in a functional way. It’s called http4k, and using it means we don’t have to do anything apart from import it in our project. This is not the place to explain how to use http4k in detail, but it’s really simple. You can refer to the guide on the http4k website (or my book).
First we need to define our main function, which should take a request and discriminate which kind of request it is. Let’s call it twoWords, like the application. We can use theroutes function of http4k that composes our two domain functions (generate and expand) and returns a new function. The function associates a different URL path to each one using http4k DSL:
val twoWords = routes(
“/generate” bind GET to ::generate,
“/x/{short}” bind GET to ::expand
)In other words, we are binding a path to our generate function and the other to our expand function. The malformed request error case is automatically handled by http4k, so we don’t need to do anything.
The implementation of the business logic functions is just returning a place holder text for the moment:
fun generate(req: Request): Response =
Response(OK).body("Your mnemonic short Url will be here!")fun expand(req: Request): Response =
Response(OK).body("Your full Url will be here!")
To finish the walking skeleton, we need to launch the server in the main function. It’s a very simple server using http4k. Any function in the form of Request -> Response can become a web-server. In our main function we start it on port 8081 with the function twoWords:
fun main() {
val port = 8081
println("TwoWords started: http://localhost:$port/")
twoWords.asServer(Jetty(port)).start()
}And now we can start the application from the IDE to verify with a browser that it actually works. That’s it for this post. In the next post, we will look at how to implement the logic and finish the application.
Part one of this series:
It continues on part three:
💬 If you are interested posts like this one, please follow me on Medium or on my twitter account, ramtop.
If you really really liked it, consider buying my book, From Objects to Functions:
You can save 35% off the ebook using promo code uboop_medium_35 now through July 31. Promo codes are not valid on prior purchases.
