he_the_great (he_the_great) wrote,
he_the_great
he_the_great

Sorting Time in Go

A while back I was having a discussion about Go on Reddit. I don't program in Go so I had to come up with a task so that I could come to grasp what Go offered for polymorphic functions. Let me relay that information.

The task is simply to sort Time. It is something I've done in D and frankly expected I'd have to "fake" having a hard time, but luckily Go didn't make it any easier for me (to the best of my knowledge). In fact I find the sort package is full of great examples demonstrating Go's polymorphic problems.

golang
package main

import "fmt"
import "time"
import "sort"

// Define us a type so we can sort it
type TimeSlice []time.Time

func main() {
    // Create slice of two times
    events := make([]time.Time, 2)
    // 4:30AM
    events[0], _ = time.Parse("15:04""04:30")
    // 3:12PM
    events[1], _ = time.Parse("15:04""15:12")
    // Wrap array in type for sorting
    sort.Sort(TimeSlice(events))
    
    fmt.Println(events)
}

// Forward request for length
func (p TimeSlice) Len() int {
    return len(p) }

// Define compare
func (p TimeSlice) Less(i, j int) bool {
    return p[i].Before(p[j]) }

// Define swap over an array
func (p TimeSlice) Swap(i, j int) {
    p[i], p[j] = p[j], p[i] }

Starting from the beginning it is required to define a type which is a slice of Time. I've chosen to call it TimeSlice. At this point, I can't figure out why it is required. I would have expected just using the normal []time.Time would be fine... but maybe that doesn't work with the magic Interface{} type.

golang
    // Create slice of two times
    events := make([]time.Time, 2)

I found it interesting that a built-in function takes a type. It makes me wonder if one could make there own functions which operate on types... but it's Go, so doubtful.

golang
    // 4:30AM
    events[0], _ = time.Parse("15:04""04:30")
    // 3:12PM
    events[1], _ = time.Parse("15:04""15:12")
    // Wrap array in type for sorting
    sort.Sort(TimeSlice(events))

Nothing unusual about the date parse or the request for sorting a TimeSlice. To make a sortable TimeSlice I need three functions, Len, Swap, and Less. None of which are provided for my new type.

golang
func (p TimeSlice) Len() int {
    return len(p) }

Len is a fairly simple function, it just calls len and forwards the answer.

golang
func (p TimeSlice) Less(i, j int) bool {
    return p[i].Before(p[j]) }

The Less function isn't too bad, I just need to access the two elements and compare them, I've chosen the Before function in this case, but I can define it to be anything.

golang
func (p TimeSlice) Swap(i, j int) {
    p[i], p[j] = p[j], p[i] }

The Swap function isn't quite as simple as the others. One must be familiar with Go and understand the order of evaluation which this expression will follow. Or you can do what I did and copy it out of source code in the sort package and trust that the Go authors know what they are doing.

Copy Paste

You heard what I said. I did a copy and paste from the official standard library package. That is how I started with all three functions, the main changes was use making it take TimeSlice rather than IntSlice. The second biggest change was Less needed to use a function rather than <.

Now I was going to do that anyway just to get an understanding of what it was like to create a polymorphic function. What I wasn't expecting to find was a complete lack of these functions for time.Time. The time package doesn't define any sorting helpers.

Update: See comments for reference to SortWrapper which addresses this issue.

Sort Strategy

The sort strategy is pretty nice, since time doesn't have a provided sort, I can make the Less function do what I want. For example I can sort by After. There are many times a default sort is insufficient to the goals of the program.

What about sorting a TimeSlice in a couple different ways? I may need to give the user choice over how they desire to sort the data so I'll want a couple strategies available. To achieve this I'd have to define TimeSliceBefore, TimeSliceAfter, TimeSliceInbetween because I've already defined Less for TimeSlice. This means implementing 3 * 3 functions (5 right? only 5). Ok, it isn't that bad, I can setup my build to run cpp across my source first.

Update: Read comment section for proper implementation of these types (don't need swap or len each time)

IntSlice

Yes, IntSlice, Float64Slice, StringSlice. These are all provided by the sort package for your convenience. And if that isn't enough, they have the sort functions (e.g. ints()) which provides the ability to sort a slice without wrapping it in IntSlice first.

I can only imagine that sorting is not very common (at least not outside of, int, float, and string). I see this as something very discouraging, it makes the toy examples and probably much work straight forward. Then step outside of that comfort zone and you're hit with building everything yourself

Conclusion

Go does provide means for polymorphic functions. Functions can be written to operate on a number of different types and still provide type safety. I will get compile time errors if TimeSlice is missing a required function.

Go has absolutely no form of generics, it can't understand how to navigate a slice without also knowing the type inside the slice. And Go does not provide built-in Len/Less/Swap functions for slices.

I think this example is one which demonstrates why this is such a big problem in Go. Sorting is such a common operation, it can happen in many forms. I would expect there to be quit a bit of duplicate "helper" sort functions out there. Even C provides a function which can walk an array and sort it ignoring the type and using a compare function.

"We don't feel an urgency for them, although we understand some programmers do." -- FAQ

Tags: golang, programming
Subscribe

  • UI Automation by Mocking

    The testing pyramid is a popular communication tool to show where the quantity of testing should occur. Some people have to complain about the…

  • When is it OK to Find a Bug

    "How many times have you seen an email praising the heroic efforts of the developer who fixed some last-minute major issues in a huge new feature…

  • Full Registration

    One thing I've come to realize in software testing is to never entertain the idea of a full regression. The idea behind a full regression is to…

  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 4 comments