Hello Steffen,

Let's take Kotlin documentation (https://kotlinlang.org/docs/collection-aggregate.html#fold-and-reduce)

Naming is not so consistent in all the programming languages, they mix up the names "reduce" and "fold". For example in Haskell "fold" does not take an initial value, so it is like a "reduce" in Kotlin. In Kotlin, Java, Scala and other oo languages "reduce" does not take an initial value while "fold" does. Pharo align with those languages (except that out fold is called #inject:into:)

So for me the Pharo methods #reduce: and #inject:into represent well what they are doing and they are well named.

Cheers,
Sebastian

----- Mail original -----

Actually, #inject:into: is what is normally called fold or foldl,
and #reduce: is commonly called fold1.  It is very confusing to
call foldl1 #fold:.

To the best of my knowledge, the name 'reduce' comes from APL.
"Z <- LO/R
has the effect of placing the function LO between adjacent pairs
of items along the last axis of R and evaluating the resulting
expression for each subarray.
If R is the vector A B C the LO-reduction is defined as follows:
LO/R <-> A LO B LO C"
which for APL means A LO (B LO C), so it's technically foldr1.
-- IBM APL2 Language Reference, 1994, page 209.

The name given to #inject:into: when it was first invented was
LIT, short for List ITeration.

Here's a reference: Functional Programming, Application and
Implementation, Peter Henderson, 1980, page 41:
<quote>
As another example of a higher-order function consider the following
operation of reduction (the idea and the name are in fact taken from the
programming language APL). We define reduce(x,g,a) where x is a list,
g is a binary function, and a is a constant, so that the list
x = (Xl. . . Xk) is reduced to the value g(X1, g(X2, ... g(Xk,a) ...))
<snip>
reduce(x,g,a) = if x = NIL then a else
g(car(x),reduce(cdr(x),g,a))
</quote>

So APL used "reduce" for foldr1, and Henderson, because
most functions don't carry their identity with them,
used it for foldr.

As I recall it, the name "reduce" was dropped because
people wanted to support both foldl and foldr (and did
NOT want to apply it to higher-ranked arrays, so that
'rank reduced by 1' wasn't an aid to memory).  But it
IS a name for the operation that predates Smalltalk
and is still in use (as APL itself is).

If it comes to that, this higher-order function is
called 'reduce' in Swift:
https://developer.apple.com/documentation/swift/array/reduce(::)
and of course the Map-Reduce paradigm is famous, and
guess what 'Reduce' stands for?

An intention-revealing name in Smalltalk would have been
aCollection injectInto: aBinaryValuable [ifNone: emptyBlock]

On Thu, 13 Apr 2023 at 07:03, Steffen Märcker merkste@web.de wrote:

The standard prelude in Haskell does not define anything
called "fold".  It defines fold{l,r}{,1} which can be
applied to any Foldable data (see Data.Foldable).  For
technical reasons having to do with Haskell's
non-strict evaluation, foldl' and foldr' also exist.
But NOT "fold".

https://hackage.haskell.org/package/base-4.18.0.0/docs/Data-Foldable.html#laws

On Thu, 13 Apr 2023 at 21:17, Sebastian Jordan Montano <
sebastian.jordan@inria.fr> wrote:

Hi Richard and Sebastian!

Interesting read. I obviously was not aware of the variety of meanings for fold/reduce. Thanks for pointing this out. Also, in some languages it seems the same name is used for both reductions with and without an initial value. There's even a list on WP on the matter: https://en.wikipedia.org/wiki/Fold_%28higher-order_function%29#In_various_languages

Kind regards,
Steffen

Richard O'Keefe schrieb am Donnerstag, 13. April 2023 13:16:28 (+02:00):

The standard prelude in Haskell does not define anything
called "fold".  It defines fold{l,r}{,1} which can be
applied to any Foldable data (see Data.Foldable).  For
technical reasons having to do with Haskell's
non-strict evaluation, foldl' and foldr' also exist.
But NOT "fold".

https://hackage.haskell.org/package/base-4.18.0.0/docs/Data-Foldable.html#laws

On Thu, 13 Apr 2023 at 21:17, Sebastian Jordan Montano sebastian.jordan@inria.fr wrote:

Hello Steffen,

Let's take Kotlin documentation (https://kotlinlang.org/docs/collection-aggregate.html#fold-and-reduce)

Naming is not so consistent in all the programming languages, they mix up the names "reduce" and "fold". For example in Haskell "fold" does not take an initial value, so it is like a "reduce" in Kotlin. In Kotlin, Java, Scala and other oo languages "reduce" does not take an initial value while "fold" does. Pharo align with those languages (except that out fold is called #inject:into:)

So for me the Pharo methods #reduce: and #inject:into represent well what they are doing and they are well named.

Cheers,
Sebastian

----- Mail original -----

--
Gesendet mit Vivaldi Mail. Laden Sie Vivaldi kostenlos von vivaldi.com herunter.

OUCH.  Wikipedia is as reliable as ever, I see.
compress and reduce aren't even close to the same thing.
Since the rank of the result of compression is the same
as the rank of the right operand, and the rank of the
result of reducing is one lower, they are really quite
different.  compress is Fortran's PACK.
https://gcc.gnu.org/onlinedocs/gfortran/PACK.html

On Fri, 14 Apr 2023 at 01:34, Steffen Märcker merkste@web.de wrote:

:-D I don't know how compress made onto that site. There is not even an example in the list of language examples where fold/reduce is named compress.

Richard O'Keefe schrieb am Donnerstag, 13. April 2023 16:34:29 (+02:00):

OUCH.  Wikipedia is as reliable as ever, I see.
compress and reduce aren't even close to the same thing.
Since the rank of the result of compression is the same
as the rank of the right operand, and the rank of the
result of reducing is one lower, they are really quite
different.  compress is Fortran's PACK.
https://gcc.gnu.org/onlinedocs/gfortran/PACK.html

On Fri, 14 Apr 2023 at 01:34, Steffen Märcker merkste@web.de wrote:

Hi Richard and Sebastian!

Interesting read. I obviously was not aware of the variety of meanings for fold/reduce. Thanks for pointing this out. Also, in some languages it seems the same name is used for both reductions with and without an initial value. There's even a list on WP on the matter: https://en.wikipedia.org/wiki/Fold_%28higher-order_function%29#In_various_languages

Kind regards,
Steffen

Richard O'Keefe schrieb am Donnerstag, 13. April 2023 13:16:28 (+02:00):

The standard prelude in Haskell does not define anything
called "fold".  It defines fold{l,r}{,1} which can be
applied to any Foldable data (see Data.Foldable).  For
technical reasons having to do with Haskell's
non-strict evaluation, foldl' and foldr' also exist.
But NOT "fold".

https://hackage.haskell.org/package/base-4.18.0.0/docs/Data-Foldable.html#laws

On Thu, 13 Apr 2023 at 21:17, Sebastian Jordan Montano sebastian.jordan@inria.fr wrote:

Hello Steffen,

Let's take Kotlin documentation (https://kotlinlang.org/docs/collection-aggregate.html#fold-and-reduce)

Naming is not so consistent in all the programming languages, they mix up the names "reduce" and "fold". For example in Haskell "fold" does not take an initial value, so it is like a "reduce" in Kotlin. In Kotlin, Java, Scala and other oo languages "reduce" does not take an initial value while "fold" does. Pharo align with those languages (except that out fold is called #inject:into:)

So for me the Pharo methods #reduce: and #inject:into represent well what they are doing and they are well named.

Cheers,
Sebastian

----- Mail original -----

--
Gesendet mit Vivaldi Mail. Laden Sie Vivaldi kostenlos von vivaldi.com herunter.

The reason I came up with the naming question in the first place is that I (finally !) finish my port of Transducers to Pharo. But currently, I am running into a name clash. Maybe you have some good ideas how to resolve the following situation in a pleasant way.

• #fold: exists in Pharo and is an alias of #reduce:
• #reduce: exists in Pharo and calls #foldLeft: which also deals with more than two block arguments

Both of which are not present in VW. Hence, I used the following messages in VW with no name clash:

• #reduce: aReduction "= block + initial value"
• #reduce:init: is similar to #inject:into: but executes an additional completion action

Some obvious ways to avoid a clash in Pharo are:

1. Make #reduce: distinguish between a reduction and a simple block (e.g. by double dispatch)
2. Rename the transducers #reduce: to #injectInto: and adapt #inject:into: to optionally do the completion
3. Find another selector that is not too counter-intuitive

All three approaches have some downsides in my opinion:

1. Though straight forward to implement, both flavors behave quite different, especially with respect to the number of block arguments. The existing one creates a SequenceableCollection and partitions it according to the required number of args. Transducers' #reduce: considers binary blocks as the binary fold case but ternary blocks as fold with indexed elements.
2. This is a real extension of #inject:into: but requires to touch multiple implementations of that message. Something I consider undesirabe.
3. Currently, I cannot think of a good name that is not too far away from what we're familiar with.

Do you have some constructive comments and ideas?

Kind regards,
Steffen

Steffen Märcker schrieb am Donnerstag, 13. April 2023 17:11:15 (+02:00):

:-D I don't know how compress made onto that site. There is not even an example in the list of language examples where fold/reduce is named compress.

Richard O'Keefe schrieb am Donnerstag, 13. April 2023 16:34:29 (+02:00):

OUCH.  Wikipedia is as reliable as ever, I see.
compress and reduce aren't even close to the same thing.
Since the rank of the result of compression is the same
as the rank of the right operand, and the rank of the
result of reducing is one lower, they are really quite
different.  compress is Fortran's PACK.
https://gcc.gnu.org/onlinedocs/gfortran/PACK.html

On Fri, 14 Apr 2023 at 01:34, Steffen Märcker merkste@web.de wrote:

Hi Richard and Sebastian!

Interesting read. I obviously was not aware of the variety of meanings for fold/reduce. Thanks for pointing this out. Also, in some languages it seems the same name is used for both reductions with and without an initial value. There's even a list on WP on the matter: https://en.wikipedia.org/wiki/Fold_%28higher-order_function%29#In_various_languages

Kind regards,
Steffen

Richard O'Keefe schrieb am Donnerstag, 13. April 2023 13:16:28 (+02:00):

The standard prelude in Haskell does not define anything
called "fold".  It defines fold{l,r}{,1} which can be
applied to any Foldable data (see Data.Foldable).  For
technical reasons having to do with Haskell's
non-strict evaluation, foldl' and foldr' also exist.
But NOT "fold".

https://hackage.haskell.org/package/base-4.18.0.0/docs/Data-Foldable.html#laws

On Thu, 13 Apr 2023 at 21:17, Sebastian Jordan Montano sebastian.jordan@inria.fr wrote:

Hello Steffen,

Let's take Kotlin documentation (https://kotlinlang.org/docs/collection-aggregate.html#fold-and-reduce)

Naming is not so consistent in all the programming languages, they mix up the names "reduce" and "fold". For example in Haskell "fold" does not take an initial value, so it is like a "reduce" in Kotlin. In Kotlin, Java, Scala and other oo languages "reduce" does not take an initial value while "fold" does. Pharo align with those languages (except that out fold is called #inject:into:)

So for me the Pharo methods #reduce: and #inject:into represent well what they are doing and they are well named.

Cheers,
Sebastian

----- Mail original -----

--
Gesendet mit Vivaldi Mail. Laden Sie Vivaldi kostenlos von vivaldi.com herunter.

#reduce: aReduction
Are you saying that aReduction is an object from which
a dyadic block and an initial value can be derived?
That's going to confuse the heck out of Dolphin and Pharo
users (like me, for example).  And in my copy of Pharo,
#reduce: calls #reduceLeft:, not #foldLeft:.
The sad thing about #reduceLeft: in Pharo is that in order
to provide extra generality I have no use for, it fails to
provide a fast path for the common case of a dyadic block.

reduceLeft: aBlock
aBlock argumentCount = 2 ifTrue: [
|r|
r := self first.
self from: 2 to: self last do: [:each |
r := aBlock value: r value: each].
^r].
... everything else as before ...

Adding up a million floats takes half the time using the
fast path (67 msec vs 137 msec).  Does your #reduce:
also perform "a completion action"?  If so, it definitely
should not be named after #inject:into:.

At any rate, if it does something different, it should have
a different name, so #reduce: is no good.

#reduce:init:
There's a reason why #inject:into: puts the block argument
last.  It works better to have "heavy" constituents on the
right in an English sentence, and it's easier to indent
blocks when they come last.

Which of the arguments here specifies the 'completion action'?
What does the 'completion action' do?  (I can't tell from the name.)

I think the answer is clear:

• choose new intention-revealing names that do not clash.

If I have have understood your reduce: aReduction correctly,
a Reduction specifies

• a binary operation (not necessarily associative)
• a value which can be passed to that binary operation
  which suggests that it represents a magma with identity.
  By the way, it is not clear whether
  {x} reduce: <<ident. binop>>
  answers x or binop value: ident value: x.
  It's only when ident is an identity for binop that you
  can say 'it doesn't matter'.
  I don't suppose you could bring yourself to call
  aReduction aMagmaWithIdentity?

Had you considered
aMagmaWithIdentity reduce: aCollection
where the #reduce: method is now in your class so
can't technically clash with anything else?
All you really need from aCollection is #do: so
it could even be a stream.

MagmaWithIdentity

 |r|
 r := self identity.
 anEumerable do: [:each | r := self combine: r with: each].
 ^r

MagmaSansIdentity

 |r f|
 f := r := nil.
 anEnumerable do: [:each |
   r := f ifNil: [f := self. each] ifNotNil: [self combine: r with:

each]].
f ifNil: [anEnumerable error: 'is empty'].
^r

On Fri, 14 Apr 2023 at 05:02, Steffen Märcker merkste@web.de wrote:

Hi Richard!

Thanks for sharing your thoughts.

There's a reason why #inject:into: puts the block argument
last.  It works better to have "heavy" constituents on the
right in an English sentence, and it's easier to indent
blocks when they come last.

Nice, I never though of it this way. I always appreciate a historical background.

Let me try to respond to the rest with a focus on the ideas. First of all, the point of the transducers framework is to cleanly separate between iteration over sequences, processing of the elements and accumulation of a result. It enables easy reuse the concepts common to different data structures.

1. What do I mean by completion? If we iterate over a sequence of objects, we sometimes want to do a final step after all elements have seen to complete the computation. For instance, after copying elements to a new collection, we may want to trim it to its actual size:

   distinct := col inject: Set new into: #add.
   distinct trim.

For some cases it turns out to be useful to have an object that knows how to do both:

distinct := col reduce: (#add completing: #trim) init: Set new.

#reduce:init: knows how to deal with both this new objects and ordinary blocks. For now I will call both variants a "reducing function". Note, completion is completely optional and the implementation is literally #inject:into: plus completion if required.

2. What is a reduction? In some cases, it turns out to be useful to pair up a reducing function with an (initial) value. You called it a magma and often its indeed the neutral element of a mathematical operator, e.g., + and 0. But we can use a block that yields the initial value, too. For instance:

   sum := #+ init: 0.
   result := numbers reduce: sum.

   toSet := (#add completing: #trim) initializer: [Set new].
   distinct := col reduce: toSet.

#reduce: is just a shorthand that passes the function and the value to #reduce:init: Maybe #reduceMagma: is a reasonable name?

3. The reason I implemented #reduce:init: directly on collections, streams, etc. is that these objects know best how to efficiently iterate over their elements. And if a data structure knows how to #reduce:init: we can use it with all the transducers functions, e.g., for partitioning, filtering etc. Other useful methods  could then be added to the behaviour with a trait, e.g., #transduce:reduce:init which first apples a transducer and then reduces. As traits are not available in plain VW 8.3, I did not try this approach, though.

4. Lets take #reduce:Left: as and example and reimplement the method using transducers, shall we? The following code works for each sequence/collection/stream that supports #transduce:reduce:init:

   reduceLeft: aBlock

   | head rest arity |
   head := self transduce: (Take number: 1) reduce: [:r :e | e] init: nil.
   rest := Drop number: 1.

   arity := aBlock arity.
   ^arity = 2
   ifTrue: [self transduce: rest reduce: aBlock init: head]
   ifFalse: [
   | size arguments |
   size := arity - 1.
   rest := rest * (Partition length: size) * (Remove predicate: [:part | part size < size]).
   arguments := Array new: arity.
   arguments at: 1 put: head.
   self
   transduce: rest
   reduce: ([:args :part |
   args
   replaceFrom: 2 to: arity with: part;
   at: 1 put: (aBlock valueWithArguments: args);
   yourself] completing: [:args | args first])
   init: arguments]

This code is both more general and faster: It does not create an intermediate OrderedCollection and it treats the common case of binary blocks efficiently. Note the implementation can more compact and optimized if it was specialized in certain class. For instance, SequenceableCollection allows accessing elements by index which turns the first line into a simple "self first".

Thanks for staying with me for this long reply. I hope I did not miss a point. I do not insist on the existing names but will appreciate any ideas.

Best, Steffen

Richard O'Keefe schrieb am Freitag, 14. April 2023 09:43:32 (+02:00):

#reduce: aReduction
Are you saying that aReduction is an object from which
a dyadic block and an initial value can be derived?
That's going to confuse the heck out of Dolphin and Pharo
users (like me, for example).  And in my copy of Pharo,
#reduce: calls #reduceLeft:, not #foldLeft:.
The sad thing about #reduceLeft: in Pharo is that in order
to provide extra generality I have no use for, it fails to
provide a fast path for the common case of a dyadic block.

reduceLeft: aBlock
aBlock argumentCount = 2 ifTrue: [
|r|
r := self first.
self from: 2 to: self last do: [:each |
r := aBlock value: r value: each].
^r].
... everything else as before ...

Adding up a million floats takes half the time using the
fast path (67 msec vs 137 msec).  Does your #reduce:
also perform "a completion action"?  If so, it definitely
should not be named after #inject:into:.

At any rate, if it does something different, it should have
a different name, so #reduce: is no good.

#reduce:init:
There's a reason why #inject:into: puts the block argument
last.  It works better to have "heavy" constituents on the
right in an English sentence, and it's easier to indent
blocks when they come last.

Which of the arguments here specifies the 'completion action'?
What does the 'completion action' do?  (I can't tell from the name.)

I think the answer is clear:

• choose new intention-revealing names that do not clash.

If I have have understood your reduce: aReduction correctly,
a Reduction specifies

• a binary operation (not necessarily associative)
• a value which can be passed to that binary operation
  which suggests that it represents a magma with identity.
  By the way, it is not clear whether
  {x} reduce: <<ident. binop>>
  answers x or binop value: ident value: x.
  It's only when ident is an identity for binop that you
  can say 'it doesn't matter'.

I don't suppose you could bring yourself to call
aReduction aMagmaWithIdentity?

Had you considered
aMagmaWithIdentity reduce: aCollection
where the #reduce: method is now in your class so
can't technically clash with anything else?
All you really need from aCollection is #do: so
it could even be a stream.

MagmaWithIdentity

 |r|
 r := self identity.
 anEumerable do: [:each | r := self combine: r with: each].
 ^r

MagmaSansIdentity

 |r f|
 f := r := nil.
 anEnumerable do: [:each |
   r := f ifNil: [f := self. each] ifNotNil: [self combine: r with: each]].
 f ifNil: [anEnumerable error: 'is empty'].
 ^r

On Fri, 14 Apr 2023 at 05:02, Steffen Märcker merkste@web.de wrote:

The reason I came up with the naming question in the first place is that I (finally !) finish my port of Transducers to Pharo. But currently, I am running into a name clash. Maybe you have some good ideas how to resolve the following situation in a pleasant way.

• #fold: exists in Pharo and is an alias of #reduce:
• #reduce: exists in Pharo and calls #foldLeft: which also deals with more than two block arguments

Both of which are not present in VW. Hence, I used the following messages in VW with no name clash:

• #reduce: aReduction "= block + initial value"
• #reduce:init: is similar to #inject:into: but executes an additional completion action

Some obvious ways to avoid a clash in Pharo are:

1. Make #reduce: distinguish between a reduction and a simple block (e.g. by double dispatch)
2. Rename the transducers #reduce: to #injectInto: and adapt #inject:into: to optionally do the completion
3. Find another selector that is not too counter-intuitive

All three approaches have some downsides in my opinion:

1. Though straight forward to implement, both flavors behave quite different, especially with respect to the number of block arguments. The existing one creates a SequenceableCollection and partitions it according to the required number of args. Transducers' #reduce: considers binary blocks as the binary fold case but ternary blocks as fold with indexed elements.
2. This is a real extension of #inject:into: but requires to touch multiple implementations of that message. Something I consider undesirabe.
3. Currently, I cannot think of a good name that is not too far away from what we're familiar with.

Do you have some constructive comments and ideas?

Kind regards,
Steffen

Steffen Märcker schrieb am Donnerstag, 13. April 2023 17:11:15 (+02:00):

:-D I don't know how compress made onto that site. There is not even an example in the list of language examples where fold/reduce is named compress.

Richard O'Keefe schrieb am Donnerstag, 13. April 2023 16:34:29 (+02:00):

OUCH.  Wikipedia is as reliable as ever, I see.
compress and reduce aren't even close to the same thing.
Since the rank of the result of compression is the same
as the rank of the right operand, and the rank of the
result of reducing is one lower, they are really quite
different.  compress is Fortran's PACK.
https://gcc.gnu.org/onlinedocs/gfortran/PACK.html

On Fri, 14 Apr 2023 at 01:34, Steffen Märcker merkste@web.de wrote:

Hi Richard and Sebastian!

Interesting read. I obviously was not aware of the variety of meanings for fold/reduce. Thanks for pointing this out. Also, in some languages it seems the same name is used for both reductions with and without an initial value. There's even a list on WP on the matter: https://en.wikipedia.org/wiki/Fold_%28higher-order_function%29#In_various_languages

Kind regards,
Steffen

Richard O'Keefe schrieb am Donnerstag, 13. April 2023 13:16:28 (+02:00):

The standard prelude in Haskell does not define anything
called "fold".  It defines fold{l,r}{,1} which can be
applied to any Foldable data (see Data.Foldable).  For
technical reasons having to do with Haskell's
non-strict evaluation, foldl' and foldr' also exist.
But NOT "fold".

https://hackage.haskell.org/package/base-4.18.0.0/docs/Data-Foldable.html#laws

On Thu, 13 Apr 2023 at 21:17, Sebastian Jordan Montano sebastian.jordan@inria.fr wrote:

Hello Steffen,

Let's take Kotlin documentation (https://kotlinlang.org/docs/collection-aggregate.html#fold-and-reduce)

Naming is not so consistent in all the programming languages, they mix up the names "reduce" and "fold". For example in Haskell "fold" does not take an initial value, so it is like a "reduce" in Kotlin. In Kotlin, Java, Scala and other oo languages "reduce" does not take an initial value while "fold" does. Pharo align with those languages (except that out fold is called #inject:into:)

So for me the Pharo methods #reduce: and #inject:into represent well what they are doing and they are well named.

Cheers,
Sebastian

----- Mail original -----

--
Gesendet mit Vivaldi Mail. Laden Sie Vivaldi kostenlos von vivaldi.com herunter.