Go: proposal: Go 2: Higher Order Collection Functions

[fluxynet]

The proposal is to bring higher order functions to slice processing in golang.
The work could be done by golang runtime or the compiler to produce required results.

I believe not only would it greatly improve the productivity of developers,
but it would take functional programming in go even further, without adding too much complexity.

The advantages:

1. Intent is clear while complexity is hidden
2. Callbacks can be anonymous functions, or not, encourages reusability of code
3. map can be implicitly divided across processors by the runtime to maximize resource usage
4. No new syntax added
5. Can be contained in a "module", thus be backward compatible
6. Code is less verbose and tends to be shorter
7. Encourages data immutability

Rob Pike made an implementation using existing tools: https://github.com/robpike/filter
However he himself does not recommend this particular implementation.
Note that it uses reflect; not some language built-in as this proposal suggests.

Francesc Campoy also made a great talk about feasibility in his talk https://www.dotconferences.com/2015/11/francesc-campoy-flores-functional-go .
It is possible, but too complex to recommend.

Again this proposal is about having language built-ins to support higher order functions.

Many people are used to the concepts because these are very old ideas, so I will just present some examples.

map

example 1

import "collections"

data := [1,2,3,4]

//without map
mult := make([]int, len(data))
for i, x := range data {
    mult[i] = x*2
}

//with map
//the func argument is enforced to int because data is []int
//data type of multiplied is implicity []int because the func returns int
multiplied := collections.Map(data, func(x int) int {
    return x*2
})

example 2

import "collections"

type struct Results {
    Marks int `json:"marks"`
    Grade string `json:"grade"`
}

func calculate(x int) Results {
    var r Results
    r.Marks = x

    switch true {
    default:
        r.Grade = "F"
    case x >= 80:
        r.Grade = "A"
    case x >= 70:
        r.Grade = "B"
    case x >= 60:
        r.Grade = "C"
    case x >= 50:
        r.Grade = "D"
    case x >= 40:
        r.Grade = "E"
    }

    return r
}

data := [1,2,3,4]

//without map
results := make([]Results, len(data))
for i, x := range data {
    data[i] = calculate(x)
}

//with map
//the data type of res is implicitly a slice of Results
//the argument of the func is enforced to int because data is a slice of int
res := collections.Map(data, calculate)

example 3

import "collections"

type Student struct {
    Name string
    Marks []int
    Average int
}

var students []Student
students = fetchDataSet()

//without map
results := make([]Student, len(students))
for i, student := range students {
    student.Average = 0
    if n := len(student.Marks); n != 0 {
        for _, mark := range student.Marks {
            student.Average = student.Average + mark
        }

        student.Average = student.Average / n
    }

    results[i] = student
}

//with map
//the following is arguably easier to read
//the intent is clearer; the complexity itself is hidden
res := collections.Map(results, func(s Student) Student {
    student.Average := collections.Reduce(s.Marks, func(carry int, m int) int {
        return carry+m
    })

    if n := len(student.Marks); n !== 0 {
        student.Average = student.Average / n
    }

    return student
})

reduce

example 1

import "collections"

data := [1,2,3,4,5]

//without map
var sum int
for _, x := range data {
    sum = sum+x
}

//with map
sum := collections.Reduce(data, func (carry int, x int) int {
    return carry+x
})

example 2

import "collections"

type Leaderboard struct {
    Highest int
    Lowest  int
}

func checkLeader(l Leadearboard, x int) Leaderboard {
    if x > l.Highest {
        l.Highest = x
    }

    if x < l.Lowest {
        l.Lowest = x
    }

    return l
}

data := [1,2,3,-2,-3,-4,-5]

//without reduce
var ldr Leaderboard
for _, x := range data {
    ldr = checkLeader(ldr, x)
}

//with reduce
//leader type is implicity Leaderboard
//the func arguments are enforced to Leaderboard, int because it returns Leaderboard, and data is a slice of int
leader := collections.Reduce(data, checkLdr)

filter

import "collections"

data := [1,2,3,-2,-3,-4,-5]

//without Filter
var pos []int
for _, x := range data {
    if x > 0 {
        pos = append(pos, x)
    }
}

//with Filter
//positives type is same as the type of data: []int.
//func argument is int because data is a slice of int.
//func must always return bool.
positives := collections.Filter(data, func(x int) bool {
    return x > 0
})

find

import "collections"

data := [1,2,3,4,6,7,8,9,10]

func isMultipleOf(n int) func(int) bool {
    return func(x int) bool {
        if x % n == 0 {
            return true
        }
        return false
    }
}

//without Find
var (
    val   int
    found bool
)

f := isMultipleOf(5)
for _, x := range data {
    if f(x) {
        val   = x
        found = true
        break
    }
}

//with Find
//the argument of the func is enforced to be single int because data is a slice of int
val, found := collections.Find(isMultipleOf(5)) //val = 10, and found = true

findIndex

import "collections"

data := [1,2,3,4,6,7,8,9,10]

//without FindIndex
var (
    index int
    found bool
)

func isMultipleOf(n int) func(int) bool {
    return func(x int) bool {
        if x % n == 0 {
            return true
        }
        return false
    }
}

