I don't know about measurements or anything. There are certainly *implementation strategies* for mapM that don't translate well to traverse. Imagine a queue, for example. One way to write mapM is this: mapM f = go empty where go !acc xs = case uncons xs of Just (x, xs') -> do y <- f x go (acc `snoc` y) Nothing -> pure acc There's no way to do anything operationally equivalent with just Applicative. Is this a good way to write it? Well, that presumably depends on the queue and on the Monad, but I'd give it a good "possibly". On Sat, Nov 7, 2020, 3:42 PM A S <masaeedu@gmail.com> wrote:
Personally I would love to know of some kind of reasoning regarding these things, as I'm not aware of any! (efficiency of Applicative vs Monad based functions)
I agree. I'd be very interested in seeing an example (contrived or otherwise) of a specific Monad which is necessarily more efficient to `mapM` over some arbitrarily selected Traversable container than to `traverse`. That would be a good first step I think.
On Sat, Nov 7, 2020 at 3:29 PM Georgi Lyubenov <godzbanebane@gmail.com> wrote:
Hi!
Regarding the "there can be no instance for which mapM is more efficient than traverse": There have been issues with Applicative functions leaking memory where Monad ones aren't in Polysemy - some of these have been fixed, but it's not clear that there are none left. There is also this claim in parser-combinators <https://hackage.haskell.org/package/parser-combinators-1.2.1/docs/Control-Applicative-Combinators.html> :
Due to the nature of the Applicative <https://hackage.haskell.org/package/base-4.12.0.0/docs/Control-Applicative.html#t:Applicative> and Alternative <https://hackage.haskell.org/package/base-4.12.0.0/docs/Control-Applicative.html#t:Alternative> abstractions, they are prone to memory leaks and not as efficient as their monadic counterparts. Although all the combinators we provide in this module are perfectly expressible in terms of Applicative <https://hackage.haskell.org/package/base-4.12.0.0/docs/Control-Applicative.html#t:Applicative> and Alternative <https://hackage.haskell.org/package/base-4.12.0.0/docs/Control-Applicative.html#t:Alternative>, please prefer Control.Monad.Combinators <https://hackage.haskell.org/package/parser-combinators-1.2.1/docs/Control-Monad-Combinators.html> instead when possible.
I have not verified it, but it is a bit worrying.
Personally I would love to know of some kind of reasoning regarding these things, as I'm not aware of any! (efficiency of Applicative vs Monad based functions)
====== Georgi _______________________________________________ Libraries mailing list Libraries@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries