Golang Release 1.21: slices - Part 1

- 10 minutes read - 1933 words
🍺 Support my Blogging work

New package in Go standard library that makes easier to work with slices.

As part of the new Go release, several exciting changes have been introduced to the Go ecosystem. While we’ve explored some of these changes in other articles about the maps package and the cmp package, there’s much more to discover beyond these two packages.

In this article, we’ll focus on the first part of the slices package, specifically its new search functionality. Like many other updates and newly introduced packages, this one is also built upon the foundation of generics, which were introduced in Go 1.18.

BinarySearch and BinarySearchFunc

Let’s start by exploring the first pair of functions designed for efficiently searching a target value within sorted slices. In this context, we’re referring to the well-known Binary Search algorithm, which is renowned as one of the most significant algorithms and is frequently used in coding interviews. Below, you’ll find the signatures of both of these functions:

BinarySearch function

func BinarySearch[S ~[]E, E cmp.Ordered](x S, target E) (int, bool)

BinarySearchFunc function

func BinarySearchFunc[S ~[]E, E, T any](x S, target T, cmp func(E, T) int) (int, bool)

Looking at the signatures of both functions, we can identify some small differences between them, and these differences serve specific purposes. The first function, BinarySearch, expects two arguments. The first argument should be a slice of sorted items, and it must adhere to the Ordered constraint. When the items are ordered, the algorithm can efficiently compare them using the Compare function from the cmp package.

On the other hand, the second function, BinarySearchFunc, is more versatile. It allows searching within slices where the items don’t necessarily conform to the Ordered constraint. This flexibility is achieved by introducing a third argument, the comparison function. This function is responsible for comparing items and determining their order. It will be called by the BinarySearchFunc itself to make comparisons.

Both functions return two values. The first value is the index of the item within the slice, and the second is a boolean value indicating whether the item was found in the slice or not. Let’s explore some examples below:

BinarySearch examples

fmt.Println(slices.BinarySearch([]int{1, 3, 5, 6, 7}, 5))
// Output:
// 2 true
fmt.Println(slices.BinarySearch([]int{1, 3, 5, 6, 7}, 9))
// Output:
// 5 false
fmt.Println(slices.BinarySearch([]int{1, 3, 5, 6, 7}, -5))
// Output:
// 0 false

fmt.Println(slices.BinarySearch([]string{"1", "3", "5", "6", "7"}, "5"))
// Output:
// 2 true
fmt.Println(slices.BinarySearch([]string{"1", "3", "5", "6", "7", "8"}, "9"))
// Output:
// 6 false
fmt.Println(slices.BinarySearch([]string{"1", "3", "5", "6", "7"}, "4"))
// Output:
// 2 false

Take a close look at the results returned by the BinarySearch function, especially when the item doesn’t exist in the slice. In our examples, we encountered four such cases where the function returned 0, 2, 5, and 6. When the requested item isn’t present in the slice, the function indicates where it should be positioned if it were to be added to the slice. Since the slice is sorted, it’s possible to determine the appropriate position for the item within the slice.

Here’s how it works:

  • If the target item is less than all other items in the slice, it should be placed at index 0.
  • If the target item is greater than all other items, it should be positioned at the end of the slice, which falls outside the index range of the current slice.
  • Otherwise, the function calculates the suitable position for the item within the slice.

Now, let’s explore the cases for the other function, BinarySearchFunc.

BinarySearchFunc examples

fmt.Println(slices.BinarySearchFunc([]int{1, 3, 5, 6, 7}, 5, cmp.Compare[int]))
// Output:
// 2 true
fmt.Println(slices.BinarySearchFunc([]int{1, 3, 5, 6, 7}, 9, cmp.Compare[int]))
// Output:
// 5 false
fmt.Println(slices.BinarySearchFunc([]int{1, 3, 5, 6, 7}, -5, cmp.Compare[int]))
// Output:
// 0 false

fmt.Println(slices.BinarySearchFunc([]string{"1", "3", "5", "6", "7"}, "5", cmp.Compare[string]))
// Output:
// 2 true
fmt.Println(slices.BinarySearchFunc([]string{"1", "3", "5", "6", "7", "8"}, "9", cmp.Compare[string]))
// Output:
// 6 false
fmt.Println(slices.BinarySearchFunc([]string{"1", "3", "5", "6", "7"}, "4", cmp.Compare[string]))
// Output:
// 2 false

Here, we have simple examples using BinarySearchFunc, where we employed the same test cases as with the BinarySearch function. However, this time, we had to provide a comparison function as an argument. In this case, we utilized the Compare function from Go’s Standard Library.

But what’s the real purpose of BinarySearchFunc then? Let’s explore the example below to understand its significance.

