In light of this example, I oppose the proposal.

On Sat, Nov 7, 2020, 5:04 PM David Feuer <david.feuer@gmail.com> wrote:

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:

> Due to the nature of the Applicative and 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 and Alternative, please prefer Control.Monad.Combinators 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

_______________________________________________
Libraries mailing list
Libraries@haskell.org
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries