alekseevi15
Go4Fun - Fun Interview Puzzles

Go4Fun - Fun Interview Puzzles

Go for Functional Programming?

Go for Functional Programming?

alekseevi15's photo
alekseevi15
·Oct 4, 2022·

8 min read

Go is a powerful, fast, safe and simple language with some interesting distinctive features. And while Go is a multi-paradigm language, it was not designed to promote a functional-first programming model: the imperative style programming is by far the most dominant and idiomatic way of writing code in Go. Still, it could be interesting to see how far it's possible to use the language towards a more functional style.

But what is a functional programming in the first place? And how it is different from imperative programming? From Wikipedia:

Functional programming is a programming paradigm where programs are constructed by applying and composing functions. It is a declarative programming paradigm in which function definitions are trees of expressions that map values to other values, rather than a sequence of imperative statements which update the running state of the program.

Thus, one of the main prerequisites of functional programming support in a given language is treating functions as first-class citizens there: ability to assign functions to local variables, pass them around and return from other functions. And it's supported by Go, of course. That makes it possible to organize our code in a more declarative way (describing "what" we want to do), in contrast to a more imperative way ("how" we want to do it). For example:

Imperative:
seq := []int{1, 2, 3, 4, 5, 6, 7}
sum := 0
for _, e := range seq {
    if e%2 == 0 {
        sum = sum + e*2
    }
}
return sum
// 24
Functional:
seq := fun.Seq[int]{1, 2, 3, 4, 5, 6, 7}

sum := seq.Filter(func(e int) bool { return e%2 == 0 }).
    Map(func(e int) int { return e * 2 }).
    Reduce(func(e1, e2 int) int { return e1 + e2 })

return sum
// 24

Both are Go code snippets that produce the same output. The first one is a more idiomatic imperative way to do it in Go. The second one is a more functional way using common higher-order functions (functions taking other functions as arguments) provided by a functional programming library I created Go4Fun.

It's a bit unfortunate that Go doesn't support a short lambda syntax present in many other modern programming languages, that would allow the code to look like that, for example (that is not real Go code):

seq.Filter(e => e%2 == 0).
    Map(e => e * 2).
    Reduce((e1, e2) => e1 + e2)

There is an open Go 2 proposal to add support for a more lightweight anonymous function syntax (github.com/golang/go/issues/21498). At the moment, it looks like there is a standoff between "progressives" who want Go to have it and "conservatives" resisting the proposal (recommend to read, quite interesting).

Anyway, even without the short lambda syntax it's possible to write useful common generic functional programming types (Option, Future, Either...) and higher-order functions (Map, FlatMap, Filter, Fold, Reduce, Zip...).

Go support for higher-order functions allows to implement by hand other functional programming concepts not provided out of the box: currying and function composition.

Currying

Currying is the technique of converting a function that takes multiple arguments into a sequence of functions that each takes a single argument.

Currying of a function with 3 arguments could be implemented in Go like that:

func Curry3[A, B, C, D any](f func(A, B, C) D) func(A) func(B) func(C) D {
    return func(a A) func(B) func(C) D {
        return func(b B) func(C) D {
            return func(c C) D {
                return f(a, b, c)
            }
        }
    }
}

And then it can be used to curry a function f with 3 arguments:

f := func(a int, b bool, c string) string {
    return "(" + fmt.Sprint(a) + " " + fmt.Sprint(b) + " " + fmt.Sprint(c) + ")"
}

curriedF := Curry3(f)

// Calling the curried function with all 3 arguments:
curriedF(1)(true)("abc")

// Using the curried function (providing 2 arguments out of 3)
// with Map function (expecting 1 String argument in this case):
seq := Seq[string]{"abc", "def", "ghi"}
r := seq.Map(curriedF(1)(true))

return r
// [(1 true abc) (1 true def) (1 true ghi)]

Currying is a useful practical concept which benefits however might not be immediately obvious. Since many common higher-order functional programming functions (like Map) expect functions with 1 argument as a parameter, using Currying technique we can convert some multi-argument function into a sequence of 1-argument functions, thus making it compatible. Like in the example above: we have a function f which expects 3 arguments, but we are able to use it with Map by currying f first and then providing 2 arguments out of 3.

