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

[David Feuer]

Off the top of my head, I can't think of anything about sequence or
sequenceA to justify their existence as class methods from the standpoint
of practical programming. I could imagine they might be helpful to
beginners who may find it easier to think about a container full of actions
than about a container full of elements and a function that can be applied
to them to get actions. But it's also not clear to me that removing methods
is very valuable unless either:

1. We get down to just one method, which can be good for performance with
non-regular types, or

2. We end up with a class that works with GND/DerivingVia, such as

  class (Foldable t, Functor t) => Traversable t where
    mapTraverse :: Applicative f => (t b -> r) -> (a -> f b) -> t a -> f r

The one-method bonus can generally be worked around with auxiliary classes
in the rare cases where it comes up, so I wouldn't worry about that too
much here.

On Sat, Nov 7, 2020, 9:47 PM Carter Schonwald <carter.schonwald at gmail.com>
wrote:

> 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/524959ea/attachment-0001.html>