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

fold
reduce

(Erica Sadun) #1

Pitch: Introducing fold to reduce a sequence onto its own elements and eliminate common errors

Work in progress is at this gist. Please refer to the gist for the latest updates as this post and thread may be out of date.

Draft follows. Constructive feedback is greatly appreciated. Thank you in advance.

Reducing a sequence onto its own elements

Introduction

This proposal introduces sequence folding as an overload to Swift's reduce method. This design simplifies call sites and can eliminate common errors associated with reduce.

Swift-evolution thread: Pitch: Reducing a sequence onto its own elements to simplify code and reduce errors

Motivation

While Swift's reduce method plays an important role in functional coding, many calls to the method can be simplified by tweaking the API. This proposal introduces a folding operator that seeds itself from the elements passed to reduce, removing the need for an explicit value seed.

The Standard Library reduce method combines elements of a sequence by applying a closure:

public func reduce<Result>(
  _ initialResult: Result, 
  _ nextPartialResult: (Result, Self.Element) throws -> Result) rethrows 
  -> Result { ... }

reduce(:_,:_) is used to calculate sums and products, append strings together, search for maxima and minima, and so forth. The call site supplies a seed value (the initialResult) of an arbitrary generic Return type. Each subsequent partial result is built by applying the nextPartialResult closure to the previous result and the next element of the sequence. The reduce method returns after exhausting all elements in the sequence.

The proposed reduce(:_) overload omits the initial seed. It is seeded by the first element of the sequence if one exists. Otherwise it returns nil for empty sequences. Like reduce(:_,:_), it combines sequence elements with a closure:

public func reduce(
    _ nextPartialResult:
    (_ partialResult: Element, _ current: Element) throws -> Element) rethrows 
    -> Element?

The re-architected calls are simpler to read, although they necessarily bring sequence reduction into the Optional space. They eliminate the first argument and form a result from the sequence itself:

let sum: Int = intSequence.reduce(0, +)
let sum: Int? = intSequence.reduce(+)

let product: Int = intSequence.reduce(1, *)
let product: Int? = intSequence.reduce(*)

reduce(_:, _:)'s initial result seed uses a "magic value". It is supplied by the call site, and not the language or the Standard Library. Because of this, it can be technically brittle. As the following sections explore, that initial result can be the source of both semantic and seeding errors.

Semantic Errors

Most functional programmers treat reduce(_:_:) as a monoid-based folding operation. A monoid is an algebraic operation that combines two values to produce another value within the same domain. Each monoid declares an identity that leaves other values unchanged when called with its function.

For example, summing numbers has an identity of 0. Adding 0 to any number returns that number. Similarly, the product identity for numbers is 1, and the and identity for Boolean values is true. When constructing reduce, many Swift developers use the identity to seed the first argument:

let boolean: Bool = booleanSequence.reduce(true, { $0 && $1 })

While Swift's reduce(_:_:) method does not require monoids, it's common to use a monoid to populate reduce's two arguments: the algebraic identity as the initial result and its binary (Element, Element) -> Element function to calculate the next partial result.

The monoid approach ensures that any non-empty sequence can be reduced correctly. The initial value will not affect the operation. Essentially, this best practices approach to reduce(_:,_:) says: "use a first argument that has no effect on the final result." In doing so, it's worth considering eliminating this identity.

When following the monoid patter, any empty sequence returns its identity. The product of no numbers is 1, the the combination of no matrices is the identity matrix, and the greatest common divisor of no 0-based natural numbers is 0, and so forth. Removing that identity means approaching empty sequences in a different manner.

The design of reduce(:_) returns nil in the absense of sequence members rather than an identity. It does this for two reasons:

  • Some identities are not universal across Swift types, creating a bar to building generic implementations.
  • Some identities simply cannot be represented in Swift.

Generics and Identities

Swift previously decided that the minimum value of an empty integer array should not be Int.max, even though Int.max is the identity of the min function across Int. We know this because Swift has already adopted an optional approach in the Standard Library for no-element sequences of any Comparable elements, which may not support a min or max property:

