Pitch: Reducing a sequence onto its own elements to simplify code and reduce errors

fold
reduce

(Peter Tomaselli) #41

Right. Sorry, what I mean is, for which other functions (besides min and max) would you find these semantics to be useful?


#42

I did some work with Network Calculus which uses min-plus algebra.

Briefly, min-plus algebra is a semiring equiped with + and min operations where each element is a function. The operation is performed elementwise on the functions.

Doing computation with any element in this algebra is quite wasteful and I’d rather skip it when possible.

All in all, even though both operations are monoidal, we usually pretend they’re semigroup and never use the identities.

It’s probably not your typical use case, but I think Swift is powerful in that it allows us to utilize simple mechanics in such a way,


#43

Yet another alternative would also be to provide folding function to sequence of other standard library elements: sum, product for Numeric; intersect, union for SetAlgebra; clamp for Range.

Pros:

  • It results in very simple call sites, providing great readability.
  • It should contain most of the common use cases.

Cons:

  • Extending this functionality would still be the same as before, by extending Sequence yourself.
  • It sits on slippery slope, one can easily argue to include other functions such as quarternion’s product, tensor/simd’s arithmatic (as of now, Numeric still inherits from ExpressibleByIntegerLiteral).
    • Future operations can easily forget this part of the language (much like how many newer Sequences doesn’t override underestimatedCount when better implementation is possible).

#44

While it is true that this works for Array, it is not correct for a general Sequence which may be single-pass. Specifically, the .dropFirst() call would in fact skip the second element entirely, if the earlier .first was a destructively consuming access.


(Ben Cohen) #45

While true, that’s not really relevant to the point about map.


(Jordan Rose) #46

I wasn't 100% sure about the nil return value until I realized you can optional-chain it with the default:

let sum = nums.reduce(+) ?? 0

And then I thought: "if you have to do this anyway in most circumstances, is this really worth adding another overload?" But I guess it's strictly more powerful than the existing reduce, since your default does not have to be an identity element.


(Erica Sadun) #47

min and max do the same. I imagine you'd do a check like you do with that:

guard let sum = seq.reduce(+) else { return }
// use sum

(Erica Sadun) #48

Now that the design feedback has died down (I have learned a lot, thank you all so much), I'd like to know whether this "simple, useful (if fairly low-priority) addition" to the standard library meet the barrier of moving forward in the evolution process.

Please share your thoughts and, if possible, review the latest update to the proposal. I am looking for a sufficient quorum of support or it shall join my heap of "well, that would have been nice" ideas.

Thank you


(Ryan Sobol) #49

I'd like to know whether this "simple, useful (if fairly low-priority) addition" to the standard library meet the barrier of moving forward in the evolution process.

Your desire to contribute and improve Swift is so inspiring. In general, what I personally would love to see in 2019 are more well thought out proposals that round out Swift’s existing FP abstractions. It feels like Swift is good on the Optional (i.e. Maybe) monad. But perhaps that’s just me...


(Francois Green) #50

+1
This would be a great addition and does simplify some cases I've encountered. I hope as Swift moves into being a general purpose language, more tools are added for manipulating data: We are not all algorithmists after all.


(Erik Little) #51

Yes please! Personally I'd like to see more simple, useful additions go through review.


(Peter Tomaselli) #52

It’s officially an overload (underload?) of reduce now right? The very top of the first post still says fold

I like it! The ?? examples are compelling, and apparently now that I’ve performed some functional hand-wringing in public my brain is satisfied. :laughing:

+1!


(Erica Sadun) #53

Adding an inout variation to enhance performance. There's little difference for most summing and products but a significant boost when accessing property fields: https://gist.github.com/erica/619ff306286219e7afaa715683786f56


(Matthew Johnson) #54

While I do think Monoid is something we should support eventually I don't have opposition to this more ad-hoc solution in principle. I can see how providing a default instead via ?? instead of having to provide a correct initial value could help some people avoid mistakes.

However, I see that you have changed the name to reduce. There are currently two overloads of reduce in the standard library and you are proposing adding two more. I am not as averse to overloads as some people are so I'm not opposed to this in principle either. But I think it's pretty clear based on past comments by the core team and standard library team that the size of overload sets in the standard library is not going to be too large so there is limited space for overloads of reduce.

If we're going to add another overload, my top priority would be the one taking an inout initial value that @stephencelis posted about earlier today. IMO, this is the most fundamental reduce primitive. All other variants can be written efficiently in terms of it while it cannot be written efficiently in terms of any of the others. If the argument against that overload (that "reassigning" uses of the existing into overload could be optimized to be equivalent) has turned out to not be true in practice then perhaps that overload should be revisited.

So I'm not opposed to this in principle but I don't want to see this proposal get in the way of possibility of accepting (in the future) APIs that I feel are more important. I'm not sure where that leaves me on your current design, but my impression is that 5 overloads of reduce is definitely more than will be accepted for the standard library.


(Erica Sadun) #55

While the inout variant is more performant for some applications, it's also harder to construct for many use-cases. I'd rather offer both.


(Matthew Johnson) #56

I would be fine with that. I'm just not sure the core team will accept both (I would be surprised if they do). :slight_smile:


(Erica Sadun) #57

To be fair, it doesn't look to the user like two APIs: list.reduce(+) and list.reduce(+=)


(Matthew Johnson) #58

Agree from a code standpoint, although they do appear independently in the documentation. (It would be interesting to see alternative approaches to documentation formatting that bundles “method families” together and presents them as conceptually the same operation with different options for usage)

However I don’t think this is the primary reason people have concerns people have about overload sets. I think the most important reason is that they can result in more confusing / less relevant error messages.


#59

I think inout reduce is quite weird when used in this manner. If the Element has reference semantic, it somehow infer that the first element is more significant compared to others


(Nicola Salmoria) #60

I think this addition would meet the bar of being widely useful and avoiding common mistakes.

I think it also meets the bar of being not trivial to implement correctly using the standard library methods: it is tempting to do it like

    if let first = first {
        dropFirst().reduce(first, +)
    }

but that works only for Collection, not for Sequence; and doing something similar for Sequence requires being careful to not lose the second element of a single-pass sequence.