Traversable with data applicatives

[utdemir]

This discussion started at #126, where we discussed a proposed linear Foldable implementation and the fact that it is not implied by linear Traversable; and ended up concluding that what we need is a variant of the existing Traversable which uses data Applicatives instead of control Applicatives.

See the thread at #126 for a longer discussion, but I'm quoting the critical comment there, from @aspiwack:

We've established that being “traversable” by Control.Applicative-s is a common occurrence, but doesn't imply Foldable.

However, being “traversable” by Data.Applicative-s, a less common occurrence, does imply Foldable (indeed Const m is a Data.Applicative (for m a monoid)).

So, here is the thought. Why don't we give a name to the equivalent of traverse, but with Data.Applicative and add it to the Foldable type class (I'd call it fold but it's already taken, let's find another name)?

This issue to discuss whether we indeed want another Traversable using data Applicatives; and if we do, bikeshed the details (mainly the name, I guess).

[aspiwack]

This wouldn't introduce backwards incompatible change. So I'll downgrade it to after-first-milestone status.

[sjoerdvisscher]

Regarding naming, since we have:

consumeFoldable :: (Consumable a, Foldable f) => f a %1 -> ()
consumeFoldable = foldMap consume

moveTraversable :: (Movable a, Traversable t) => t a %1 -> Ur (t a)
moveTraversable = traverse move

i.e. Foldable implies Consumable and Traversable using Data.Applicative implies Movable. So I think it makes sense to put Foldable and Traversable under Data.Unrestricted, which allows us to keep the names the same.

[treeowl]

I don't see why we'd want Foldable to have a traverse method; that seems a step too far, excluding things like Data.Set. But it would be very nice to be able to traverse with a Data.Applicative.

Here's a cute idea. I don't know if it's too cute, but it certainly collapses things a bit:

{-# LANGUAGE UndecidableSuperClasses, ... #-}

class Functor 'Many f => Functor m f where
  fmap :: (a %1-> b) %m-> f a %1-> f b

class (Applicative 'Many f, Functor m f) => Applicative m f where
  pure :: a %m-> f a
  liftA2 :: (a %1-> b %1-> c) %m-> f a %1-> f b %1-> f c

class (Functor 'Many t, Traversable 'One t) => Traversable m t where
  traverse :: Applicative m f => (a %1-> f b) -> t a %1-> f (t b)

Now

Functor 'Many  ~=  Data.Functor
Functor 'One ~= Control.Functor

Applicative 'Many ~= Data.Applicative
Applicative 'One ~= Control.Applicative

Traversable 'Many ~= traversable with a data Applicative
Traversable 'One ~= traversable with a control Applicative

[utdemir]

@treeowl That idea is seems to be similar to the one on the issue https://github.com/tweag/linear-base/issues/27.

I personally would prefer an interface like that than the explosion of classes as we have right now. The only downside I can (without any evidence) imagine is this possibly being confusing to the type checker, I think it is worth experimenting with.