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

fold
reduce

(Matthew Johnson) #34

Right, but that ignores the fact that I brought up Monoid because it is actually a sub-optimal solution in many cases, including the motivating examples.

One of the unfortunate aspects of the SE community is the desire to always push off related topics to independent threads. This prevents us from stepping back and looking a the motivating problem more holistically. IMO, this proposal cannot be evaluated well without considering alternative ways to solve the motivating problems, including Monoid.

I agree with others that if we include a fold that is not based on Monoid it should not trap and should return optional. However, I don't think it makes sense to include such a method unless there are sufficiently many use cases that cannot be addressed well with Monoid. If you want to continue proposing an Optional-returning fold I recommend looking for use cases other than monoid-style value combining (it might help to look for semigroups that are not also monoids).


#35

Touche, but Monoid costs too much for what it’s really worth.

It’s structure is rigid; adding another monoid incurs a non-trivial amount of boilerplate.
You argued that it shouldn’t need many more custom ones, but that means we’re reducing boilerplate codes by putting boilerplate codes in the standard library. That’s something I can’t sit very well with.

We’ve debated solely about Monoid for more than a third of the lifetime of this proposal, yet not going anywhere. I’m inclined to say that, from this thread’s perspective, we’ve already considered Monoid at this point. Though it’s hard to say when only a few people are in the discussion.


(Matthew Johnson) #36

Abstractions are defined once and used many times. Given that combining values is one of the most pervasive operations in programming, I think explicitly modeling combining operations is a good thing to do. Fortunately for you, I don't get to decide what makes it into the standard library and what doesn't! :slight_smile:

This thread has mostly consisted of opinions without strong arguments that clearly evaluate the tradeoffs. I wish we would see more of that kind of objective analysis on SE. People can reasonably have different opinions about what tradeoffs we should make, but it should be possible to at least try to agree on what the tradeoffs are before a decision is made.


#37

This does look too much like something you can do with

let ageSum1 = people.map { $0.vitae.age } .reduce(0, +)

which to me seems like a more versatile option with about the same mental model.


(Peter Tomaselli) #38

A question I wanted to ask before things moved too far downthread…

I’m curious to know more about what this means, or if you could provide some examples! :slight_smile:


#39

You can write some fun functions around this and reuse existing machinery.

func get<Root, Value>(_ kp: KeyPath<Root, Value>) -> (Root) -> Value {
  return { root in
    root[keyPath: kp]
  }
}

func combining<Root, Value>(
  _ f: @escaping (Root) -> Value,
  by g: @escaping (Value, Value) -> Value
  )
  -> (Value, Root)
  -> Value {

    return { value, root in
      g(value, f(root))
    }
}

And with those defined, your example becomes:

people.reduce(0, combining(get(\.vitae.age), by: +))

As a sidebar, the (A, A) -> Bool shape also shows up in a bunch of generic algorithms (sorted, min, max), so the their function can be pretty handy:

func their<Root, Value>(
  _ f: @escaping (Root) -> Value,
  _ g: @escaping (Value, Value) -> Bool
  )
  -> (Root, Root) -> Bool {
    return { g(f($0), f($1)) }
}

people.sorted(by: their(get(\.name), <))

And with the obvious Comparable overload:

func their<Root, Value: Comparable>(
  _ f: @escaping (Root) -> Value
  )
  -> (Root, Root) -> Bool {
    return their(f, <)
}

people.sorted(by: their(get(\.name)))

I'm also a fan of defining the prefix ^ operator to simplify the noise of get while we wait for more seamless key-path integration :slight_smile:

prefix operator ^
prefix func ^ <Root, Value>(_ kp: KeyPath<Root, Value>) -> (Root) -> Value {
  return get(kp)
}

Which makes the earlier examples read quite lovely!

people.reduce(0, combining(^\.vitae.age, by: +))
people.sorted(by: their(^\.name))

#40

I’m referring to this:

extension Sequence {
    @warn_unqualified_access
    public func min(
        by areInIncreasingOrder: (Element, Element) throws -> Bool
    ) rethrows -> Element?

    @warn_unqualified_access
    public func max(
        by areInIncreasingOrder: (Element, Element) throws -> Bool
    ) rethrows -> Element?
}

extension Sequence where Element: Comparable {
    @warn_unqualified_access
    public func min() -> Element?

    @warn_unqualified_access
    public func min() -> Element?
}

They’re defined here.

You can use it like this:

[1, 2, 3, 4].min(<) // Optional(1)
[Int].min(<) // nil
[1,2,3,4].min() // Optional(1); Another implementations when Element is Comparable

This saves me a lot of time since I can skip a lot of logic when I have empty data and they do remind me to check if that’s the case.


(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


Why doesn't "reduce(into:)" include a variant that takes an "inout" input?