Function composition

Function composition is an operation that takes two functions f and g, and produces a function h such that h(x) = g(f(x)).

It could be implemented in Go like that:

func Compose2[A, B, C any](f func(A) B, g func(B) C) func(A) C {
   return func(a A) C { return g(f(a)) }
}

And then we can use it like that:

f := func(a int) bool { return a != 0 }
g := func(b bool) string { return fmt.Sprint(b) }

h := Compose2(f, g)

return h(1) == g(f(1))
// true

Function composition allows us to build more complex functions out of simpler ones. For a trivial example like the above, the benefit would clearly not outweigh the trouble, but the more functions, acting as building blocks, you have in your pipeline - the more obvious the benefit could become.

Apart from higher-order functions, currying and function composition, there are other features often associated with functional programming: closures, tail recursion optimization, immutable data types...

Closures

A closure is a function value that references variables from outside its body.

Obviously, it's supported by Go, for example:

func myfunc() func(int) int {
    s := 10
    return func(x int) int {
        return s + x
    }
}

In this case myfunc function returns a closure: a new function value "bound" to a local variable s of myfunc.

Tail recursion optimization

What is a tail recursion?

Tail recursion is a recursive function in which the recursive call is the last statement that is executed by the function.

In a traditional recursion often you perform your recursive call first, and then you take an output of the recursive call and calculate a result. This way you don't get a result of your calculation until you have returned from every recursive call.

In a tail recursion you perform your calculation first and after that you make a recursive call passing a result of your current step to the next recursive call.

For example, this function is not tail-recursive:

func factorial(n int) int {
   if n < 2 {
      return 1
   }
   return n * factorial(n - 1)
}

But this one is tail recursive:

func factorial(n, current int) int {
   if n < 2  {
      return current
   }
   return factorial(n - 1, n * current)
}

In many languages the latter case could be optimized automatically by the compiler or runtime to avoid stack frame growing (which otherwise could eventually lead to stack overflow crash). Often that is done by replacing a tail recursion with a traditional loop or by reusing a stack frame when calling the function in the tail position. In that case it's possible to get the best of 2 worlds: expressiveness of recursion, natural when implementing some algorithms, plus performance of traditional loops.

At the moment, the tail-call optimization is not supported by Go. There was a proposal which was closed after a long discussion: github.com/golang/go/issues/22624

Immutable data types

In object-oriented and functional programming, an immutable object is an object whose state cannot be modified after it is created.

Immutable objects provide a number of important benefits: they are easier to reason about (we know that they can't be updated unexpectedly by some other parts of the code, thus not requiring defensive copies), more thread-safe and (in some cases) could even improve runtime efficiency.

Many core built-in types in Go are naturally immutable: bool, int, string... But when talking about a language support for immutable data types, often a more general support for immutable composite data types is implied. E.g. slices, maps or structures that would get "frozen" after they are created: you can read them but could not update "in place", only by getting a copy of the object with an updated value. It might sound as a horribly inefficient exercise, however it depends on how underlying data structures are implemented - updated immutable instances could potentially reuse existing data nodes which could be very efficient, especially when creating copies of objects.

At the moment, there is no built-in support for immutable slices, maps or structures in Go, however a similar effect could often be achieved by e.g. exporting only read-only methods from the structure, without public access to the internal fields and mutating methods. That could be a bit verbose but still could do. There is a number of open Go 2 proposals on the immutability topic that could be interesting to read, like: github.com/golang/go/issues/27975

Conclusion

In this article we've scratched the surface of some functional programming concepts and their possible application in Go: imperative vs functional code, higher-order functions, currying, function composition, closures, tail recursion, immutable data types. Go is a practical language with simplicity being one of its the most cherished assets. And still it supports a decent number of features that make it possible to apply some practical functional programming techniques. If someone is interested to explore this topic in more depth and would like to join me in this adventure, I would be happy to see you on GitHub (github.com/ialekseev/go4fun). We can play together :) Thanks for reading!

 
Share this