<div dir="ltr">At the very least, it does seem like we're going to need to do a broader survey of the instances out there, as well as fix a lot more Applicative instances to have a better (*>) first as well as thoroughly document what to do, if we want to proceed on this front.<div><br></div><div>If we ultimately want to remove mapM from the class to get it a more permissive type signature, and get mapM_ from Foldable to have the more general signature to boot, then we'll need to figure out how to address these concerns.</div><div><div><br></div><div>It still strikes me as the right general direction to go in, but this is troubling.</div><div><br></div><div>-Edward</div></div></div><div class="gmail_extra"><br><div class="gmail_quote">On Mon, Aug 3, 2015 at 12:33 PM, Ben Gamari <span dir="ltr"><<a href="mailto:ben@well-typed.com" target="_blank">ben@well-typed.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><span class="">Edward Kmett <<a href="mailto:ekmett@gmail.com">ekmett@gmail.com</a>> writes:<br>
<br>
> On Tue, May 12, 2015 at 3:58 AM, Simon Marlow <<a href="mailto:marlowsd@gmail.com">marlowsd@gmail.com</a>> wrote:<br>
><br>
>><br>
>> Yes, I'm not really concerned that mapM is a method of Traversable rather<br>
>> than just being an alias for traverse, but I'm wondering why we define it<br>
>> in the list instance rather than using the default.<br>
>><br>
><br>
> We were pretty paranoid about introducing space or time regressions and<br>
> didn't have a proof that we wouldn't introduce them by changing something<br>
> there, so we left it alone.<br>
><br>
</span>On a related note, D924 [1] proposed that mapM_ be redefined in<br>
terms of traverse_. Unfortunately at least one monad in GHC itself was<br>
adversely affected [2] by this change, resulting in non-linear complexity in<br>
a previously well-behaved function (a minimal demonstration of this can<br>
be found below).<br>
<br>
We discussed this in the GHC weekly meeting and felt that we should<br>
ensure that the libraries group was aware of this issue.<br>
<br>
Cheers,<br>
<br>
- Ben<br>
<br>
<br>
[1] <a href="https://phabricator.haskell.org/D924" rel="noreferrer" target="_blank">https://phabricator.haskell.org/D924</a><br>
[2] <a href="https://ghc.haskell.org/trac/ghc/ticket/10711" rel="noreferrer" target="_blank">https://ghc.haskell.org/trac/ghc/ticket/10711</a><br>
[3] Demonstration of regression in complexity of mapM_ when expressed in<br>
terms of `traverse_`,<br>
<br>
{{{<br>
module Main where<br>
<br>
import Control.Monad hiding (mapM_)<br>
import Prelude hiding (mapM_)<br>
<br>
-- | Testcase derived from Assembler monad in ByteCodeAsm<br>
data Assembler a<br>
= Thing Int (Int -> Assembler a)<br>
| Pure a<br>
<br>
instance Functor Assembler where<br>
fmap = liftM<br>
<br>
instance Applicative Assembler where<br>
pure = return<br>
(<*>) = ap<br>
<br>
instance Monad Assembler where<br>
return = Pure<br>
Pure x >>= f = f x<br>
Thing i k >>= f = Thing i (k >=> f)<br>
<br>
-- This is traverse_<br>
mapA_ :: (Foldable t, Monad f) => (a -> f b) -> t a -> f ()<br>
mapA_ f = foldr ((*>) . f) (pure ())<br>
<br>
-- This is the current definition<br>
mapM_ :: (Foldable t, Monad f) => (a -> f b) -> t a -> f ()<br>
mapM_ f = foldr ((>>) . f) (pure ())<br>
<br>
test = map (\i->Thing i (const $ return 2)) [0..10000]<br>
<br>
doTestM = mapM_ id test<br>
doTestA = mapA_ id test<br>
<br>
run :: Assembler a -> a<br>
run (Thing i f) = run (f i)<br>
run (Pure r) = r<br>
{-# NOINLINE run #-}<br>
<br>
main :: IO ()<br>
main = print $ run doTestM<br>
}}}<br>
<span class="HOEnZb"><font color="#888888"><br>
--<br>
You received this message because you are subscribed to the Google Groups "haskell-core-libraries" group.<br>
To unsubscribe from this group and stop receiving emails from it, send an email to <a href="mailto:haskell-core-libraries%2Bunsubscribe@googlegroups.com">haskell-core-libraries+unsubscribe@googlegroups.com</a>.<br>
For more options, visit <a href="https://groups.google.com/d/optout" rel="noreferrer" target="_blank">https://groups.google.com/d/optout</a>.<br>
</font></span></blockquote></div><br></div>