Generalize Wander

[zrho]

Obviously, we need a good story for traversals. Currenty, there is the Wander type class, that allows to lift a traversable functor into the profunctor. While this looks quite neat and similar to Choice and Strong, I think it is a bit restrictive: Sometimes, you have a traversal that only works for fixed types, e.g. with monomorphic containers. I would propose generalizing Wander to the following (admittedly quite ugly) type:

class (Strong p, Choice p) <= Wander p where
  wander
    :: forall s t a b. (forall f. (Applicative f) => (a -> f b) -> s -> f t)
    -> p a b -> p s t

Here, wander is the inverse to traverseOf. The original function can be recovered by applying traverse from Data.Traversable as the first argument. Function and Star f for Applicatives f can be generalized to this new definition:

instance wanderFunction :: Wander Function where
  wander t p = runIdentity <<< t (Identity <<< p)

instance wanderStar :: (Applicative f) => Wander (Star f) where
  wander t = Star <<< t <<< runStar

What do you think?

[paf31]

It certainly seems like an improvement to me. Is it possible to generalize the existing instances of Wander to this (e.g. UI)? Seems everything else should go through since from the caller side, traverse is more specific than the new argument.

@ekmett Do you have any thoughts on this representation as opposed to Wander given the type system constraints?

[zrho]

If a profunctor p is an instance of Wander in the new form, wander and traverseOf establish that p is represented by some applicative functor, which is one definition of a traversable. wander captures this existential with the rank-2 type.

UI was the motivation for this change, because I thought UI eff v s t was represented as a profunctor by Sink eff v. If s and t differ, this seems to be a bit problematic, though: I have not yet been able to get an iso UI eff v s t =~= s -> Sink eff v t. I will investigate this further.

[ekmett]

Strong makes sense as a superclass. Choice doesn't fit with the semantics of Wander, does it?

[ekmett]

As for using the rank-2 type, you're basically just asking for a traversal as an argument, so it is equally expressive. It actually looks half-way decent to me.

[paf31]

@zrho I don't think UI is representable. Star Sink is bigger due to the extra a which is necessary to keep the most recent state of the other components. If you add the a to UI instead, you have to make an arbitrary choice which one to keep in mappend. This is why I only convert to Sink inside traversal right now.

[zrho]

Indeed. We might use a super-class for this restricted case, that only allows to lift monomorphic traversals and have it be the super-class of Wander:

-- TODO: find a proper name
class (Strong p) => WanderMono p where
  wanderMono :: (forall f. Applicative f => (a -> f a) -> s -> f s) -> p a a -> p s s

(EDIT: Strong instead of Choice as super-class)

Then UI eff v is an instance of that at least.

[ekmett]

Where do these Choice constraints keep coming from?

[zrho]

The last one was a typo, I wanted to remove Choice and keep Strong :)

[ekmett]

Whew. I was worried I was missing something obvious. =)

[zrho]

I've hacked around a bit and noticed that Choice for Star f used the pure part of Applicative f, but not the <*> part. This makes intuitive sense: Viewing a prism for a type a where a is a monoid must have a default value (mempty), yet not concern itself with appending multiple values.

After a bit of tinkering, I found that Star f supported a function Star f a b -> Star f c d -> Star f (a, c) (b, d) that used <*> if f is Applicative, combining results. Indeed, strong choice profunctors that support such a function can be used for traversals. In Haskell code:

-- Choice intentional this time ;)
class (Strong p, Choice p) => Traversing p where
  both :: p a b -> p c d -> p (a, c) (b, d)

instance Applicative f => Traversing (Star f) where
  both p q = Star $ \(a, c) -> (,) <$> runStar p a <*> runStar q c

Then for lists and a slow proof-of-concept implementation for arbitary traversals:

list :: (Traversing p) => p a b -> p [a] [b]
list p = dimap toCons fromCons $ right' $ both p (list p) where
  toCons []     = Left ()
  toCons (x:xs) = Right (x, xs)
  fromCons = either (const []) (uncurry (:))

wander
  :: Traversing p => (forall f. Applicative f => (a -> f b) -> s -> f t)
  -> Optic p s t a b
wander tr p = dimap (id &&& getParts) (uncurry setParts) $ second' (list p) where
  setParts s bs = runIdentity $ unsafePartsOf' tr (\_ -> Identity bs) s
  getParts s = getConst $ unsafePartsOf' tr Const s

This could probably be made fast(er) by avoiding lists and doing this with a Bazaar directly; I didn't have time to investigate that yet.

Conversion back to an ordinary traversal can be done with:

traverseOf' :: Applicative f => Optic (Star f) s t a b -> (a -> f b) -> s -> f t
traverseOf' = dimap Star runStar

I tried it out on lists and it worked quite fine. Is there something obviosuly wrong with this? Can it be made fast?

[ekmett]

@zrho: I've explored this design too. It is, unfortunately, really slow. =(

The both combinator you give there is (***) Control.Arrow, but limited to just a profunctor.

Note you don't need both Strong and Choice for it to be a definable thing. e.g. There are a lot of Arrow instances that are not ArrowChoice instances, so Choice is rather too strong a superclass here.

Moreover, in the arrow case a Strong superclass there is motivated by the fact that you can define first and second by using id as the other argument, but in the Profunctor case that isn't available to us.

