Go Language: Monads in Standard Library

standardizing an idiomatic approach to iterators can now make dealing with large slices and maps much more efficient, this is a much better approach than introducing a streaming specific syntax.

These new function definitions are much more flexible that they might first look. I am writing wrappers around all the non-standard iterator like collection or streaming data access that I deal with daily and decided to share my solutions with you.

This is what the definitions of these functions look like.

The first one is for iterating over a stream of single return values. In Go this means slices and arrays.

The great thing is now you can define your own “Collection” types and provide an idiomatic iterator for them now.

// Seq is an iterator over sequences of individual values.
// When called as seq(yield), seq calls yield(v) for each value v in the sequence,
// stopping early if yield returns false.
// See the [iter] package documentation for more details.
type Seq[V any] func(yield func(V) bool)

The implementation of these seem to be confusing a lot of people. Some people think it is too complicated, some people think is it too simple.

I really want to say you are iterating over a list of items, but that is not correct, it might not be a list, so I will use the term sequence because that is the most semantically correct.

I think they reached a very good balance with minimal complexity for maximum functionality. Is this implementation as powerful as the iteration in functional languages. No, but it does 80% or more of what they do and pretty close to 100% of what the majority of people actually use day to day for minimal complexity.

Here is a non-contrived example that is short enough to be written inline if you need to generate a simple range of numbers. I put it in a function for some testing I was doing to generate data for more complex adapters and wrappers to use as contrived test data.

This does just what it says in the name of the function, it generates a sequence of ints from start to end inclusive.

func IntRange(start int, end int) iter.Seq[int] {
    return func(yield func(int) bool) {
        for i := start; i <= end; i++ {
            if !yield(i) {
                return
            }
        }
    }
}

// here is how you would use it
ints := seq.IntRange(0, 99)

for i := range ints { 
    fmt.Println("%d", i
}

The great thing about these new iterator functions is you do not have to allocate a bunch of memory to process sequences of data that is being dynamically generated. Whether that is from an algorithm or from some I/O operations it makes everything “look” the same in the code.

This way of iterating a sequence is considered a “Push” method. It is very much like .Each()/.ForEach() would be in other languages. The implementation is very much like generators in Python. They even share the yield keyword. There are similar in some ways and different in others.

The most important difference is that the Go implementation is a specific function definition, not just a keyword you can put in any function.

Monadish composition

The most powerful thing about this new feature is you can chain them in a very Monadish manner.

This function takes any thing with a .Stringer() interface and returns the value of .String() in a lazy generative manner. It only does the processing when it is required.

func ToString[T fmt.Stringer](it iter.Seq[T]) iter.Seq[string] {
    return func(yield func(string) bool) {
        for i := range it {
            if !yield(i.String()) {
                return
            }
        }
    }
}

This basically wraps another iter.Seq and transforms the data as it requested. You can chain like this to filter things out or add things in very clearly and concisely.

This is one of the most important things to know about these new functions. They were designed for composition. If you do not understand Monads and you can learn how these functions work, then you are actually about 90% of the way there.

Go is not a functional language, and as we know with the attempts to shoehorn functional programming paradigms where they do not fit; Java, JavaScript. Go is no exception, but these iterator functions do not feel forced or out of place. They fit naturally into the idiomatic code that you have been writing for the last ten years.

iter.Seq2

iter.Seq2 is the map-like iterator. It is not limited to maps and is not even specifically tied to the map[] type. If you read the source, the two values it returns are labeled K,V but the k type is any and not restricted to comparable like map[] would limit keys.

Therefore you can use it to iterator over sequences and expose their unique ids as the K and the actual item in the list as the V. There is a good argument to make that iter.Seq2 could be more useful in almost every case where you are dealing with a sequence of Entity type data (data that has an identity). iter.Seq would still be the best semantic choice for sequences of scalar/value objects.

In this next example I create a iter.Pull wrapper around an inline iter.Seq that simply generates an integer one more than the last one. Do not worry about the iter.Pull I will explain it next, it is very simple to understand.

Then I pass that as a function to seq.SeqtoSeq2 to use as a key generator for the values from ints.

    func SeqToSeq2[K any, V any](is iter.Seq[V], keyFunc func(v V) K) iter.Seq2[K, V] {
        return iter.Seq2[K, V](func(yield func(K, V) bool) {
            for v := range is {
                k := keyFunc(v)
                if !yield(k, v) {
                    return
                }
            }
        })
    }

    // key generator sequence
    next, stop := iter.Pull(func(start int) iter.Seq[int] {
        index := start
        return iter.Seq[int](func(yield func(int) bool) {
            for {
                if !yield(index) {
                    return
                }
                index++
            }
        })
    }(0)) // creates an infinitely increating counter generator

    ints := seq.IntRange(0, 99)

    intMap := seq.SeqToSeq2[int, int](ints, func(v int) int {
        k, ok := next()
        if !ok {
            stop()
            return -1
        }
        return k
    })

Now I can get the index of each item in ints as a key with iter.Seq2 and the indexes are generated as they are needed and the stop() discards the key generator sequence when the wrapped sequence is done. No intermediate slices or array buffers are generated during this conversion.

iter.Pull

iter.Pull is the inverse iterator paradigm of iter.Seq. iter.Seq is called a push iterator. It pushes you the next value of the sequence during the iteration loop.

iter.Pull is obviously a pull iterator, or the opposite of push. You have to ask for the next() value when you want it and you have to test for the end of the sequence by looking at the value of ok and ending the iteration when ok is false.

In the above key generator sequence you could not do an infinite series of data without resorting to making the code much more complex with goroutines and channels to manage the key generator function and dispose of it when done with the data.

iter.Pull makes this very easy with the stop() function that it provides.

the push iterators are going to do the job for the majority of iteration needs. The pull iterators are there to cover the times that the push iterators just will not work.

Go team is sneaking Monadish behavior into the standard library

Comments

Go is Not

iter.Seq in practice

More from this blog

No more Load/Store use StorageLike

Use marker values instead of null or whatever your language calls a it!

iter.Seq in practice

ReST vs GraphQL an invalid comparison

Monadish composition

iter.Seq2

iter.Pull

Command Palette

Comments

Go is Not

iter.Seq in practice

More from this blog

Monadish composition

iter.Seq2

iter.Pull