This implementation is O(n^2). We could do it in O(n), but that would require a more elaborate setup including storage with O(1) lookup (which could be based on a compile-time hash). If we implement such storage for associative sequences, we could use it to optimize this.
We can't specify the signature right now, because the tag of the returned object depends on whether x < y or not. If we wanted to be mathematically correct, we should probably ask that if_(cond, x, y) returns a common data type of x and y, and then the behavior of min would follow naturally. However, I'm unsure whether this is desirable because that's a big requirement.