proposal: x/exp/xiter: add Max/Min/MinMax{Func}

[leaxoy]

Proposal Details

Proposed add below functions:

func Max[E cmp.Ordered](s Seq[E]) E // zero length seq panics, like slices.Max

func MaxFunc[E any](s Seq[E], f func(E, E) int) E

func Min[E cmp.Ordered](s Seq[E]) E

func MinFunc[E any](s Seq[E], f func(E, E) int) E

func MinMax[E cmp.Ordered](s Seq[E]) (E, E)

func MinMaxFunc[E any](s Seq[E], f func(E, E) int) (E, E)

[ianlancetaylor]

I assume these will panic on an empty sequence, similar to slices.Min.

[jimmyfrasche]

(I was surprised there wasn't a slices.MinMax{,Func}. Maybe that should be another proposal?)

This comment applies to #67457 and #67458 as well.

Sequences are sometimes safely resumable (will get the same results in the same order if you range over it again) but that's not a guaranteed property.

Maybe things like this could be handled in a slightly different manner. First have a general adapter:

func Tap[T any](iter.Seq[T], func(T) bool) iter.Seq[T]

(and likewise for Tap2)

Tap returns an identical sequence but taps in with an additional yield func called before the actual yield func. That let's you react to items into the input stream and record info on the go (and halt early if necessary, this is not strictly required but seems useful).

That way you could have something like

seq, info := collectMinMax(seq)
for v := range seq {
  //...
}
min, max := info.MinMax()

where collectMinMax is written in terms of Tap. This would also let you access the min/max so far in the loop body.

[jimmyfrasche]

Actually I suppose if it can stop the sequence early, that's identical to TakeWhile albeit using it in a way that's creative wrt to its name

[leaxoy]

Later I thought about it carefully, panic on empty sequence is unreasonable, because we can easily judge whether slice is empty or not, but there is no reasonable way to deal with sequences. In other words, it is difficult for users to avoid panic.

Therefore an extra bool is returned bool that indicating whether there is a maximum/minimum value.

So the signature can change to:

func Max[E cmp.Ordered](s Seq[E]) (E, bool)

func MaxFunc[E any](s Seq[E], f func(E, E) int ) (E, bool)

// So and Min/MinFunc/MinMax/MinMaxFunc.

[jimmyfrasche]

Here's a basic implementation of MinMax using TakeWhile to tap into the sequence:

func MinMax[T cmp.Ordered](s iter.Seq[T]) (*Stats[T], iter.Seq[T]) {
	stats := &Stats[T]{}
	return stats, xiter.TakeWhile(stats.record, s)
}

type Stats[T cmp.Ordered] struct {
	Ok       bool
	Min, Max T
}

func (s *Stats[T]) record(v T) bool {
	if s.Ok {
		s.Min, s.Max = min(s.Min, v), max(s.Max, v)
	} else {
		s.Ok, s.Min, s.Max = true, v, v
	}
	return true
}

[jimmyfrasche]

With #60274 it could be defined for 0-length sequences, and a bit more concisely, at the expense of no longer working on strings

func MinMax[T math.Ordered](s iter.Seq[T]) (*Stats[T], iter.Seq[T]) {
	stats := &Stats[T]{
		Min: math.Greatest[T](),
		Max: math.Least[T](),
	}
	return stats, xiter.TakeWhile(stats.record, s)
}

type Stats[T math.Ordered] struct {
	Min, Max T
}

func (s *Stats[T]) record(v T) bool {
	s.Min, s.Max = min(s.Min, v), max(s.Max, v)
	return true
}

[coady]

A downside to slices.{Min,Max}Func is that they require a ternary comparison function only to use it as a boolean. Presumably this was to match SortedFunc, but the use case isn't equivalent. There's never a need to negate/reverse the comparison function because the direction is already implied by Min or Max. A boolean function would be sufficiently general to implement either.

Conversely, if a ternary function is a requirement, then it could at least leverage that to gather all equal elements. Collecting ties is a common use case, and elegantly solves the empty/panic problem.

func SelectFunc[E any](s Seq[E], f func(E, E) bool) (E, bool) // cmp.Less == Min

func MinFunc[E any](s Seq[E], f func(E, E) int) []E
func MaxFunc[E any](s Seq[E], f func(E, E) int) []E

I think either of those would be an improvement of the choice in slices.