Re: [GHC] #4517: Add Data.Functor.Backwards to transformers
#4517: Add Data.Functor.Backwards to transformers ---------------------------------+------------------------------------------ Reporter: r6 | Owner: Type: proposal | Status: new Priority: normal | Component: libraries (other) Version: 7.0.1 | Keywords: backwards Testcase: | Blockedby: Os: Unknown/Multiple | Blocking: Architecture: Unknown/Multiple | Failure: None/Unknown ---------------------------------+------------------------------------------ Data.Functor.Backwards is a wrapper for functors that allow Foldable, Traversable, and Applicative functors to be operated backwards. It is similar to Dual for Monoids. The Applicative instance runs effects in reversed order. The Foldable instance folds from right to left, The Traversable instance traverses from right to left. -- Russell O'Connor http://r6.ca/ ``All talk about `theft,''' the general counsel of the American Graphophone Company wrote, ``is the merest claptrap, for there exists no property in ideas musical, literary or artistic, except as defined by statute.''
On Sat, Nov 20, 2010 at 05:25:23PM -0500, roconnor@theorem.ca wrote:
Data.Functor.Backwards is a wrapper for functors that allow Foldable, Traversable, and Applicative functors to be operated backwards. It is similar to Dual for Monoids. The Applicative instance runs effects in reversed order. The Foldable instance folds from right to left, The Traversable instance traverses from right to left.
The current version of the module is here: http://hackage.haskell.org/packages/archive/applicative-extras/0.1.6/doc/htm... I think this fits with transformers, and the implementation for Traversable is cute. My only question is whether a constructor that flips Applicatives should be identified with one that reverses the traversal order of containers.
On Sat, Nov 20, 2010 at 8:08 PM, Ross Paterson
On Sat, Nov 20, 2010 at 05:25:23PM -0500, roconnor@theorem.ca wrote:
Data.Functor.Backwards is a wrapper for functors that allow Foldable, Traversable, and Applicative functors to be operated backwards. It is similar to Dual for Monoids. The Applicative instance runs effects in reversed order. The Foldable instance folds from right to left, The Traversable instance traverses from right to left.
The current version of the module is here:
http://hackage.haskell.org/packages/archive/applicative-extras/0.1.6/doc/htm...
I think this fits with transformers, and the implementation for Traversable is cute.
My only question is whether a constructor that flips Applicatives should be identified with one that reverses the traversal order of containers.
I have a library lying around which defines two transformers: Backward
reverses Applicative instances, and Reverse reverses Foldable,
Traversable, Alternative, and MonadPlus instances.
*Reverse> traverse (\x -> pure x <|> pure (x*10)) [1,2] :: [[Int]]
[[1,2],[1,20],[10,2],[10,20]]
*Reverse> runBackward $ traverse (\x -> pure x <|> pure (x*10)) [1,2] :: [[Int]]
[[1,2],[10,2],[1,20],[10,20]]
*Reverse> getReverse $ traverse (\x -> pure x <|> pure (x*10)) [1,2] :: [[Int]]
[[10,20],[10,2],[1,20],[1,2]]
*Reverse> runBackward . getReverse $ traverse (\x -> pure x <|> pure
(x*10)) [1,2] :: [[Int]]
[[10,20],[1,20],[10,2],[1,2]]
I'm not sure how necessary this distinction is. It was based on some
reasonable-seeming laws governing <|>/mplus/mappend and traverse, but
it's really only meaningful for lists (and other sequences which are
isomorphic to lists).
The key code is,
instance Applicative f => Applicative (Backward f) where
pure = Backward . pure
Backward f <*> Backward a = Backward (a <**> f)
instance Traversable f => Traversable (Reverse f) where
traverse f = fmap Reverse . runBackward . traverse (Backward . f)
. getReverse
instance Alternative f => Alternative (Reverse f) where
empty = Reverse empty
Reverse x <|> Reverse y = Reverse (y <|> x)
(It turns out, you can use MonadFix to apply Backward to Monad
instances as well. I'm not sure whether that's guaranteed to be
compatible with the Applicative instance.)
--
Dave Menendez
On Sat, Nov 20, 2010 at 10:17:29PM -0500, David Menendez wrote:
The key code is,
instance Applicative f => Applicative (Backward f) where pure = Backward . pure Backward f <*> Backward a = Backward (a <**> f)
instance Traversable f => Traversable (Reverse f) where traverse f = fmap Reverse . runBackward . traverse (Backward . f) . getReverse
Yes, that's the same as Russell's code.
instance Alternative f => Alternative (Reverse f) where empty = Reverse empty Reverse x <|> Reverse y = Reverse (y <|> x)
Don't you need an Applicative instance for that?
On Sun, Nov 21, 2010 at 6:00 AM, Ross Paterson
On Sat, Nov 20, 2010 at 10:17:29PM -0500, David Menendez wrote:
The key code is,
instance Applicative f => Applicative (Backward f) where pure = Backward . pure Backward f <*> Backward a = Backward (a <**> f)
instance Traversable f => Traversable (Reverse f) where traverse f = fmap Reverse . runBackward . traverse (Backward . f) . getReverse
Yes, that's the same as Russell's code.
Aside from the distinction between Reverse and Backward, yes.
instance Alternative f => Alternative (Reverse f) where empty = Reverse empty Reverse x <|> Reverse y = Reverse (y <|> x)
Don't you need an Applicative instance for that?
Yes. For Reverse, the Functor, Applicative, and Monad instances just
lift the instances of the underlying type. (In fact, I'm not sure why
I wrote them out instead of using newtype deriving.)
--
Dave Menendez
On 11/20/10 10:17 PM, David Menendez wrote:
I have a library lying around which defines two transformers: Backward reverses Applicative instances, and Reverse reverses Foldable, Traversable, Alternative, and MonadPlus instances.
Can I ask that the name Reverse not be used? I have a newtype wrapper for Ord by that name which I'm planning to propose adding to base (in a month or so, once the semester ends so I have the time). I can't think of another good name for the obvious Ord transformer, though there are a few other names which would make sense for Applicatives. -- Live well, ~wren
Can I ask that the name Reverse not be used? I have a newtype wrapper for Ord by that name which I'm planning to propose adding to base (in a month or so, once the semester ends so I have the time). I can't think of another good name for the obvious Ord transformer,
As far as an Ord instance represents a relation, ``Converse'' would be a natural name for something representing the converse relation. Wolfram
On Sat, Nov 20, 2010 at 05:25:23PM -0500, roconnor@theorem.ca wrote:
Data.Functor.Backwards is a wrapper for functors that allow Foldable, Traversable, and Applicative functors to be operated backwards. It is similar to Dual for Monoids. The Applicative instance runs effects in reversed order. The Foldable instance folds from right to left, The Traversable instance traverses from right to left.
It probably should also have an Alternative instance. I expect that wouldn't reverse the order of alternatives: instance (Alternative f) => Alternative (Backwards f) where empty = Backwards empty Backwards x <|> Backwards y = Backwards (x <|> y)
Discussion so far. There are three aspects of functors that can be "reversed" 1. Foldable-Traversable 2. Applicative 3. Alternative-MonadPlus It appears at first glance that all three of these aspects are independent and thus we would need three different wrappers to implement the three separate functionality. For example lists have all three aspects and one can imagine possibly reversing list instances independently in each of the aspects. So far two name are proposed: Backwards and Reverse. There is one request for not using Reverse because someone want to use it to dualize Ord; however it was suggested that Converse be used for Ord. The question of whether 3 is or isn't independent of the other two is made more difficult due to Alternative/MonadPlus not having a clear set of laws. In fact, MonadPlus has two candidate sets of laws that are not compatible with each other. One possibility is to split this proposal into three proposal, one for each of the aspects. I suggest not doing this, or at least not splitting it up yet, since, although these items appear that they can be applied independently, they are still interrelated as one can see by the fact that the Traversable Reverse instance uses the Applicative Reverse instance. -- Russell O'Connor http://r6.ca/ ``All talk about `theft,''' the general counsel of the American Graphophone Company wrote, ``is the merest claptrap, for there exists no property in ideas musical, literary or artistic, except as defined by statute.''
On Tue, Nov 23, 2010 at 11:40:40AM -0500, roconnor@theorem.ca wrote:
Discussion so far.
There are three aspects of functors that can be "reversed"
1. Foldable-Traversable 2. Applicative 3. Alternative-MonadPlus
It appears at first glance that all three of these aspects are independent and thus we would need three different wrappers to implement the three separate functionality. For example lists have all three aspects and one can imagine possibly reversing list instances independently in each of the aspects.
Ignoring 3 for the moment, there are basically two choices: (1) the current design, with a single type constructor that reverses the order of Applicative effects and also the order of Foldable and Traversable: http://hackage.haskell.org/packages/archive/applicative-extras/0.1.6/doc/htm... (2) two type constructors, both with derived Functor instances: * one morally equivalent to reversing the arguments of all the data constructors: Foldable and Traversable process elements in the reverse order, but other instances (Applicative and Monad) are derived. * one with an Applicative instance that reverses the order of effects, but Foldable and Traversable are derived. There wouldn't be a Monad instance, because it's not possible to define one that's compatible with the Applicative instance. The second design seems slightly cleaner to me, though it's not a big deal.
participants (5)
-
David Menendez -
kahl＠cas.mcmaster.ca -
roconnor＠theorem.ca -
Ross Paterson -
wren ng thornton