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

[Carter Schonwald]

Yeah, mapM is semantically different from traverse.  So dropping mapm seems
ill advised.

@david: is there an analogue for sequence?

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

> In light of this example, I oppose the proposal.
>
> On Sat, Nov 7, 2020, 5:04 PM David Feuer <david.feuer at 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 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
>>>>
>>> _______________________________________________
> 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/cdfa5154/attachment.html>