/// - Returns: The sequence's minimum element. If the sequence has no
///   elements, returns `nil`.
public func min() -> Self.Element? // ...

Since extreme values are not guaranteed to be present for every Comparable type, the design of the min() and max() methods cannot produce an identity for every sequence fed to them. In the absense of identities, they return nil. Adding a requirement to support an extreme-reporting protocol (for example, Comparable & ExtremeReporting) would narrow the number of types serviced by these features to the detriment of the language.

reduce(:_) follows the no-identity pattern to provide a consistent alternative to reduce(:_:_) when processing empty sequences of any type. It always returns nil, indicating a missing value, instead of the default seed.

let minimumValue: Int = [99, 2, -55, 6]
  .reduce(.max) { $0 > $1 ? $1 : $0 } // -55

let minimumValue: Int? = [99, 2, -55, 6]
  .reduce({ $0 > $1 ? $1 : $0 }) // -55
  
let minimumValue: Int = []
  .reduce(.max) { $0 > $1 ? $1 : $0 } // Specific to `Int`

let minimumValue: T? = emptySequenceOfT
  .reduce({ $0 > $1 ? $1 : $0 }) // nil, regardless of `T`

Unrepresentable Identities

In some cases, it's simply not reasonable to represent an identity in Swift. For example, the intersection identity for sets is the complete set. Consider the following code. It returns a set of strings common to all the sets passed to it. No identity can be used here because a canonical set of all possible strings cannot be constructed within the Swift language. In this case, a solution can be modeled with reduce(_:) but not reduce(_:_:):

// This returns a set of common strings
// e.g., let stringSetSequence: [Set<String>] = 
//   [["now", "is", "the", "time"], ["today", "is", "the", "day"]]
// returns {"is", "the"}

// Not constructable with `reduce(_:_:)`
let result = stringSetSequence
    .reduce(WHAT_GOES_HERE?, { $0.intersection($1) })

// Constructable with `reduce(_:)`
let result = stringSetSequence
    .reduce({ $0.intersection($1) })

Absent an identity that can be specified within the language, there is no other option than to return nil, representing a missing value, which is what the reduce(_:) design does.

Seeding Errors

The first argument of result(_:_:) is prone to error. These initial result errors may be simple call-site typos. The coder may know the correct identity but misstate it in code. For example, they may replace one well-known identity with another, as is common when forming a product, or they may simply type the right identity incorrectly.

These scenarios are easily remedied with adequate tests. For example, [value].reduce(identity, f) should always equal value for values across the domain. Still, these errors are better avoided than fixed.

In other cases, a coder may populate the first argument with the wrong value, not knowing the right one. This is less easily resolved as the person writing the code may write incorrect or insufficient tests as a result of confirmation bias.

Using reduce(:_) eliminates both types of errors because there is no need to supply and validate an identity element in code.

Call-Site Typos

Magic values rely on proper recall and text entry and are a point of coding fragility. This fragility extends to well-known algebraic identities like 0 for addition and 1 for multiplication. In using reduce(:_,:_), a simple brain freeze may introduce errors when seeding the first argument, as shown in the example below. Converting from reduce(:_,:_) to reduce(:_) eliminates this class of errors from the call site:

// common typo
let product: Int = intSequence.reduce(0, *)

// always correct, no magic value
let product: Int? = intSequence.reduce(*)

//  another common typo
let minimumValue: Int = intSequence
  .reduce(.min) { $0 > $1 ? $1 : $0 }
  
// again correct, no constant substitution
let minimumValue: Int? = intSequence
  .reduce({ $0 > $1 ? $1 : $0 })

Incorrect Identities

Eliminating identities is an important benefit when using less common seeds. For example, you can build minimum bounding frames for rectangles using both reduce(:_,:_) and reduce(:_) but specifying the wrong reduce(:_,:_) seed introduces the following value error:

