Going Functional 2 - Our own map, purity and some functional constructs*

Introduction

In the end of the previous installment, it was mentioned that as a follow-up, we were going to implement our own versions of "powerful functional constructs". It's more accurate to call them building blocks instead. The reason is twofold:

1. In literature, both specific and non-specific to FP, these constructs tend to be showcased and explained.

2. Using a combination of these constructs, you can compose them to create more powerful logical chains.

Another aspect, also worthy of mention (*) is that these constructs constitute what I personally use on a daily basis even while working full-time with Java (since Java 8, support for a subset of functional constructs is available - what we will discuss is also part of this subset), so, more "commercially-oriented" developers can also benefit from this.

Languages we will use

I will limit all the examples to Python and Haskell, and in the end, will mention how the Java Stream API allows us to use some of these constructs.

The examples will be kept simple and self-contained, which will allow for any technically inclined person to follow, even if the programming languages are new for them. At the same time, don't let the simplicity fool you: just because the examples are short and simple, it doesn't mean the code isn't highly composable and reusable - in fact, you will be surprised how such small pieces of code can be so powerful.

The building blocks

The constructs I will explain are:

1. map - transforming operation that receives a function and an iterable and applies the function to every element of the iterable, while leaving the original unchanged.

2. anonymous functions - pure, nameless functions, where the definition is the function (because it's anonymous, we can't call the function by name, it's a simple expression. We can however, assign this expression to a variable, and use the variable "as a function").

Understanding and building the "building blocks" one at a time

I will use the definitions from the HaskellWiki and use them as a basis to show some examples, and then will implement the actual construct in my most idiomatic code possible in both Haskell and Python.

1. Map

Definition of map:

The function that applies another function to a list of arguments and obtains a list of results

Haskell has an interpreter, based on its compiler, ghc, called ghci. I'll assume that people reading this are under unix systems and, if not, firing up an online Haskell environment (or any other language, really. Check http://repl.it for the awesomeness) should be trivial.

With that out of the way, let's see how the map operation works in Haskell: we will map a number to its square.

GHCi, version 8.6.3: http://www.haskell.org/ghc/  :? for help
Prelude> square x = x*x
Prelude> l = [1,2,3,4]
Prelude> map square l
[1,4,9,16]
Prelude> l
[1,2,3,4]
Prelude>

As described above, and as we can see on line 4, map receives a function (remember how this matches Python?) and an iterable in this case a list, and applies the function to each element of the iterable. Additionally, it's possible to see that the original list is left unchanged - no side-effects.

In order to implement this operation, we need to think about what it does in informal terms:

• a function will be applied to each individual element of a list, and transform this element into its value after the function application

• if the list is empty, no function can be applied since there is no element, so we return an empty list

To implement it, we need a function object/reference/variable and we need an iterable. The operation we want to achieve will then look like this:

(f, [a,b,c...,z]) --- map ---> ([f(a),f(b),f(c)...,f(z)]

Let's see how to do this in Python, both iteratively and then recursively, by exploiting the structure of the iterable object:

>>> def map(f,iter):
...     transformed = []
...     for elem in iter:
...            
transformed.append(f(elem))
...     return transformed

The iterative version loops over each element of the list, applies the function to each element and adds the transformed element to a new list, simple and straightforward.

>>> def map(f,iter):
...     if iter[1:]==[]:
...             return [f(iter[0])]
...     else:
...             return [f(iter[0])]+map(f,iter[1:])

The recursive version works by extracting the first element of the list, apply the transforming function to it and appending it to the yet to be computed result of the recursion on the tail (the rest) of the list.
When "the rest" is empty, we end the recursion by returning a single element list with the function application.

The power of abstraction

This idea is very powerful because it's highly abstract:

When a construct, class or function is very abstract, it means it's very powerful.

There are no ties to idioms, business rules, language quirks or the real world, just pure mathematical abstraction of function application over iterable things.

What this means, is that now, you can map your business logic into this and use it as you need, how you need it:

Prices went double on some client? Map your prices list with a double function.

Need a property of an object? A list of car license plates starting from a car object? Create a function that receives a car and returns its license plate, etc, etc.

Implementing map in Haskell

The Haskell implementation of map is going to be based on the recursive version above and it'll serve to show that Haskell is actually very close in its expressiveness to the real mathematical idea behind this construct:

map :: (a -> b) -> [a] -> [b]
map _ [] = []
map f (x:xs) = f x : map f xs

The first line is a type signature. It's out of the scope of this post to explain what this is, but it tells the haskell compiler that our map function receives a function ( a->b) and a list ([a]) and returns another list ([b]).
It's important to note that these parameters and their names, are encoding the types as well as operations that are valid in the type system according to the type signature. This is very important:

functional operations need to be type compliant to be valid

This is so important in fact, that Haskell enforces the programmer to abide by this rule by embedding it in its type system.

It may seem obvious that you can't map a function to reverse strings to a list of integers, but when your domain grows larger and you apply some of these transforming operations in sequence, its easy to be lost. Haskell has our back :)

Anonymous functions

Anonymous functions, sometimes referred to as lambdas or lambda functions, are a very important construct in the functional programming world, because they combine themselves really well with other abstractions and allow the programmer to express their intent really clearly. It's functions as values defined. Let's see how we can define a lambda to square a number:

square = lambda x: x*x

Here, square is the variable name holding the value that is the lambda expression. It's similar to what we did in part one with the function reference to be passed to other function.

They compose very well with map, like this:

map(square, [1,2,3,4])
>>> [1,4,9,16]

The main advantage here is that this code is easy to read and to understand, because it clearly expresses our intent: we want to square a list of numbers. This is expressive, short and concise.

Conclusions

I hope you enjoyed to learn about map and lambda functions! Next post, filter and reduce