`Sequence` cleanup: `fold` vs `reduce`, more powerful `scan`

[fridis]

foldf is redundant with reduce, and fold* generally provides the same functionality like reduce*, so we should think of better names, e.g.,

• reduce(R type, init R, f (R,T) -> R | abort R) R should be reduce_or_abort
• foldf(B type, f (B,T)->B, e B) should be reduce(B type, init B, f (B,T)->B)
• fold1(f (T,T)->T) should be reduce1(f (T,T)->T)
• fold(m Monoid T) should be reduce(m Monoid T)

Similarly, we need a similar set for functions for Sequence.scan.

[maxteufel]

I'm not sure about this, in most languages, fold seems to be the more general variant of reduce by taking an additional accumulator parameter.

We should certainly make this more consistent though.

[simonvonhackewitz]

I'm not sure about this, in most languages, fold seems to be the more general variant of reduce by taking an additional accumulator parameter.

I agree with that.

For languages that provide both (e.g. Rust, Scala, Kotlin ...), the option to provide the initial value (and type) of the accumulator seems to be the difference.

Some languages only provide one, e.g. Python and JavaScript only have reduce (though the initial value can be provided as an optional argument), Haskell on the other hand only has foldl and foldr but no reduce.

I would therefore suggest to use "fold" for the first two:

• reduce(R type, init R, f (R,T) -> R | abort R) R should be fold_or_abort
• foldf(B type, f (B,T)->B, e B) should be fold(B type, init B, f (B,T)->B)

[fridis]

@simonvonhackewitz , can you collect what other languages (Go, Java, C#, Rust) use. I see that we have the following variants

1. with or without initial value
2. with a new result type R or using the same type T
3. order or operation: foldl vs. foldr
4. using a function argument or a monoid

So this gives a total of 16 variants, that is too many. We should probably drop the variant using the same type T (2.), so we are down to 8 variants.

Which of these variants do other languages provide and what are they called?

[simonvonhackewitz]

I think point 1. and 2. are basically the same, or should at least be combined. Without an initial type the result type must be of the same type, and if an initial value is provided I see no reason to limit it to the same type.

Go does not natively provide fold, reduce, or related operations.

Java provides reduce through the Stream API C# provides Aggregate via System.Linq Both can be used with an initial value in an overloaded version, in this case the result can be of a different type. They are left-associative. Monoid is not supported

Rust provides fold and reduce through the Iterator trait. fold is with initial value and the result type can be different. Both are left-associative.

[simonvonhackewitz]

@fridis ping

[fridis]

Having thought about this a bit, I suggest the following

• instead of the abort result in reduce, we should have an abort effect that permits returning early from any calculation, e.g., instead of

  max = 1000
  data := 0..100
  total := data.reduce 0 a,b->
      if a+b>max then
        abort max
      else 
        a+b
  

  do this

  max = 1000
  data := 0..100
  total := abortable ! ()->
    data.fold 0 a,b->
      if a+b>max then
        abortable.env.abort max
      else 
        a+b
  

• foldf/foldrf (with 3 arguments) should be called fold/foldr to be symmetric with scan (which has no f in this variant).
• I would go for only a single name, i.e, no fold and reduce with slightly different semantics like in Rust. The question is, what name: fold, reduce, aggregate. My fealing is that reduce is the most widely known term (but that might be because I went through the hadoop map-reduce hype period).
• if we use reduce as the common name, then foldr* should also be renamed as reducer*.
• we currently have foldr (s T, m Monoid T) using an initial value and a monoid only as the right-variant. This should IMHO be deleted.

@simonvonhackewitz, can you create new issues for adding an abortable effect (assign this to me), renaming foldf/foldrf, removing foldr (s T, m Monoid T), removing abort from reduce and, finally, renaming fold*/reduce* to a single name (which I suggest to be reduce*)?