let frames = [
  CGRect(x: 10, y: 10, width: 50, height: 50),
  CGRect(x: 40, y: 80, width: 20, height: 30),
  CGRect(x: -5, y: 10, width: 10, height: 10),
]

frames.reduce(CGRect.zero, { $0.union($1) })
// (x: -5.0, y: 0.0, width: 65.0, height: 110.0), incorrect

frames.reduce(CGRect.null, { $0.union($1) })
// (x: -5.0, y: 10.0, width: 65.0, height: 100.0), correct

frames.reduce({ $0.union($1) })
// (x: -5.0, y: 10.0, width: 65.0, height: 100.0), correct

When the coder selects the more common .zero constant over the less well known .null, the .zero seed pulls the y bounds to 0.0, leaving ten extra points of space preceding the minimum frame. While CGRect.null returns the right results, reduce(:_) uses a simpler approach that cannot be affected by incorrectly chosen identities.

If the developer uses insufficient test cases that wrap the origin, they may not discover the error. Using reduce(:_) gets rid of these errors and removes any resposibility for representing the identity from code.

Detailed design

This design introduces an unseeded variation of reduce(:_,:_). This overload uses the first value of each sequence to form its initial partial result. If the sequence is empty, it returns nil.

While reduce uses a partial result generator with a potentially distinct return type f(Result, Element) -> Result, reduce(:_) constrains its results to the same type as the source element f(Element, Element) -> Element. This change is required as the seed value will always be the sequence element type should a first value exist and nil otherwise.

Although applications of reduce may return a type distinct from the sequence elements, this can often be broken down into (Element) -> Result and (Result, Result) -> Result steps. For example, let stringSum = stringSequence.reduce(0, { $0 + $1.count }) is essentially the same as stringSequence.map({ $0.count }).reduce(0, +).

The design of reduce(:_) uses an iterator to distinguish empty sequences from those with values.

Preliminary Implementation

import Foundation

extension Sequence {
  /// Combines the elements of the sequence using a closure, returning the
  /// result (or nil, for a no-element sequence).
  ///
  /// Use the `reduce(_:)` method to produce a combined value from a
  /// sequence. For example, you can return the sum or product of a
  /// sequence's elements or its minimum or maximum value.
  /// Each `nextPartialResult` closure is called sequentially, accumulating
  /// the value initialized to the first element of the sequence.
  /// This example shows how to find the sum of an array of numbers.
  ///
  ///     let numbers = [1, 2, 3, 4]
  ///     let numberSum = numbers.reduce({ x, y in
  ///         x + y
  ///     })
  ///     // numberSum == 10
  ///
  /// Alternatively:
  ///
  ///     let numberSum = numbers.reduce(+) // 10
  ///     let numberProduct = numbers.reduce(*) // 24
  ///
  /// When `numbers.reduce(_:)` is called, the following steps occur:
  ///
  /// 1. The partial result is initialized from the first sequence member,
  ///    returning nil for an empty sequence. The first number is 1.
  /// 2. The closure is called repeatedly with the current partial result and
  ///    each successive member of the sequence
  /// 3. When the sequence is exhausted, the method returns the last value
  ///    returned from the closure.
  ///
  /// If the sequence has no elements, `reduce` returns `nil`.
  ///
  /// If the sequence has one element, `reduce` returns that element.
  ///
  /// For example, `reduce` can combine elements to calculate the minimum
  /// bounds fitting a set of rectangles defined by an array of `CGRect`
  ///
  ///     let frames = [
  ///       CGRect(x: 10, y: 10, width: 50, height: 50),
  ///       CGRect(x: 40, y: 80, width: 20, height: 30),
  ///       CGRect(x: -5, y: 10, width: 10, height: 10),
  ///     ]
  ///
  ///     frames.reduce({ $0.union($1) })
  ///     // (x: -5.0, y: 10.0, width: 65.0, height: 100.0)

