Imperative methods

[raviqqe]

Problem

• We currently use a functional style for all the interfaces of persistent data structures.
  • This is primarily the easiness of writing programs in a functional style.
• We implicitly use option types and take references of keys and values through pointer references in methods of persistent data structures.
• It's not optimal for performance.
  • e.g. We can't know if entries are inserted/removed or not at the same time!
  • Go is primarily a system programming language but not a functional programming language!
• The interface will be inconsistent with methods providing destructive updates, which might be implemented in the future.
  • e.g. HashMap::insert() | im

Examples

func (m Map[K, V]) Find(k K) *V {
  ...
}

func (m Map[K, V]) Insert(k K, v V) Map[K, V] {
  ...
}

Solution

• Migrate to imperative interfaces of persistent data structures.
  • An implementation is in Indicate absence with a boolean return, instead of nil pointers #25.

Examples

func (m Map[K, V]) Find(k K) (V, bool) {
  ...
}

func (m Map[K, V]) Insert(k K, v V) (Map[K, V], bool) {
  ...
}

References

• The original discussion is in Update the package to use generics #16.
• im, which is probably the most popular persistent data structure library in Rust adopts imperative interfaces for their implementations.
  • I guess it's because Rust users usually care more about performance than easiness in programming.