BinarySearchFunc complex example

type Exam struct {
    Content string
    Mark    int
}

fmt.Println(slices.BinarySearchFunc([]Exam{
    {
        Content: "First",
        Mark:    1,
    },
    {
        Content: "Second",
        Mark:    1,
    },
    {
        Content: "Third",
        Mark:    2,
    },
    {
        Content: "Fourth",
        Mark:    3,
    },
}, Exam{
    Content: "Third",
    Mark:    2,
}, func(exam1 Exam, exam2 Exam) int {
    compare := cmp.Compare(exam1.Mark, exam2.Mark)
    if compare == 0 {
        return cmp.Compare(exam1.Content, exam2.Content)
    }
    return compare
}))
// Output:
// 2 true

In this example, we can see the true significance of BinarySearchFunc. If we intend to search for an element in a slice that doesn’t consist of items of type Ordered, as in this case with a simple struct Exam, then we should use this method. We can define our own comparison function to adapt the provided binary search solution to handle our specific situation.

Min and MinFunc

Now, let’s discuss something that we can easily understand just from the function names. Yes, we are talking about the functions Min and MinFunc. We have already discussed the built-in min and max functions, and the functions in the slices package heavily rely on them. But before we dive into further explanation, let’s take a look at their signatures:

Min functions

func Min[S ~[]E, E cmp.Ordered](x S) E

MinFunc functions

func MinFunc[S ~[]E, E any](x S, cmp func(a, b E) int) E

The purpose of both new functions is to find the minimum value in the slice provided as an argument to the function. In the case of the Min function, the slice must contain items of the Ordered type, while in the case of the MinFunc, there is no such requirement, but we must provide a comparison function as a second argument.

Example of Min function

fmt.Println(slices.Min([]int{1, 3, 9, 2, -1, 5, 7}))
// Output:
// -1
fmt.Println(slices.Min([]string{"bac", "aaa", "a", "cccc"}))
// Output:
// a
fmt.Println(slices.Min([]float64{1, 1, 1}))
// Output:
// 1
fmt.Println(slices.Min([]int{}))
// Output:
// panic: slices.Min: empty list

Example of MinFunc function

fmt.Println(slices.MinFunc([]int{1, 3, 9, 2, -1, 5, 7}, cmp.Compare[int]))
// Output:
// -1
fmt.Println(slices.MinFunc([]string{"bac", "aaa", "a", "cccc"}, cmp.Compare[string]))
// Output:
// a
fmt.Println(slices.MinFunc([]float64{1, 1, 1}, cmp.Compare[float64]))
// Output:
// 1

type Exam struct {
    Content string
    Mark    int
}

fmt.Println(slices.MinFunc([]Exam{
    {
        Content: "First",
        Mark:    1,
    },
    {
        Content: "Second",
        Mark:    1,
    },
    {
        Content: "Third",
        Mark:    2,
    },
    {
        Content: "Fourth",
        Mark:    3,
    },
}, func(exam1 Exam, exam2 Exam) int {
    compare := cmp.Compare(exam1.Mark, exam2.Mark)
    if compare == 0 {
        return cmp.Compare(exam1.Content, exam2.Content)
    }
    return compare
}))
// Output:
// {First 1}

In the provided examples, we can see that both functions work as expected. Min works fine with all types that are of the Ordered type, and for other types, we should use MinFunc. One important note for these two methods is that both expect to receive a slice with at least one element as an argument. In case that doesn’t happen, both functions will panic, so make sure to handle this use case in your code.

Max and MaxFunc

I’ll keep this section as brief as possible since this new pair of functions is a continuation of the previous pair. So, let’s take a look at them:

Max functions

func Max[S ~[]E, E cmp.Ordered](x S) E

MaxFunc functions

func MaxFunc[S ~[]E, E any](x S, cmp func(a, b E) int) E

And followed immediately with some examples:

Example of Min function

fmt.Println(slices.Max([]int{1, 3, 9, 2, -1, 5, 7}))
// Output:
// 9
fmt.Println(slices.Max([]string{"bac", "aaa", "a", "cccc"}))
// Output:
// cccc
fmt.Println(slices.Max([]float64{1, 1, 1}))
// Output:
// 1
fmt.Println(slices.Max([]int{}))
// Output:
// panic: slices.Max: empty list

Example of MinFunc function

fmt.Println(slices.MaxFunc([]int{1, 3, 9, 2, -1, 5, 7}, cmp.Compare[int]))
// Output:
// -9
fmt.Println(slices.MaxFunc([]string{"bac", "aaa", "a", "cccc"}, cmp.Compare[string]))
// Output:
// cccc
fmt.Println(slices.MaxFunc([]float64{1, 1, 1}, cmp.Compare[float64]))
// Output:
// 1