This is actually an orthogonal direction of additional capabilities with respect to Strong and Choice.

[xplat]

@zrho:

(<***>) :: p a (b -> c) -> p a b -> p a c

is equivalent over Profunctor p to your both and might be faster. Also, it should come along with

konst :: b -> p a b
-- or
none :: p () ()

which are also equivalent. Together (and with Profunctor p superclass) they form an endoprofunctor-equivalent of Applicative.

[xplat]

I just noticed that in (<***>) / konst form the class is entirely the same as (Profunctor p, Applicative (p a)). I thought of this class starting with monoids for a "parallel wires" extension of Day convolution for endoprofunctors, but it just happens to turn out equivalent to a set of monoids for pointwise Day convolution. Whodathunk.

[zrho]

The Choice superclass is haunting me. Ideally, we would want all our prisms to be traversals, but if Choice is not a superclass of Wander, this is not the case. This seems pretty clear but I failed to recognize that until I tried to compile

bars :: forall a b. Traversal (Foo a) (Foo b) a b
bars = foo <<< _Just <<< bar <<< traversed

from the test file where the compiler complains about a missing choice constraint.

[ekmett]

Having just the ability to do both isn't enough to build a traversal. you need both that and sums, so a traversal would have two constraints.

[paf31]

My intuition is that both is like composing two profunctor diagrams in parallel, but you still need the ability to compose zero things.

[ekmett]

To show that there is a reason for having this distinction, if you have a single fixed shape with one or more entries, then 'both' is enough to handle it. Representable functors are such an example.

[ekmett]

The remaining issue is what @paf31 just mentioned, the need to handle an empty structure.

[zrho]

Sure. I was referring to the original formulation

class (Strong p, Choice p) <= Wander p where
  wander
    :: forall s t a b. (forall f. (Applicative f) => (a -> f b) -> s -> f t)
    -> p a b -> p s t

where we thought the Choice constraint was erroneous. I should have made that clear, that is not at all obvious from my post, I see.

[ekmett]

You wound up needing Choice to implement the [] traversal because you have two cases to deal with (:) and []. On the other hand, both can handle (,) on its own. Walking that is easier because it has a fixed shape.

[ekmett]

It seems to me that the definition for a traversal would be something like:

type Traversal s t a b = forall p. (Choice p, Strong p, Wander p) => p a b -> p s t

as Wander is a case that can be disconnected from the rest. With just Strong and Choice you are limited to affine traversals, and we've shown things like both that can be walked with just Wander.

(Wander also needs a unit traversal though)

[zrho]

Ah, I see. What do you mean with the unit traversal?

[ekmett]

data Proxy a = Proxy

How do we write the Traversable instance for Proxy using the building blocks thus far?

[zrho]

I think we are getting confused over the two formulations, one with both and one with wander :: (forall f. Applicative f => (a -> f b) -> s -> f t) -> p a b -> p s t. You mean something like konst or none in addition to both, like @xplat noted? Yes, that is neccessary; did you mean that? I do not see how the latter one with wander would need a unit traversal. I thought we have already rejected the both approach for performance reasons?

[ekmett]

Yes. All of my comments for the last hour or two have pertained to the both based formulation.

[ekmett]

I've been continuing the discussion there because I think it does shine some light on different portions of the design space, so I'm not completely dismissing it out of hand.

Being able to talk about things with 'fixed representable shape' (only a Wander constraint) separately from 'affine traversals' (Choice + Strong) separately from 'traversals' (Choice + Strong + Wander) separately from things with 'fixed shape' (Wander + Strong) and separately from things with variable shape but no extra 'data' (Wander + Choice) leads to interesting divisions in the abstraction that the current formulation ignores. If you further split Wander up into its current semigroup-like structure and then add a separate unit to it only via a subclass, then you can also talk meaningfully about relevant traversals (with a guaranteed 1 or more targets).

[paf31]

Closing this since the new representation seems to handle things like (,) nicely, but I'm also interested to hear more about Both.

[paf31]

One small observation (possibly useful, possibly not): both could have the more generic type

both :: forall b x y z w. (Bifunctor b) => p x y -> p z w -> p (b x z) (p z w)

which subsumes ||| and *** and gives a general sort of "parallel composition" of profunctors.

Another thought: if both is too slow because we have to convert traversals to nested pairs and back, why not start from traversals in terms of both, and define Traversable in terms of Traversal? E.g. https://gist.github.com/paf31/15800b8a1cd01368c012 Surely this is much easier in PureScript than in Haskell.

[ekmett]

I've started using a form of 'wander' in profunctors HEAD:

https://github.com/ekmett/profunctors/blob/4ce324fabf2492638fb431707d40a6b10a0eee2c/src/Data/Profunctor/Traversing.hs#L85

It showcases the benefit of defining things in terms of wander over traverse'.

[masaeedu]

I'm not sure what the conclusion here was. Wouldn't adding something like WanderMono as proposed above, and then using that as a constraint for Traversal's be a good idea?

I have a type that can implement (forall f. Applicative f => (a -> f a) -> (s -> f s)) -> P a a -> P s s, but not the more general a b s t version. As far as I understand all the Traversal's in the library don't really need the full generality of a Wander constraint, and would be happy with the WanderMono constraint I can satisfy.

[masaeedu]

Hmm. Actually, wouldn't WanderMono be Fold?