f := isMultipleOf(3)
for i, x := range data {
    if f(x) {
        index = i
        found = true
        break
    }
}

//the argument of the func is enforced to be single int because data is a slice of int
index, found := collections.Find(data, isMultipleOf(3)) //index = 2, and found = true

each

This one is not very different or more useful than a for-loop but if each function call is made to run across different routines,
and this is clearly mentionned in the documentation, it can be a real advantage.

import "collections"

data := [1,2,3,4,5]

//without Each
for x := range data {
    fmt.Printf("2 x %d = %d\n", x, x*2)
}

//with Each
collections.Each(data, func(x int) {
    fmt.Printf("2 x %d = %d\n", x, x*2)
})

[Xeoncross]

Some examples are actually less-clear I might argue:

var sum int;
for _, v := range data { sum += v }

vs

sum := collections.Reduce(data, func (carry int, v int) int { return carry+v })

However, I agree that the code and intent is easier to read in more complex cases. Nevertheless, I suspect a measurable slowdown between the new collections.Fx() and the extra couple lines needed with plain for loops in these examples.

[DylanMeeus]

A couple of thoughts, but before I get to the critique, I just want to mention that I actually like such a style of programming. (Just not in Go, perhaps).

1) Technically, you already have higher order functions in Go (Functions are first-class citizens and you can pass them along to other functions)

2) What you seem to want is to include _generic_ higher order functions. The examples you have shown are trivial to introduce in a language with Generics. However, I don't see them getting a clean solution in Go without generics. The solution of Rob is probably not the way you'd want to go about this.

This proposal seems to depend on Generics in Go2. Personally I hope generics don't get introduced in Go. And if they happen to get introduced, implementing these functions for yourself is trivial and I'm not sure if the standard library should include them.

EDIT: Another small point I want to make. But you mention:

I believe not only would it greatly improve the productivity of developers,

I'm not sure if I agree there. It seems to mostly reduce typing. But that won't be the great benefit to productivity. It just might be cleaner to read (imo).

[fluxynet]

Thank you @DylanMeeus for your thoughts.

1. Technically, you already have higher order functions in Go (Functions are first-class citizens and you can pass them along to other functions)

Yes you are right.

1. However, I don't see them getting a clean solution in Go without generics.

I am not sure - is that a technical limitation?

This proposal seems to depend on Generics in Go2. Personally I hope generics don't get introduced in Go. And if they happen to get introduced, implementing these functions for yourself is trivial and I'm not sure if the standard library should include them.

It needs not depend on generics. If we have generics it would indeed be trivial to implement, but maybe it could be implemented without having free-for-all generics.

It just might be cleaner to read (imo).

The ability to have cleaner code to read, is it not an improvement to productivity?

[DylanMeeus]

For me, not having a clean solution without generics does sound like a technical limitation.

My last argument was badly constructed, sorry, I'll try to improve it.
The ability to have cleaner code which is easier on the eyes (less overhead to read), might not be easier to "parse" (for humans).

Anecdotally, at a place where I worked we migrated to Java 8 and whilst the functional methods were _cleaner_ to read (less clutter) they were _harder_ to understand at a glance by people who did not use such methods before. Of course, this is just a matter of learning how to use the methods. :)

Anyway, I'll leave the question of productivity in the middle. For some it'll be more natural to use and for others it will not. But let's not have that distract us from the proposal at hand :)

My main complaint would be the necessity for Generics. Maybe others see a clean solution without introducing them?

[fluxynet]

My main complaint would be the necessity for Generics. Maybe others see a clean solution without introducing them?

While personally I understand the need for Generics, I am concerned that it might add complexity to the language.

This approach is fairly simple in usage, maybe not in its implementation - that's is the beauty of Go (go routines and channels are other such examples).

I am keen to know if:

1. This approach is desirable at all (by people other than myself)
2. It is feasible without free-for-all generics

[bradfitz]

Marking on hold until #15292 (generics) is resolved one way or another.

[fluxynet]

@Xeoncross:

Nevertheless, I suspect a measurable slowdown between the new collections.Fx() and the extra couple lines needed with plain for loops in these examples.

It depends on the implementation. In some cases, I might argue that there would be a measurable gain in performance where parallelism comes in effect.

For example

func aVeryTimeConsumingFunction(a SomeStruct) SomeValue

var results = make([]SomeValue, len(someInput))
for i := range someInput {
    results[i] = aVeryTimeConsumingFunction(someInput[i])
}
//above is purely sequential

//this one can be concurrent (internal implementation)
var results = collections.map(someInput, aVeryTimeConsumingFunction)

We can manually use channels and routines to achieve the same, but that is only one level of data nesting.

However, I agree that the code and intent is easier to read in more complex cases.

That is my point, with 2-3 levels of data nesting the code will become obscure with for-loop. You will need to span the code across several functions to achieve the same clarity as with the functional approach.

[ianlancetaylor]

This is a set of specific functions that could be implemented with a general purpose generics implementation if we had one. I'm going to close this in favor of #15292 . If that issues does not succeed, we can return to this idea.