  ///
  /// - Parameters:
  ///   - nextPartialResult: A closure that combines an accumulating value and
  ///     an element of the sequence into a new accumulating value, to be used
  ///     in the next call of the `nextPartialResult` closure or returned to
  ///     the caller.
  ///   - partialResult: The accumulated value of the sequence, initialized as the 
  ///     first sequence member
  ///   - current: The next element of the sequence to combine into the partial result
  /// - Returns: The final accumulated value or if the sequence has
  ///   no elements, returns `nil`.
  ///
  /// - Complexity: O(*n*), where *n* is the length of the sequence.
  @inlineable
  public func reduce(
    _ nextPartialResult:
    (_ partialResult: Element, _ current: Element) throws -> Element) rethrows 
    -> Element? {
    var iterator = makeIterator()
    guard var accumulator = iterator.next() else {
      return nil
    }
    while let element = iterator.next() {
      accumulator = try nextPartialResult(accumulator, element)
    }
    return accumulator
  }
}

Precedent

This design follows the Standard Library precedent for sequence extremes (min, max) by returning nil when a sequence has no elements. This allows seedless calls that apply across many types without having to declare identities for each type and each operation.

Naming

This design overloads reduce to accept a single closure argument. Here is a quick overview of alternate naming options.

Generally speaking, a fold or reduce higher order function processes a data structure to build a return value. An unfold seeds a start value to generate a data structure.

Many languages include up to four styles of reduction: left to right with an initial value, right to left with an initial value, left to right without an initial value, and right to left without an initial value. Swift currently implements just one of these, the left-to-right reduce(:_,:_), which takes an initial value.

The name fold is a term of art, commonly interchanged with reduce in various languages. Other terms include accumulate, aggregate, compress, and inject. The names are used somewhat interchangably among languages, with a slight tendency towards fold for using an initial value and reduce without.

If the reduce feature were being designed today, this proposal would recommend fold over reduce, and prefer overloading fold for both applications. As reduce already exists, it overloads the existing method.

Language Fold with Initial Value Fold without Initial Value
C# 3.0 Aggregate Aggregate
C++ accumulate
CFML, Clojure, CLisp, D, Java 8+, Perl, Python reduce reduce
Elm, Erlang, Standard ML foldl, foldr
F# fold, foldBack reduce, reduceBack
Gosu fold, reduce
Groovy inject inject
Haxe, Rust fold
JavaScript reduce, reduceRight reduce, reduceRight
Kotlin fold, foldRight reduce, reduceRight
Logtalk, OCaml fold_left, fold_right
Oz FoldL, FoldR
PHP array_reduce array_reduce
R Reduce Reduce
Ruby inject, reduce inject, reduce
Scala foldLeft, foldRight reduceLeft, reduceRight
Scheme fold-left, fold-right reduce-left, reduce-right
Haskell foldl, fold foldl1, foldr1
Xtend fold reduce

Source compatibility

This change is purely additive.

Effect on ABI stability

N/A

Effect on API resilience

N/A

Alternatives considered

  • The forum thread discussed introducing monoids either as a protocol or type, for example as shown here and shown here, allowing calls to sequenceOfInt.fold(Add.self) or ["a", "bc"].reduce(String.join) or frames.reduce(CGRect.union). This may be an avenue worth exploring in the future but its scope lies outside this proposal.

  • Stephen Celis had a really fun approach for combining keypaths with reduce.

Acknowledgements

Thanks Soroush Khanlou, Tim Vermeulen, Lily Vulcano, Davide De Franceschi, Stephen Cellis, Matthew Johnson, Nevin, Brandon Williams, Tellow Krinkle, David Hart, Peter Tomaselli, Ben Cohen, Lantua, Stephen Cellis, and everyone else who offered their feedback, functional programming experience, and design insights.


#2

Without commenting on the rest of the proposal, I just want to point out that mathematically the empty product is in fact equal to 1, the multiplicative identity.


(Brandon Williams) #3

