It is looking to me that it would be easier to decide what to include if we had a few applications working with linear lists or similar. In the abstract, it is difficult to compare the alternatives (regarding the question about any).

All good points.

I believe any should be your first suggestion (no leftover, no Consumable). It's the unfortunate consequence of the linear (||) being strict. Or at the very least, it's a similar phenomenon.

I can't think of a Traversable which wouldn't have Consumable (t ()), but there may be. It is certainly true that there is no control applicative which would let us drop the container to implement some fold. Const m is a data applicative. At some point, we considered using data applicatives in the definition of Traversable, but we didn't go for it.

@b-mehta do you remember why not? Do you have thoughts on any of the above?

I don't recall completely, but we had a quick discussion here: #48, which could be useful. As for a Traversable without Consumable (t ()), doesn't (a,) where a isn't consumable work? I could be wrong though, it's been a while since I've thought about these things.

As for a Traversable without Consumable (t ()), doesn't (a,) where a isn't consumable work?

Sorry @b-mehta, I do not understand what you mean.

As far as I can understand when implementing foldMap, we can effectfully map the values inside the container, but then we are still left with the container itself that we somehow need to consume. As @aspiwack mentioned Const would be a solution to that, but it doesn't type check becuse it can not be a Control functor.

@aspiwack, Thanks, makes sense. I will make Foldable a superclass of Traversable.

As for a Traversable without Consumable (t ()), doesn't (a,) where a isn't consumable work?

Sorry @b-mehta, I do not understand what you mean.

He says that

instance Traversable ((,) a)

(even linearly)

But that you don't have instance Consumable (a,()) in general. This is very true. Thanks @b-mehta . In fact, this works with Const a as well.

And the argument for Traversable to use control applicative and not data applicative, is in fact similar.

This means, by the way, that Foldable oughtn't be a superclass of Traversable. Since Const a is Traversable, but not Foldable (in general). And so is (,) a. Quite fascinating all this.

Before merging this. I have a thought (it can be addressed in a future PR, but this thread is the perfect venue for this discussion). It occurred to me today. @b-mehta I'd like your opinion on this as well.

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)?

It gives a stark distinction between Foldable and Traversable in terms of Data and Control. It sort of makes sense, doesn't it? But maybe there are objections there that I'm not currently seeing. Probably even. So I'd like everybody's thought on the subject.

@aspiwack ,

I played around with a Traversable using Data.Applicative.

As you mentioned, it is a less common occurence; I couldn't implement instances for: (,) a, Const a or Either a, I now understand that the reason is Data.Applicative's possibility of duplicating those a's.

It is quite interesting how big of a difference linearity can make. After spending a few hours thinking about this, it does make sense. On the other hand, it feels a bit daunting at times; having two different Data.Functor.Traversable typeclass each differing by the Applicative instance. It is confusing to me because I think practically they are very similar to each other. So, I personally am not keen to introduce the additional complexity, and my prefence would be to only have Traversable using Control.Applicative's, and having a separate Foldable instance.

But I would also be happy to implement the new typeclass if you think it is worth it.

The heart of my question was, rather, do we lose anything if we add this data-traversal as an additional method in foldable:

class Functor t => Foldable t where
  …
  foldButReallyTraverseWellThisNeedABetterNameButWhatever :: Data.Applicative f => (a #-> f b) -> t a #-> f (t b)

Is there any functor of notice which supports foldMap (say) but not foldButReallyTraverseWellThisNeedABetterNameButWhatever?

Because I have this idea that this would be a good place for it.

[above comment edited after @utdemir pointed out I wrote in several mistakes. Disregard the email and go read the comment on github directly]

We found a few Foldable instances which does not support

f :: Data.Applicative f => (a #-> f b) -> t a #-> f (t b)

eg. Consumable a => (,) a, Consumable a => Either a. They can only work if the constraint is Movable instead of Consumable, since they end up calling Data.Applicative.pure :: a -> f a (notice the unrestricted arrow).

I just noticed another interesting difference. It looks like the foldl definition which used to be here and on the new Foldable instance is different:

-- Prelude.Linear.Internal.Simple.foldl (removed with this PR)
foldl :: (b #-> a -> b) -> b #-> [a] -> b

-- Data.Foldable.Linear.foldl
foldl :: (b #-> a #-> b) -> b #-> t a #-> b 

It looks like the old one traverses a non-linear container with a linear accumulator, which might be useful on some cases, but the new one still makes sense to me.

Maybe we should have both. Unfortunately that requires us to find different names for them.

For me foldMap is the central method of Foldable, all other methods derive from it using different Monoids. So if foldMap is linear on the container, all other methods should be too.

For me foldMap is the central method of Foldable, all other methods derive from it using different Monoids. So if foldMap is linear on the container, all other methods should be too.

I agree. However, the old signature also does make sense by itself, in fact I just had a case where I required exactly that. I guess it's derivable from the second one by mapping the list elements to Unrestricted, but it's a hassle.

Could you maybe do it with alaf? https://hackage.haskell.org/package/lens-4.19.2/docs/Control-Lens-Combinators.html#v:alaf

@sjoerdvisscher Thanks, yes, it looks like it is a job for alaf! Of course, that is given we implemented a linear version of it.

I now think since the new implementation already covers the old one with some wrapping and unwrapping around it, I am happy with only including the new one for now.

This PR is starting to diverge from master, so I want to try again to get it in. @aspiwack, it seems like there is no more discussion going on. We can ping some more people to look at it if you want to, or if you have any other comments I'd be happy to address them before we can merge this one.

To be frank, I lost track of this discussion. What are the conclusions in your opinion?

@aspiwack,

In my opinion, the biggest open question here is linear Foldable not being a superclass of linear Traversable. The reason for that is Traversable using a Control.Applicative instead of Data.Applicative (#126 (comment)).

• We do not want reverting Traversable to use Data.Applicative instead, since it is a less common occurence.
• We explored adding a method using Data.Applicative's to Foldable, but then we are losing a few useful Foldable instances (Implement Data.{List,Foldable}.Linear #126 (comment))

In short, the current state is that we have Foldable and Traversable classes but neither imply the other.

There are a few other minor discussions, mainly about choosing between alternative signatures; but we made some decisions there, and as @facundominguez said before we have some use cases it's difficult to choose between them (#126 (comment)).

One of my concerns we haven't addressed is this:

Data.List comes with a lot of rewrite rules and annotations to make sure that the operations fuse. Replicating those might end up being a lot of work, especially since I do not completely understand how they work. In some cases we can't even Unsafe.toLinear them since our semantics are a bit different (we need to call lseq to forget the unused elements). So, this PR just implements the simplest versions.

If all above is good, I think this PR is good to merge (I can fix the conflicts when it's good to go). We can always revisit these decisions.

We do not want reverting Traversable to use Data.Applicative instead, since it is a less common occurence.

I found yesterday that this would have been useful to define

instance Dupable a => Dupable (Array a) where
  dupV = traverse dupV

Currently fails with

    • Could not deduce (linear-base-0.1.0.0:Control.Monad.Linear.Internal.Applicative
                          (V n))
        arising from a use of ‘traverse’

We explored adding a method using Data.Applicative's to Foldable, but then we are losing a few useful Foldable instances (#126 (comment))

We are losing instances, yes, but I'm not sure that we concluded that they were useful.

Maybe we just need the data-applicative-wise traversable in addition to all this. But, to be honest, I've never regarded Foldable as more than a historical type class with not a lot of meaning. Whereas data-applicable-wise traversable would make more sense to me. @mboes do you have an opinion on this matter?

Maybe we just need the data-applicative-wise traversable in addition to all this. But, to be honest, I've never regarded Foldable as more than a historical type class with not a lot of meaning. Whereas data-applicable-wise traversable would make more sense to me.

I agree with this. So here's an idea. Let's side-step this discussion by removing Foldable from the equation entirely. I can modify this PR to just work on lists, putting everything in Data.List.Linear. This would already ease the pain of not having those utility functions, since most of our collections expose a toList method (of course, Foldable is just a glorified toList function). With the added advantage that we can merge this sooner.

I am convinced that we will end up having a variant of Traversable-with-data-applicatives, so lets make a separate issue to discuss that (or if we indeed want Foldable).

I am convinced that we will end up having a variant of Traversable-with-data-applicatives

Me too. It does seem increasingly unavoidable.

Ok for making this a list-only issue and merging fast.

I'm closing this PR in favour of #189, and we can continue the traversable discussion at #190.