On Sat, Nov 20, 2010 at 8:08 PM, Ross Paterson <ross@soi.city.ac.uk> wrote:
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 <dave@zednenem.com> <http://www.eyrie.org/~zednenem/>