Allow vertical composition of non-overlapping traversals #109

Closed
jwiegley opened this Issue Nov 22, 2012 · 10 comments

Comments

Projects
None yet
4 participants
Collaborator

jwiegley commented Nov 22, 2012

Ok, the non-overlapping constraint can't be checked, but it would be nice to be able to say:

over (_1 <*> _3) (+1) (1,1,1) => (2,1,2)

Where <*> becomes something that actually works. :)

Owner

ekmett commented Nov 22, 2012

I beat my head on this one for an hour or so trying to figure out the right way to implement it to no avail.

I'm going to leave this issue open to remind me that it exists.

ekmett was assigned Nov 22, 2012

Owner

ekmett commented Nov 22, 2012

I think any solution is going to involve getting creative about tying the knot.

For instance, rwbarton smashed together a version of the single-traversal lazy replace-with-max function:

replaceWithMax t s = result where
  (result, Just m) = (`appEndo` Nothing) 
                 <$> runWriter (t (\v -> tell (Endo $ max (Just v)) >> return m) s) 
>>>replaceWithMax both (3,4)
(4,4)

The reasoning in whatever combinator is built may have to be similar.

Owner

ekmett commented Nov 23, 2012

As it turns out, this is impossible. =/

By the time you get done working it out you can't build a 'Traversal', you can only build something like:

type Vertical s t a b = forall m. (Monad m, Applicative m) => (a -> m b) -> s -> m t

This happens because you need to take the entire output from the first Traversal and start a second Traversal on that. If you fmap into the first result, this results in m (m t), for an unknown user-supplied m, which then requires join or (>>=) to forge into the final form.

Even if we allowed for this type it is pretty much useless, since to read from it, you need to use an Accessor, and Accessor provably can't be made into a Monad.

So you can't read and could only barely write to the resulting pseudo-Traversal.

As much as I would love to be able to provide this functionality to the end-user, it is both a theoretical and practical impossibility. =(

ekmett closed this Nov 23, 2012

Collaborator

pthariensflame commented Nov 23, 2012

You could still use Writer, though, and just discard the unnecessary half of the tuple afterwards.

Owner

ekmett commented Nov 23, 2012

Writer doesn't actually work, because that requires the value to be ().

(a -> m ()) -> s -> m t

finishes breaking the rest of the laws for you. ;)

Remember you need to be able to let b = a, s = t, for something to be a valid Lens, Traversal, etc.

The closest thing to that that can fit the laws is an Action. =/

Collaborator

pthariensflame commented Nov 23, 2012

Why does b have to be restricted to () when you could instead just restrict the whole thing to being Simple and just pass the value through unchanged?

Owner

ekmett commented Nov 23, 2012

Good point.

Owner

ekmett commented Nov 23, 2012

I may have to retract the claim that it is not possible to read from and settle for the claim that the resulting pseudo-traversal doesn't interact with the rest of the ecosystem.

On an unrelated note, a variant of upon that took multiple accessors could be made, perhaps to work.

Contributor

sjoerdvisscher commented Nov 23, 2012

This would make SimpleTraversal s a a monoid I think, with ignored as identity.

Owner

ekmett commented Nov 23, 2012

While it would form a Monoid, it only forms a monoid if you ignore the Traversal laws. The composed monoids would have to affect disjoint portions of the structure or you'll have human sacrifice, dogs and cats living together -- mass hysteria.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment