scan functions expect you to provide a neutral element, such as
0 for addition or
1 for multiplication. But sometimes there may not be an obvious neutral element. In mathematics, such a structure is called a semigroup, while those with neutral elements are called monoids.
We can always turn any semigroup into a monoid, simply by adding a distinct new value to serve as the neutral element.
type with_neutral 't = #neutral | #val t
The operator must also be augmented to handle the neutral element:
def f_with_neutral 't (f: t -> t -> t) (x: with_neutral t) (y: with_neutral t) : with_neutral t =match (x, y) case (#val x, #val y) -> #val (f x y) case (#neutral, _) -> y case (_, #neutral) -> x
We can then define a variant of
reduce that does not require a neutral element to be provided. If the input array is empty, it will return the
def reduce1 't (f: t -> t -> t) (ts: t) : with_neutral t = reduce (f_with_neutral f) #neutral (map (\t -> #val t) ts)
Try it out in the REPL:
> reduce1 (+) (iota 100) #val 4950i32 > reduce1 (+) (iota 0) #neutral
reduce1 is less efficient than
reduce due to the baggage of carrying around
#neutral, as well as the extra control flow. It is always better if a neutral element is more naturally available, but this technique will do in a pinch.
Sadly, no similar trick exists for turning a non-associative function associative.