In the previous post I was trying to show you how to live without equality operator. This time I will try to kill yet another unnecessary abstraction, that all of us were addicted to at some point.

I can has no loopz?

I was of course talking about loops. One of very first abstractions that made programming actually possible. I am not saying that every single loop is evil, but I would say that when it comes to mutating data I think there might be better ways.

In Elixir you don’t have traditional loops. Why?! Because all of the Elixir data is immutable. It would make no sense to constantly increment values. As seen in my previous post you can get away with using recursion, but in most cases it can be done using Enum module.

Map

Enum.map is basically a function that takes an enumerable (most of collections, lists, maps etc.) as an argument and takes also a function as second argument and applies that function to every single element of the collection and returns new collection.

In Elixir map operation takes two parameters: collection on which it will perform computations and function reference that will be applied on every single element of that collection. Let’s assume we want to multiply list’s elements by number 2.

//That's how you would do in imperative language
for(int i = 0; i < n; i++){
  collection[i] = collection[i] * 2;
}

#and that's how you would do it in more functional oriented language
Enum.map(collection, fn a-> a*2 end)
#or in shorthand
Enum.map(collection, &(&1*2))

As you can see Functional way is way more compact and readable. Yet another plus is that if data is immutable, you’ll still have access to previous data state as you can see in following example:

list = [1,2,3,4]
changed_list = Enum.map(list, &(&1 *2))

Try for yourself

Reduction

It is yet another important operation. It allows you to take a bunch of things and turn into one totally brand new thing. And most common task we all have been through on the beginning of our IT career was performing a summation. So let’s just assume that we have to implement such thing right now.

double sum = 0;
for(int i = 0; i < n; i++){
  sum += collection[i];
}

#List is any list of numbers
Enum.reduce(list, 0, fn element, acc -> element+acc end)
#or
Enum.reduce(list, 0,&(&1 + &2))

As you might have guessed so far, that function you pass must take two arguments: current element and accumulator. On the first slot function will receive an element from the list and second element is an accumulator. Accumulator is just value that was returned in previous iteration thus function must return a single value. And that’s exactly why we supplied that 0 in second slot. It will be treated as result of iteration prior to first. If you would look at docs you would realize that’s there is also reduce/2. It doesn’t take an initial value and will treat first element of collection as first accumulator.

list = [1,2,3,4]
result = Enum.reduce(list, 0, fn element, acc -> element+acc end)
another_result = Enum.reduce([0 | list], fn element, acc -> element+acc end)

Try for yourself

Map & Reduce

Let’s take a little bit harder example that will involve combining those two. Matrix multiplication is very easy to implement when we have random access to elements, but as you may noticed we have been only accessing elements sequentially. If we would do this in C we would just take two matrices multiply corresponding elements (row X column, first element in row times first element in the collumn and so forth and so on). And in functional languages that’s not very efficient. We technically could operate on parallel rows by zipping two rows together. If you recall your math lessons you probably know operation called matrix transposition, which is basically swapping rows and columns.

Sample transposition

Original matrix
[1, 2, 3]
[4, 5, 6]
[7, 8, 9]


Transposed
[1, 4, 7]
[2, 5, 8]
[3, 6, 9]

Remember the zip I mentioned? It will prove pretty handy here. Matrix is basically lists of lists. Zipping takes nth elements of m lists and group those element into a single tuple which can be conveniently converted into list… Do you see where this is going to?

List.zip(matrix)
|> Enum.map(&Tuple.to_list(&1))

Try for yourself

Knowing that rest is pretty easy. You have two matrices. First one you’ll have to transpose, then zip corresponding rows and reduce them multiplying elements of zipped tuples and summing them. Consider this your homework. Here is an example solution and sample implementation in one of the elixir existing libraries .

Why does this matter?

Those two operations are most prominent and well known to all of functional programmers. The legend says that every operation that transform a collection using loop can be also done using those two functions and that’s exactly from where Hadoop MapReduce name comes from.

If you’re coming from an imperative ecosystem you probably noticed that this code may be slower than it’s imperative counterpart. It has a lot of function calls, a bunch of map and reduce operations… But there is a catch! A big one actually. Most of operations we’ve done depend on map, zip and reduce implementation. And map can be very easily made parallel! Thus your code can be run simultaneously on all of the cores without any headache (mostly). Actually author of library I mentioned earlier implemented this algorithm in parallel .