-- # Reducing or scanning without a neutral element
--
-- The `reduce` and `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](https://en.wikipedia.org/wiki/Semigroup), while those
-- with neutral elements are called
-- [monoids](https://en.wikipedia.org/wiki/Monoid).
--
-- 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 `#neutral` value.

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.