Implement a generic data list structure

As a coding challenge I was asked to provide a generic list implementation using a language of my choice and using only primitive types, avoiding the use of high level built-ins. I chose Go because I want to learn it and I know it can be useful to create an abstract, generic implementation.

The challenge request to implement at least 4 methods on the generic type:

  • Filter() –  returns a subset of the List satisfying an operation
  • Map() – returns the List objects’ map
  • Reverse() – reverse the ordering of the List objects
  • FoldLeft() – join the objects from left to right using a join character

As a bonus question I was asked to code unit tests for the aforementioned methods and give an explanation on how the implementation guarantees concurrent access on resources.

So here is my implementation: the type List has only one attribute, an array of type interface{}

type List struct {
    data []interface{}
}

Every type will be convertible to the interface{} type, but as Golang has strong types the conversion is not implicit and must be declared.

Reverse() will create a new array of interface{} to hold the reversed list

func (m *List) Reverse() *List {
    var ret []interface{}
    for i := 1; i <= len(m.data); i++ {
        ret = append(ret, m.data[len(m.data)-i])
    }
    return &List{
        data: ret,
    }
}

Map() returns the List elements’ array, so it can be accessed as a whole

func (m *List) Map() []interface{} {
    return m.data
}

This two function types will help define a custom operation to be used in Filter() and FoldLeft(): functions are types in Go and this enable a great level of abstraction.

type filterFn func(interface{}) interface{}
type foldFn func([]interface{}) interface{}

Filter() will use a filter function, without the need to define it (!), and return a portion of the List data array.

func (m *List) Filter(filter filterFn) *List {
    var ret []interface{}
    for d := range m.data {
        if data := filter(m.data[d]); data != nil {
            ret = append(ret, data)
        }
    }
    return &List{
        data: ret,
    }
}

FoldLeft() will use a fold function, again not yet defined, the return a single element made of the entire list.

func (m *List) FoldLeft(fold foldFn) *List {
    var ret []interface{}
    ret = append(ret, fold(m.data))
    return &List{
        data: ret,
    }
}

You can find all the code here, any comment is welcome on how to improve the abstraction or efficiency of the implementation.

The opportunity to dig into the language ability to abstract is a very helpful way to better understand the language itself, so this coding challenge was a great opportunity to learn a little bit more Go!