The examples given (for CGRect and longest strings) aren't super convincing as they stand. In the case of CGRect and union, the null rectangle is the rectangle that leaves all other rectangles unchanged when taking the union, and so it's appropriate to do:

let boundingRectangle = rectangles.reduce(.null) { $0.union($1) }

Similarly CGRect.infinite serves the same purpose but for intersection, and so it's appropriate to do:

rectangles.reduce(.infinite) { $0.intersection($1) }

And in the case of the longest word example, that snippet would probably best expressed using max:

let longestAnimal = animals.max { $0.count < $1.count }

I think it would be nice to see stronger examples.

It's more than "reasonably argued", but rather the only way it can be defined. The empty sum must be 0 and the empty product must be 1. A quick way to see this is to figure out how you would want sum and prod to act with respect to array concatenation:

sum([1, 2, 3, 4]) = sum([1, 2] + [3, 4]) = sum([1, 2]) + sum([3, 4])
prod([1, 2, 3, 4]) = prod([1, 2] + [3, 4]) = prod([1, 2]) * sum([3, 4])

You would want the sum of a concatenation of arrays to be the sum of each array, and similarly for multiplication. This means, for example:

sum([3, 4]) = sum([] + [3, 4]) = sum([]) + sum([3, 4])
prod([3, 4]) = prod([] + [3, 4]) = prod([]) * sum([3, 4])

So you have no choice but for sum([]) = 0 and prod([]) = 1.


(Matthew Johnson) #4

FWIW, there is a way to solve the issue without introducing an optional in many cases. We could introduce a Monoid protocol:

protocol Monoid {
    associatedtype Value

    /// must obey identity laws with respect to `combine`
    static var identity: Value

    /// must be associative
    static func combine(_ lhs: Value, _ rhs: Value) -> Value
}

With conformances such as:

extension Int {
    enum Add: Monoid {
        static var identity = 0
        static func combine(_ lhs: Int, _ rhs: Int) { return lhs + rhs }
    }
    enum Multiply: Monoid {
        static var identity = 1
        static func combine(_ lhs: Int, _ rhs: Int) { return lhs * rhs }
    }
}

and this overload of fold:

public func fold<M: Monoid>(_ Monoid.Type) -> Element where M.Value == Element

which would then be called as follows:

let sum: Int = sequenceOfInt.fold(Add.self)

(Tellow Krinkle) #5

Shouldn't Int be optional here?

Note: This one could be done much more obviously with

let longestAnimal = animals.max(by: { $0.count < $1.count })

Other than that, I would love to see this happen, though I feel like if the common thing is for other languages to use fold and reduce for the opposite of what Swift does, maybe we should just use reduce for both to avoid confusing people...


(Erica Sadun) #6

