Min operation on Coins

[JimLarson]

Summary

Incorporate a new Coins method: func (c Coins) Min(other Coins) Coins for utility and consistency.

Problem Definition

When working with Coins, it's sometimes useful to compute the minimum of two values, defined as the minimum of each denom, but there's no existing library method for it.

Example: toTransfer := want.Min(spendable) Example: to compute max(a.Sub(b), zeroCoin) without panicking, compute a.Sub(a.Min(b))

With IsAllLTE() defining a partial order on Coins, Min() becomes the "meet" operator of a lattice, tying the operations into centuries of mathematical precedent.

Proposal

Implement func (c Coins) Min(other Coins) Coins with tests and documentation for its properties.

Max() should be added for symmetry, with the property that a.Add(b) == (a.Max(b)).Add(a.Min(b)), so it could be defined as

func (c Coins) Max(other Coins) Coins {
    return c.Add(other).Sub(c.Min(other))
}

Where 0 is the empty Coins value, <= is IsAllLTE(), and == is a non-panicking variant of IsEqual(), for arbitrary Coins values a, b, and c, we have the properties:

• <= is a partial order:
  • Reflexivity: a <= a
  • Antisymmetry: a <= b && b <= a imply a == b
  • Transitivity: a <= b && b <= c imply a <= c
• Min() is the greatest lower bound ("meet") with respect to this order, and Max() is the least upper bound ("join"):
  • a <= b if and only if a.min(b) == a && a.max(b) == b
• Min() and Max() are commutative and associative
• Absorption laws:
  • a.Max(a.Min(b)) == a
  • a.Min(a.Max(b)) == a
• Distributivity:
  • a.Max(b.Min(c)) == a.Max(b).Min(a.Max(c))
  • a.Min(b.Max(c)) == a.Min(b).Max(a.Min(c))
• 0 is the bottom element
  • 0.Min(a) == 0
  • 0.Max(a) == a

---

For Admin Use

• [ ] Not duplicate issue
• [ ] Appropriate labels applied
• [ ] Appropriate contributors tagged
• [ ] Contributor assigned/self-assigned

[ValarDragon]

This is a great idea imo, just will need a clear comment so people realize that the following can pass:

c := A.Min(B)
assert c != A && c != B

Perhaps this can be done by calling it "MinSet" or something? (Surely theres some standard naming for taking the entry-wise minimum of two lists)

Feel free to tag me as a reviewer for such a PR

[JimLarson]

The literature seems to call this "multiset intersection" or "bag intersection", or "infemum" or "greatest common divisor". See wikipedia entry.

I can definitely document it clearly. For a name, let me see how it looks in context. Briefer seems better. So far, Min() seems the most intuitive, but maybe Inf() is just as good?

[ValarDragon]

Oh can we call it intersection?

If we prefer a 3-4 letter name, then Min also SGTM

[JimLarson]

If we call this Intersection(), we'd want to rename IsAllGTE() to Contains() to be consistent. :-) But I think we'll want to stick with an "ordering" theme rather than a "set theory" theme. The latter is technically correct, but I don't think it's how we think about Coins.

I'll try to find some places to use this in the codebase, so seeing the uses in context will help with the naming discussion.

[ValarDragon]

Ok that sounds good to me! I'm down for Min under this framing. (Using an ordering interpretation rather than a set theory one)

I don't think theres harm in duplicate functions for both SetTheory naming + normal naming, but we can easily make that a separate issue after Min() is in

[JimLarson]

@ValarDragon I've tagged you on #11200 which is in draft form, per CONTRIBUTING.md. Please advise on next steps.

[JimLarson]

Note that sdk.DecCoins has an Intersect() call with the same semantics as Min(). I'll add it as another name for Min().

[JimLarson]

See #11223 for other changes which could make Coins and DecCoins more consistent.