Add Traversable1

[masaeedu]

It is often useful to be able to traverse a non-empty structure with respect to a functor that is not quite Applicative, but is nevertheless Apply. A common use case I run into is transposing a <something> of objects into an object of <something>s.

const result = Arr.sequence(Obj)([{ x: 1, y: 2 }, { x: 3, y: 4 }])
// => { x: [1, 3], y: [2, 4] }

The problem is that objects in JS have a straightforward implementation of lift2, but lawfully implementing pure would require the ability to construct infinite objects with the same value at every possible key (this is possible with proxies, but let's not go there).

Instead, we want a weakening of the constraints of Traversable so that it can work with Applys. Conversely, the requirements on the traversable container are tightened; more things are Traversable than are Traversable1.

Here is an example of what an instance might look like for non-empty arrays:

// :: type Apply f = (Functor f) & { lift2: (a -> b -> c) -> f a -> f b -> f c }
// :: type Traversable1 t = { traverse1: Apply f -> (a -> f b) -> t a -> f (t b) }

// :: Traversable1 Array1
const Arr1 = (() => {
  const snoc = xs => x => [...xs, x];
  const traverse1 = A => f => ([x, ...xs]) =>
    xs.reduce((p, c) => A.lift2(snoc)(p)(f(c)), A.map(x => [x])(f(x)));

  return { snoc, traverse1 };
})();

// :: String[] -> String[] -> String[]
const intersection = s1 => s2 => {
  const s2_ = new Set(s2);
  return s1.filter(x => s2_.has(x));
};

// :: Apply Obj
const Obj = (() => {
  // :: Obj v -> String
  const keys = o => Object.keys(o);

  const zipWith = f => o1 => o2 => {
    const k1 = keys(o1);
    const k2 = keys(o2);
    const ks = intersection(k1)(k2);

    return ks.reduce((p, k) => ({ ...p, [k]: f(o1[k])(o2[k]) }), {});
  };

  const map = f => o => keys(o).reduce((p, k) => ({ ...p, [k]: f(o[k]) }), {});

  const lift2 = zipWith;

  return { zipWith, map, lift2 };
})();

// :: Traversable1 t -> Apply f -> t (f a) -> f (t a)
const sequence1 = T1 => A => xs => T1.traverse1(A)(x => x)(xs);

// :: Array1 (Obj x) -> Obj (Array1 x)
const s = sequence1(Arr1)(Obj);

// :: Array1 (Obj x)
const input = [{ x: 1, y: 2 }, { x: 3, y: 4 }];

console.log(s(input));
// => { x: [1, 3], y: [2, 4] }

Similar instances exist for non-empty objects themselves, non-empty trees, non-empty sets, etc.

Perhaps obvious, but it's worth noting that all Traversable1s are Traversable for free; since all Applicatives are (at least) Apply.

[nadameu]

I don't mean to dismiss your request, but Haskell's MaybeApply will turn any Apply into an Applicative. Maybe you can incorporate the logic into your Obj.

[masaeedu]

@nadameu The fact that MaybeApply will turn any Apply into an Applicative is of about the same relevance as saying that Maybe will turn any semigroup into a monoid. It is nevertheless useful to have Foldable1, if for no other reason than that threading Just/Nothing and the corresponding match through all your values (and similarly Either for promoting your Apply to an Applicative) is quite inefficient.

[masaeedu]

Btw, there's a better way to use MaybeApply than to mash it into Obj. Here's a snippet from a few months ago that illustrates how you can compositionally combine MaybeApply with an arbitrary Apply functor: https://runkit.com/masaeedu/maybeapply.