Proposal: Move `mapM` and `sequence` out of Traversable

[David Feuer]

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 at 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 at 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 at haskell.org
>> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/libraries/attachments/20201107/6ea03f4d/attachment.html>