GDScript: Basic Functional Concepts - Map, Filter, Reduce

[OniLink]

Godot version:
3.0.2

Issue description:
GDScript presently lacks some basic concepts of functional programming. While GDScript is not a functional language, these features would still be useful. In particular, I recently encountered a situation where filter would have been useful to me had it been built-in.

These functions may be better implemented if lambda expressions are implemented first, but I imagine they would be useful additions as methods for Arrays.

map: Applies a function to each item of a list
filter: Reduces a list to those items which fulfill a given criteria
reduce: Performs a pairwise operation to combine all items of a list into one item.

[Zylann]

Maybe they can take a funcref before proper lambdas get implemented?

[poke1024]

Note that if Python style list comprehensions get implemented (e.g. #15222), map and filter would be simple to add, as they will be syntactic sugar:

map(f, x) = [f(z) for z in x]
filter(f, x) = [z for z in x if f(z)]

[razcore-rad]

I'd propose to think a bit more about this, should these be global functions that operate on lists/streams such as arrays? Or methods of the objects. I'd like the methods of objects idea if the map, reduce etc. would work with iterators in mind, not just lists/arrays. So if array would inherit from a base iterator class and that class could be extended in gdscript that would be nice although I'm not sure if it's possible.

Having this as methods certainly will look better than having them as global functions, but with global functions that operate on objects that implement a more generic iterator interface, that would open up a lot more options.

If anyone has any other ideas...

[mpicard]

Honestly I prefer the JavaScript way to the Python way when it comes to these functional operatives. Maybe it's subjective but I find var new_list = [...].map('name_of_map_function') a lot more expressive/clean. It makes it more clear what the operation is operating on, it's working on the Array it's being called from. Instead of passing a reference and mutating the array, these functional concepts work best if they return new Arrays (aka immutable).

I know that in Python it was not really popular having to use a global function for map/reduce. If the iterator interface implemented or virtual method and the Array inherited it I think that would be best, but looks like the Array interface doesn't inherit from any iterator right now? Just my 2c

[jahd2602]

Given that GDScript is based on Python, the goal should be that implementation: (See Python docs on that)

map(lambda x: x+x, (1, 2, 3))

Gives:

[2, 4, 6]

Given that we don't have first-class functions, nor lambdas, we should go for a temporary solution:

map(funcref(self, "duplicate"), [1, 2, 3])

[jabcross]

@jahd2602 Implementing that in GDScript is not that difficult. Something like:

static func map(function: FuncRef, i_array: Array)->Array:
    var o_array := []
    for value in i_array:
        o_array.append(function.call_func(value))
    return o_array

should do nicely. Its not as optimized as it could be, tho.

The main benefit from using the functional style is by using lambdas, anyways. There's not much point in using it if we can't do inline functions.

[jahd2602]

@jabcross Thanks for the snippet. It is good enough for now until lambdas are ready.

[Thijs-Riezebeek]

Thanks @jabcross for the snippet! Very useful to me as someone who doesn't have a lot of GDScript experience 😅 .

And for those looking to filter an Array, below is the aforementioned snipped rewritten to a filter function I needed for my project anyway:

static func filter(filter_function: FuncRef, candidate_array: Array)->Array:
    var filtered_array := []

    for candidate_value in candidate_array:
        if filter_function.call_func(candidate_value):
            filtered_array.append(candidate_value)

    return filtered_array

[jahd2602]

For completion sake, this is the filter function:

static func reduce(function: FuncRef, i_array: Array, first = null):
	assert_true(i_array.size() + (1 if first else 0) >= 2)
	var acc = first
	var start := 0
	if acc == null:
		acc = i_array[0]
		start = 1
	for index in range(start,i_array.size()):
		acc = function.call_func(acc,i_array[index])
	return acc

[mnn]

I miss a lot of features from Scala and similar languages, so I put together an FP library which I use in our small project. I even managed to simulate lambdas/anonymous functions (without closures, but you can use "context").

Few warnings: It is not finished (but basics like map/filter/fold are there, everything should be covered by tests), some parts are ugly and I imagine performance of some functions is very far from ideal.

Take a look at: https://gitlab.com/monnef/golden-gadget

[ttencate]

One big point that many people seem to be overlooking is that the usefulness of these functional basics is limited unless we also have closures, which are not the same as lambdas. A closure can also capture variables or values from its environment. Without closures, even simple stuff like this would be impossible:

func find_person_by_name(people: Array, name: String) -> Person:
    return people.find(lambda p: p.name == name)

To make this work, the anonymous function (lambda) needs to capture the name variable from the scope in which the lambda was created. With all the lifetime and memory management issues that come with that.

I don't know the current state of lambdas in the master version of GDScript. Are they closures already, or should a separate feature proposal be created for that?

[ghost]

For sake of completeness, please add every (all), some (any) and reduce_right.

[Calinou]

For sake of completeness, please add every (all), some (any) and reduce_right.

Feature proposals should now be made on the Godot proposals repository 🙂