Iterators, Map, Filter, Reduce and list processing in Go (Golang) : implementing Python functional features.

Git repo (examples): https://github.com/serge-hulne/iter

Update: The I have published the generic version of this code on Github under GPL license at the address: https://github.com/serge-hulne/go_iter

Latest update (23/03/2022)

The latest version uses Go Generics (Go 1.8) instead of interface{} based generics.

The generic version of this library can be used in your code with:

go get github.com/serge-hulne/go_iter

I intend to write a tutorial, specifically for that library in my next article on the subject. Stay tuned!

Intro: List and Lists processing in Python (quick refresher)

List processing is an abstraction in Python which allows you to process Lists, iterators and arrays on the same footing:

Say, you want to print the squared values of the numbers contained in the array [1, 2, 3], for instance.

A trivial, non-concise, inelegant solution consists in simply looping over the array as follows:

There’s nothing wrong with it, but it creates a new level of indentation.

Repeating said process over and over again in a list derived from a list, etc.. would result in an indented bloc… in an indented bloc… in a indented bloc, which can be hard to read, once you are N levels deep into your algorithm, as in the following example:

In order to “flatten” the formulation of said algorithm, one can make use of “list comprehension” in Python instead, as in:

Which, you will probably concede, is indeed flatter.

Nota bene : In the code above words, words_arrays can be arrays or lists of undefined length.

Lists and arrays are treated on the same footing using list comprehension. This, in turn is easy on the memory of the machine, because you can treat text of very large size (or other data sets), even if they don’t fit in an array which fits in RAM.

Basically, you can do array operations (map, filter, reduce, etc.) on non-array data (data streams of arbitrary length).

How can I do that using Go?

Go does not have built-in Lists or list comprehension. However Go does have Goroutines and channels, which makes it trivial to closely emulate these very handy Python constructs.

Example 1 : Generator

Here is a exemple of a generator (emulating Python range function)

This Go function is implemented the following way:

As announced earlier, it makes use of a channel and a goroutine.

It works as follows:

This function contains a anonymous function:

Said anonymous function, which produces the data (the list of numbers) is a closure (it “captures” the variables in the surrounding block). Furthermore it calls itself, see the opening and closing parentheses at the end of the block:

The anonymous function is launched as a separate, parallel (concurrent), process, merely by use of the go command, as in:

go func() {}

The Range() function also contains a channel object. It is used by the anonymous function to return the data it produces (integers in this instance), item by item, sequentially (thereby ensuring the sync between the producer: the anonymous function and the consumer: the Range function).

Said channel, named out, is then returned by the Range() function and can be iterated since Go channels are iterable.

ch1 := make(chan int)
...
for item := range ch1 {
    ...
}

In summary, in the example of the Range() function above, the anonymous function acts as a closure, a generator, a goroutine and returns the data to the surrounding Range() function via a channel. Said channel is blocking and serves the purpose of transferring the data and ensuring that Range() waits for every successive data item synchronously. There’s no need to pass the channel to the anonymous function as an argument, it captures it, since it is a closure.

Example 2 : A fibonacci numbers generator:

This example is similar the the Range() example.

it is used by simply calling the Fib() function:

f := Fib(10)
Fibonnaci:
i =      0
i =      1
i =      1
i =      2
i =      3
i =      5
i =      8
i =     13
i =     21
i =     34
i =     55
i =     89

Example 3: filtering a list of fibonacci numbers:

This can be done in a very functional manner as:

Filter(fibs) // returns a list of even Fibonacci numbers.
// it returns:
Filter:
i =      0
i =      2
i =      8
i =     34

The filtering operation is achieved using a goroutine and a channel in a manner similar to the one used in the generators:

Example 4: mapping a list of fibonacci numbers:

Here is an example of a mapping operation which maps every item from the incoming channel to its squared value in the outcoming channel:

It can be called on our Fibonacci sequence by merely chaining mapping and filtering:

Map(Filter(sequence))

another chaining solution is given by:

f := Filter(initial_sequence)
m := Map(f)
// m is now the same as : 
m := Map(Filter(sequence))

Example 5: Reduce:

Similarly, a reduce operation can be implemented as:

It can be used on its own or combined with Map(), Filter() as in:

or alternatively as:

A major take away from processing lists this way is that if you chain File(), Map(), Reduce() this way the processing of the incoming data stream is done concurrently (thanks to the goroutines), therefore, it doesn’t wait: Filter() starts as the first data come in, Filter() also does not wait and starts as soon as the first ‘fibs’ come in, so do Map() and Reduce().

Example 6: Enumerate:

an enumerate operation can be implemented as:

and used as:

Yielding:

Enumerate
index :     0,  value =      0
index :     1,  value =      1
index :     2,  value =      1
index :     3,  value =      2
index :     4,  value =      3
index :     5,  value =      5
index :     6,  value =      8
index :     7,  value =     13
index :     8,  value =     21
index :     9,  value =     34
index :    10,  value =     55
index :    11,  value =     89

Example 7 : Taking the N first results (Take(n)):

Implementation:

Range
index =      0, squared =      0
index =      1, squared =      1
index =      1, squared =      1
index =      2, squared =      4
index =      3, squared =      9
index =      5, squared =     25
index =      8, squared =     64

it is used as follows:

Conclusion:

Map, Filter, Reduce, Take, Range can be easily and efficiently implemented in Golang (Go) and used in a similar manner they would be used in:

• Python.
• TypeScript.
• JavaScript.
• Rust.
• Dart.
• Kotlin.

Here is the Git repo: https://github.com/serge-hulne/iter