Fair enough. Editing. (Also edited for CGRect.null, and animals.max(by:). Thanks


(Gwendal Roué) #7

I support this pitch.

I've seen myself write the following more than a couple of times:

if let first = array.first {
    val = array.dropFirst.reduce(first) { ... }
} else {
    val = nil
}

If the CGRect example can be written with reduce(.null), you can not with MKRect (there is no MKRect.null).

Besides:

  • Having developed in Ruby, I was missing it.
  • Before one knows about monoids and neutral elements, one naturally sums [1, 2, 3] with 1 + 2 + 3, not 0 + 1 + 2 + 3. I mean that reduce has a little more mental overhead than fold.

(David Hart) #8

I think that overloading reduce makes so much more sense than introducing a new fold name which may confuse people, that I would suggest rewriting the proposal with it.


(Brandon Williams) #9

I couldn't find an MKRect API, but there is MKMapRect, and it does provide MKMapRect.null as well as MKMapRect.world. Those are what you would reduce with when using union and intersection respectively.


(Peter Tomaselli) #10

As a functional partisan (:sweat_smile:), I would much rather see Monoid introduced to the standard library, but I understand that’s probably a tough sell. Moving on…

Quick background: we maintain a library here at work (which we’ve been using for about a year, and which was also recently open-sourced) that includes not only Monoid, but also the concept of Reducers — simple struct wrappers around reduce-shaped functions, and some other functions to compose them. (Heavily inspired by Brandon and Stephen’s work at Point-free, so if you’ve seen any of that stuff then you’ll probably have the flavor of what I’m talking about).

In my experience advocating for this library so far, the biggest hurdle is that many developers who are unfamiliar with functional stuff just don’t have the intuition for how reduce works, period. I regularly find myself leaving a comment like “this [huge thing] could be a reduce!” on change requests, for example.

I have much less frequently been bothered by the ergonomics of reduce (although it has happened), as well as the fact that some operations have “unintuitive” initial values (for example, Int.max when you want to calculate a minimum).

So I don’t personally feel that the existing inconveniences are enough to warrant a whole new method. Additionally, I have to say that the number one problem in our codebase overall has got to be the proliferation of optionals much too far into systems and APIs, mostly because of people upstream using optional-returning API and failing to squelch those optionals at or close to the source.

To me the fact that reduce takes a non-nil initial value and that that value is static is a feature. When I’m reading complicated or gnarly code, each invocation of reduce is a place to stop and catch my breath, because that initial value is right there for me to see. So I think this is in some ways a surprisingly consequential proposal, because now the mental model of what happens at a fold call site can be sneakily quite complex.

Sorry for the wall of text. I’ve thought a lot about reduce. :laughing:


(Gwendal Roué) #11

Thanks for fixing my mistake, Brandon. And teaching me about the pieces I was missing.


(Ben Cohen) #12

As an aside: whenever you see if let x = ... { y = doSomething(x) } else { y = nil }, that's Optional.map:

let val = array.first.map { array.dropFirst().reduce($0) { ... } }

Not to everyone's taste but I feel it can lead to clearer code once you get comfortable with it, especially for things like simple computed properties.


(Ben Cohen) #13

I agree with this. I think this addition is on the edge of trivially composable (especially for collections) and adding a new function name that does basically the same thing with a twist (and so has no solid reason to be named differently) would weigh against it, on complexity grounds. Just overloading the same name should help with that. The presence/absence of an initial value argument ought to avoid any overload ambiguity.


(Jon Shier) #14

As an aside, this seems like an abuse of map, as you're not transforming the Optional, just using its value somewhere else. Personally, I'd like to see something to grab the value without expecting a transform (and a throwing accessor like Result's get() too).


(Ben Cohen) #15

Not sure why you say that. You are mapping the non-nil first element into an initial value that you use to transform the remainder. It is the value of first that entirely determines whether the reduce produces a value or not.


(Jon Shier) #16

Sorry, misread your example. My desire remains though. :smiley:


#17

I can see where you’re coming from, but IMO Swift never intends to be functional. Only that functional paradigm does a very good job at expressing user intents. With that said, reduce still have some problems.

Most of the time I see reduce being used in the folding manner we’re pitching, they tend to assume that the sequence is not empty and forget to handle such case appropriately. Say:


let value = sequence.min()

I’d be more surprised for it to be Value.max rather than nil on empty sequence.

Regarding functional side, using fold would allow us to use Semigroup, or even Magma, instead of Monoid. Though it’s be hard sell to say that it provide much more practical uses.

Optional does force you to think about failing case while maintaining a lightweight mental model (Our community has been making sure of that), much in the same way that default value is lacking. Though it’s still subjected to being abused.

Needless to say I assess this pitch positively, thought In terms of naming I think fold would be better compared to reduce since they seem to handle slightly different use cases.


(Peter Tomaselli) #18

Well, I think it’s good to take inspiration from other languages where it’s appropriate! The great thing about Monoid is how bundling the empty value with the type opens the door to creating very expressive types.

The foreign thing about Monoid, imo, is the whole issue of “newtypes”. I can’t think of another standard library API where users are asked to write wrapper types around types they “already have”. In my experience people are very weirded out by this.

I don’t think of calling reduce on an empty sequence as being a “failure” in the same way other optional-returning methods can “fail”. It’s very possible for a sequence to be empty! The current reduce API gives the user an opportunity to be very precise about what should happen in that situation, which I think is quite cool. Simply bailing out to an optional is that opportunity lost, in my opinion.

I also think that we may not have fully explored all the ways in which nil may be an unintuitive result from this function. Here’s one:

[[String]]().fold(+) // => nil

Here’s another??

struct Account { let balance: Int }
[Account]().fold { Account(balance: $0.balance + $1.balance) } // => nil

Or this kinda thing:

enum ViewState {
	case error(String)
	case values([Any])
}
[ViewState]().fold { acc, el in 
	switch (acc, el) {
		case (.error(let error), _),
		 (_, .error(let error)): return .error(error)
		case (.values(let v1), .values(let v2)): return .values(v1 + v2)
	}
} // => nil

The meaningful “empty” value of non-trivial product and sum types is quite frequently not nil! reduce as it is now at least makes you write the empty value in your source code. Monoid would let you design it into the type itself. :slight_smile:


#19

It’d be best not to require too much of an external information, I do understand Monoid as a mathematical concept (it’s a good naming when you know what it does even without knowing the library :smiley:), but I don’t know if you’re using it as a wrapper class, protocol, generic struct, etc. which makes it rather hard to follow.

Agreed. What I’m trying to say is

  1. It’s very possible for a sequence to be empty
  2. People tend to forget number 1.
  3. fold would likely remind them of number 1.

I wouldn’t agree, at best using reduce in this manner would allow you to retrieve empty value, or identity for the respective class, it wouldn’t allow you to bail out, break the loop, etc. You’ll need to check for empty sequence separately, resulting in an unhealthy amount of boilerplate.

Also I agree that some cases can be simpler to use reduce, especially when empty value is tolerable in case of empty sequence. We can let reduce have it (we’re not removing it afterall). What I’m pushing forward is that fold also has its place.

Your Account case is quite interesting. If I have code for the bank to sum the balance associated with particular person and that person don’t have any account, I’d show pop-up inviting them to make one.
I digress, but case in point, most usage of reduce as fold already assume (or explicitly check) that the sequence is not empty.

Your ViewState case is also an interesting one, I can’t even tell if returning value with empty collection is a good idea. I’d rather throw a special Invalid argument Error, which is something reduce doesn’t inherently support. :stuck_out_tongue:

Furthermore, I’d like to be able to easily have functions inline with Sequence.min() and Sequence.max().


(Matthew Johnson) #20

The Monoid design I pitched upthread does not involve wrapper types. Instead, it models the monoids directly. Individual data types are not monoids. Monoid requires a specific identity and combining operation are chosen to go with a type. This is why it does not make sense to say Int is a monoid or to design a Monoid protocol that a type like Int would conform to. Instead, there is an Additive (or Sum) monoid, a Multiplicative (or Product) monoid, etc. These monoids could be defined generically so the don’t need to be repeated for every numeric type.

The reason I bring up Monoid is that many times the combining operation people actually want to perform on a sequence is monoidal and by modeling that we can avoid an unnecessary optional. This can be done with code that is roughly as concise as the alternative approach if the appropriate Monoid conformances are provided by the standard library and Foundation. Yes, it requires people to learn a new concept, but I believe it is worthwhile.

If people think Monoid is a scary name we could always consider using a different name that is considered more approachable. On the other hand, Monoid is very easy to search for and there is an enormous amount of material available for learning about the concept that is already using that name.

I agree with the motivation of the pitch to allow users to avoid needing to explicitly state the initial value on every call to reduce. However, I also think the vast majority of uses of the proposed fold operation would be much improved by using Monoid and avoiding the optional result.

I didn’t mention it in my earlier post but if passing Add.self at the call site is considered too verbose or confusing it is possible to design a solution where the monoid can be specified with dot shorthand (i.e. .add or .sum).