type Exam struct {
    Content string
    Mark    int
}

fmt.Println(slices.MaxFunc([]Exam{
    {
        Content: "First",
        Mark:    1,
    },
    {
        Content: "Second",
        Mark:    1,
    },
    {
        Content: "Third",
        Mark:    2,
    },
    {
        Content: "Fourth",
        Mark:    3,
    },
}, func(exam1 Exam, exam2 Exam) int {
    compare := cmp.Compare(exam1.Mark, exam2.Mark)
    if compare == 0 {
        return cmp.Compare(exam1.Content, exam2.Content)
    }
    return compare
}))
// Output:
// {Fourth 3}

As in all previous examples, here too, the Max and MaxFunc combo follows the same approach. Both functions search for the maximum value in the provided slice, which must have at least one item; otherwise, both functions will panic. Similar to the previous example, MaxFunc provides support for searching for the maximum in slices whose elements are not of the type Ordered, but you should also provide the comparison function as an argument.

IsSorted and IsSortedFunc

Now, let’s discuss two slightly different functions: IsSorted and IsSortedFunc. Below, you can find their signatures:

IsSorted function

func IsSorted[S ~[]E, E cmp.Ordered](x S) bool

IsSortedFunc function

func IsSortedFunc[S ~[]E, E any](x S, cmp func(a, b E) int) bool

These two new functions check if the slices provided as arguments are sorted in ascending order. The only difference between them is that IsSorted, as in some previous examples, only works with slices of items that are of type Ordered, whereas the function IsSortedFunc accepts items of any type, but it is necessary that we provide our own comparison function as the second argument.

Examples with IsSorted function

fmt.Println(slices.IsSorted([]int{1, 2, 3, 5, 5, 7, 9}))
// Output:
// true
fmt.Println(slices.IsSorted([]int{1, 3, 9, 2, -1, 5, 7}))
// Output:
// false
fmt.Println(slices.IsSorted([]int{-1, 1, 2, 3, 5, 7, 9}))
// Output:
// true
fmt.Println(slices.IsSorted([]int{9, 7, 5, 3, 2, 1, -1}))
// Output:
// false
fmt.Println(slices.IsSorted([]int{}))
// Output:
// true
fmt.Println(slices.IsSorted([]int(nil)))
// Output:
// true

As we can observe, the IsSorted function returns a straightforward boolean value, indicating whether a slice is sorted in ascending order. It’s essential to handle empty slices as an edge case, where the function returns true. Therefore, this scenario should be appropriately addressed in the implementation. Similarly, we can utilize the IsSortedFunc function in a similar fashion:

Examples with IsSortedFunc function

fmt.Println(slices.IsSortedFunc([]int{1, 3, 9, 2, -1, 5, 7}, cmp.Compare[int]))
// Output:
// false
fmt.Println(slices.IsSortedFunc([]string{"1", "2", "3", "5", "7", "9"}, cmp.Compare[string]))
// Output:
// true

fmt.Println(slices.IsSortedFunc([]string{"9", "7", "5", "3", "2", "1"}, cmp.Compare[string]))
// Output:
// false
fmt.Println(slices.IsSortedFunc([]string{"9", "7", "5", "3", "2", "1"}, func(a, b string) int {
    return -1 * cmp.Compare(a, b)
}))
// Output:
// true

type Exam struct {
    Content string
    Mark    int
}

fmt.Println(slices.IsSortedFunc([]Exam{
    {
        Content: "First",
        Mark:    1,
    },
    {
        Content: "Second",
        Mark:    1,
    },
    {
        Content: "Third",
        Mark:    2,
    },
    {
        Content: "Fourth",
        Mark:    3,
    },
}, func(exam1 Exam, exam2 Exam) int {
    compare := cmp.Compare(exam1.Mark, exam2.Mark)
    if compare == 0 {
        return cmp.Compare(exam1.Content, exam2.Content)
    }
    return compare
}))
// Output:
// true

Just like in all the previous examples involving functions that require custom comparison logic, there are no surprises here. The IsSortedFunc function allows us to check if a slice is sorted, without any requirement for the items to be of type Ordered. It’s worth noting that we can effortlessly check if a slice is sorted in descending order by providing our custom comparison function, which returns opposite values compared to the Compare function.

Conclusion

New version of Golang, 1.21, delivered many new updates, affecting standard library as well. In this article we checked how some functions from slices packages work. Those new methods give us now possibility to easily check ordering of the items of any slice that we want.

Useful Resources

🍺 Support my Blogging work
comments powered by Disqus