Better define what Foldable ought to mean

[tel]

It's not entirely clear to me what Foldable ought to mean in a strict language. The core foldMap "visits" all elements but without lazy having lazy combination in plus we really will have to visit all of the elements and therefore will not have a real value if the data structure is infinite.

//: Monoid x -> Monoid (() => x)
function LazyMonoid(m) {
  return {
    zero: () => () => m.zero(),
    plus: (f, g) => () => plus(f(), g()),
  };
}

// t a = () => x a
// x a = null | { head: a, tail: t a }

//: (Monoid x, a -> x) -> (t a -> x)
function foldMap({ plus, zero }, inj) {
  //: (t a -> x)
  function go(s) {
    const x = s();
    // the recursive call here is too strict!
    return x ? plus(inj(x.head), go(x.tail)) : zero()
  };
  return go;
}

Here's the Haskell prior art showing how the lazy system can give rise to a strict one using seq

    -- | Right-associative fold of a structure.
    --
    -- @'foldr' f z = 'Prelude.foldr' f z . 'toList'@
    foldr :: (a -> b -> b) -> b -> t a -> b
    foldr f z t = appEndo (foldMap (Endo #. f) t) z

    -- | Right-associative fold of a structure,
    -- but with strict application of the operator.
    foldr' :: (a -> b -> b) -> b -> t a -> b
    foldr' f z0 xs = foldl f' id xs z0
      where f' k x z = k $! f x z

    -- | Left-associative fold of a structure.
    --
    -- @'foldl' f z = 'Prelude.foldl' f z . 'toList'@
    foldl :: (b -> a -> b) -> b -> t a -> b
    foldl f z t = appEndo (getDual (foldMap (Dual . Endo . flip f) t)) z
    -- There's no point mucking around with coercions here,
    -- because flip forces us to build a new function anyway.

    -- | Left-associative fold of a structure.
    -- but with strict application of the operator.
    --
    -- @'foldl' f z = 'List.foldl'' f z . 'toList'@
    foldl' :: (b -> a -> b) -> b -> t a -> b
    foldl' f z0 xs = foldr f' id xs z0
      where f' x k z = k $! f z x

Ultimately, in a strict setting Foldable appears to imply finiteness. Only with MonadicFoldable could we choose a non-strict semantics.

// Not good enough?

//: (Monad m, Monoid x, a -> m x) -> (t a -> m x)
function foldMapM({ smashWith, of }, { plus, zero }, inj) {
  function go(s) {
    const x = s();
    return x ? smashWith(plus)(inj(x.head), go(x.tail)) : of(zero());
  }
  return go;
}

// Monoid needs the ability to choose where to evaluate!

// type d x = () -> x

//: (Monoid (d x), a -> d x) -> (t a -> d x)
function foldMapL({ smashWith, of }, { plus, zero }, inj) {
  // t a -> d x
  function go(s) {
    return () => { // this isn't provided in the normal implementation! We've pushed the thunk up.
      const x = s();
      if (x) { return plus(inj(x.head), go(x.tail))(); }
      else { return zero()(); }
    };
    const x = s();
    return x ? smashWith(plus)(inj(x.head), go(x.tail)) : () => zero();
  }
  return go;
}