proposal: Go 2: Higher Order Collection Functions #31513

fluxynet · 2019-04-17T10:11:40Z

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:

Intent is clear while complexity is hidden
Callbacks can be anonymous functions, or not, encourages reusability of code
map can be implicitly divided across processors by the runtime to maximize resource usage
No new syntax added
Can be contained in a "module", thus be backward compatible
Code is less verbose and tends to be shorter
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)
})

The text was updated successfully, but these errors were encountered:

xeoncross · 2019-04-17T14:21:44Z

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 · 2019-04-17T14:27:51Z

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).

Technically, you already have higher order functions in Go (Functions are first-class citizens and you can pass them along to other functions)
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 · 2019-04-17T14:40:12Z

Thank you @DylanMeeus for your thoughts.

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.

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 · 2019-04-17T15:04:10Z

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 · 2019-04-17T15:09:00Z

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:

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

bradfitz · 2019-04-17T16:47:42Z

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

fluxynet · 2019-04-17T18:11:34Z

@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 · 2019-05-14T21:35:40Z

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.

gopherbot added this to the Proposal milestone Apr 17, 2019

gopherbot added the Proposal label Apr 17, 2019

fluxynet changed the title ~~proposal: Go 2: Higher Order Functions~~ proposal: Go 2: Higher Order Collection Functions Apr 17, 2019

bradfitz added the Proposal-Hold label Apr 17, 2019

gopherbot added the v2 A language change or incompatible library change label Apr 17, 2019

ianlancetaylor added the LanguageChange label Apr 17, 2019

ianlancetaylor closed this as completed May 14, 2019

BingBlog mentioned this issue May 8, 2020

Go Collection Functions BingBlog/good-good-study#6

Open

golang locked and limited conversation to collaborators Nov 20, 2020

gopherbot added the FrozenDueToAge label Nov 20, 2020

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

proposal: Go 2: Higher Order Collection Functions #31513

proposal: Go 2: Higher Order Collection Functions #31513

fluxynet commented Apr 17, 2019

xeoncross commented Apr 17, 2019 •

edited

DylanMeeus commented Apr 17, 2019 •

edited

fluxynet commented Apr 17, 2019 •

edited

DylanMeeus commented Apr 17, 2019

fluxynet commented Apr 17, 2019

bradfitz commented Apr 17, 2019

fluxynet commented Apr 17, 2019 •

edited

ianlancetaylor commented May 14, 2019

proposal: Go 2: Higher Order Collection Functions #31513

proposal: Go 2: Higher Order Collection Functions #31513

Comments

fluxynet commented Apr 17, 2019

map

reduce

filter

find

findIndex

each

xeoncross commented Apr 17, 2019 • edited

DylanMeeus commented Apr 17, 2019 • edited

fluxynet commented Apr 17, 2019 • edited

DylanMeeus commented Apr 17, 2019

fluxynet commented Apr 17, 2019

bradfitz commented Apr 17, 2019

fluxynet commented Apr 17, 2019 • edited

ianlancetaylor commented May 14, 2019

xeoncross commented Apr 17, 2019 •

edited

DylanMeeus commented Apr 17, 2019 •

edited

fluxynet commented Apr 17, 2019 •

edited

fluxynet commented Apr 17, 2019 •

edited