I was hoping that in GHC 7.10 we would make mapM = traverse for lists, but it appears this isn't the case: the Traversable instance for lists overrides mapM to be the manually-defined version in terms of foldr. Why is this? Fusion? Unfortunately since I want mapM = traverse (for Haxl) I'll need to continue to redefine it in our custom Prelude. Cheers, Simon
The reason I know of why mapM wasn't just made to be an alias for traverse (assuming that's what you mean) was that it was thought that particular definitions of mapM could be more efficient than traverse. For instance: mapM :: Monad m => (a -> m b) -> [a] -> m [b] mapM f = go [] where go ys [] = return (reverse ys) go ys (x:xs) = f x >>= \y -> go (y:ys) xs This doesn't use stack for m = IO, for instance. However, it has since been pointed out (to me and Ed, at least), that this matters much less now. Stack overflows are now off by default, and if you measure the overall time and memory usage, traverse compares favorably to this custom mapM. So, as long as stack isn't an artificially scarce resource, there's no reason to keep them distinct. We didn't know this until after 7.10, though. If you're just asking why the definition of 'mapM' for lists isn't 'traverse' with a more specific type, I don't know the answer to that. -- Dan On Mon, May 11, 2015 at 3:15 PM, Simon Marlow <marlowsd@gmail.com> wrote:
I was hoping that in GHC 7.10 we would make mapM = traverse for lists, but it appears this isn't the case: the Traversable instance for lists overrides mapM to be the manually-defined version in terms of foldr.
Why is this? Fusion?
Unfortunately since I want mapM = traverse (for Haxl) I'll need to continue to redefine it in our custom Prelude.
Cheers, Simon _______________________________________________ Libraries mailing list Libraries@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
On 11/05/2015 22:41, Dan Doel wrote:
The reason I know of why mapM wasn't just made to be an alias for traverse (assuming that's what you mean) was that it was thought that particular definitions of mapM could be more efficient than traverse. For instance:
mapM :: Monad m => (a -> m b) -> [a] -> m [b] mapM f = go [] where go ys [] = return (reverse ys) go ys (x:xs) = f x >>= \y -> go (y:ys) xs
This doesn't use stack for m = IO, for instance.
However, it has since been pointed out (to me and Ed, at least), that this matters much less now. Stack overflows are now off by default, and if you measure the overall time and memory usage, traverse compares favorably to this custom mapM. So, as long as stack isn't an artificially scarce resource, there's no reason to keep them distinct. We didn't know this until after 7.10, though.
If you're just asking why the definition of 'mapM' for lists isn't 'traverse' with a more specific type, I don't know the answer to that.
Yes, I'm not really concerned that mapM is a method of Traversable rather than just being an alias for traverse, but I'm wondering why we define it in the list instance rather than using the default. Cheers, Simon
-- Dan
On Mon, May 11, 2015 at 3:15 PM, Simon Marlow <marlowsd@gmail.com <mailto:marlowsd@gmail.com>> wrote:
I was hoping that in GHC 7.10 we would make mapM = traverse for lists, but it appears this isn't the case: the Traversable instance for lists overrides mapM to be the manually-defined version in terms of foldr.
Why is this? Fusion?
Unfortunately since I want mapM = traverse (for Haxl) I'll need to continue to redefine it in our custom Prelude.
Cheers, Simon _______________________________________________ Libraries mailing list Libraries@haskell.org <mailto:Libraries@haskell.org> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Okay. I talked with some folks, and I now understand why this matters for you. I can't think of a fusion reason for the custom definition. traverse is a foldr same as the particular mapM. I think it's just an oversight. Since the type doesn't even change, we should be able to fix this in 7.10.2, no? On Tue, May 12, 2015 at 3:58 AM, Simon Marlow <marlowsd@gmail.com> wrote:
On 11/05/2015 22:41, Dan Doel wrote:
The reason I know of why mapM wasn't just made to be an alias for traverse (assuming that's what you mean) was that it was thought that particular definitions of mapM could be more efficient than traverse. For instance:
mapM :: Monad m => (a -> m b) -> [a] -> m [b] mapM f = go [] where go ys [] = return (reverse ys) go ys (x:xs) = f x >>= \y -> go (y:ys) xs
This doesn't use stack for m = IO, for instance.
However, it has since been pointed out (to me and Ed, at least), that this matters much less now. Stack overflows are now off by default, and if you measure the overall time and memory usage, traverse compares favorably to this custom mapM. So, as long as stack isn't an artificially scarce resource, there's no reason to keep them distinct. We didn't know this until after 7.10, though.
If you're just asking why the definition of 'mapM' for lists isn't 'traverse' with a more specific type, I don't know the answer to that.
Yes, I'm not really concerned that mapM is a method of Traversable rather than just being an alias for traverse, but I'm wondering why we define it in the list instance rather than using the default.
Cheers, Simon
-- Dan
On Mon, May 11, 2015 at 3:15 PM, Simon Marlow <marlowsd@gmail.com <mailto:marlowsd@gmail.com>> wrote:
I was hoping that in GHC 7.10 we would make mapM = traverse for lists, but it appears this isn't the case: the Traversable instance for lists overrides mapM to be the manually-defined version in terms of foldr.
Why is this? Fusion?
Unfortunately since I want mapM = traverse (for Haxl) I'll need to continue to redefine it in our custom Prelude.
Cheers, Simon _______________________________________________ Libraries mailing list Libraries@haskell.org <mailto:Libraries@haskell.org> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
On Tue, May 12, 2015 at 3:58 AM, Simon Marlow <marlowsd@gmail.com> wrote:
Yes, I'm not really concerned that mapM is a method of Traversable rather than just being an alias for traverse, but I'm wondering why we define it in the list instance rather than using the default.
We were pretty paranoid about introducing space or time regressions and didn't have a proof that we wouldn't introduce them by changing something there, so we left it alone. -Edward
On 12/05/2015 15:26, Edward Kmett wrote:
On Tue, May 12, 2015 at 3:58 AM, Simon Marlow <marlowsd@gmail.com <mailto:marlowsd@gmail.com>> wrote:
Yes, I'm not really concerned that mapM is a method of Traversable rather than just being an alias for traverse, but I'm wondering why we define it in the list instance rather than using the default.
We were pretty paranoid about introducing space or time regressions and didn't have a proof that we wouldn't introduce them by changing something there, so we left it alone.
Ok good, so it looks like the answer is "we could change it, but benchmark first". I can do that. Thanks! Cheers, Simon
We managed to show that the old counter-example of a mapM that works where traverse that would blow the stack isn't an issue since https://ghc.haskell.org/trac/ghc/ticket/8189 was resolved. Consequently, we're looking at removing mapM entirely from the class and just making it a top level definition. To do that we'd need to deprecate redefinition of the method in instances for a version or two. This would need a new form of deprecation, where you deprecate redefinition but not use of a member of a class. (I think Herbert filed an issue to create it, but I can't find it off hand.) Once we can make that transition, then the constraints on mapM would relax to the same as those for traverse. That would fix both the constraints and the implementation going forward for everything, but we should probably handle this particular case first or you won't see any benefit for a couple of years. -Edward On Tue, May 12, 2015 at 11:58 AM, Simon Marlow <marlowsd@gmail.com> wrote:
On 12/05/2015 15:26, Edward Kmett wrote:
On Tue, May 12, 2015 at 3:58 AM, Simon Marlow <marlowsd@gmail.com <mailto:marlowsd@gmail.com>> wrote:
Yes, I'm not really concerned that mapM is a method of Traversable rather than just being an alias for traverse, but I'm wondering why we define it in the list instance rather than using the default.
We were pretty paranoid about introducing space or time regressions and didn't have a proof that we wouldn't introduce them by changing something there, so we left it alone.
Ok good, so it looks like the answer is "we could change it, but benchmark first". I can do that. Thanks!
Cheers, Simon
On 2015-05-12 at 18:10:31 +0200, Edward Kmett wrote: [...]
Consequently, we're looking at removing mapM entirely from the class and just making it a top level definition.
To do that we'd need to deprecate redefinition of the method in instances for a version or two. This would need a new form of deprecation, where you deprecate redefinition but not use of a member of a class. (I think Herbert filed an issue to create it, but I can't find it off hand.)
https://ghc.haskell.org/trac/ghc/ticket/10071 [...] Cheers, hvr
On Tue, May 12, 2015 at 2:15 AM, Simon Marlow <marlowsd@gmail.com> wrote:
Unfortunately since I want mapM = traverse (for Haxl) I'll need to continue to redefine it in our custom Prelude.
Apologies if I'm missing context, but what about replacing mapM with traverse in the source code? What problems do the additional polymorphism create? -- Kim-Ee
On 12/05/2015 04:33, Kim-Ee Yeoh wrote:
On Tue, May 12, 2015 at 2:15 AM, Simon Marlow <marlowsd@gmail.com <mailto:marlowsd@gmail.com>> wrote:
Unfortunately since I want mapM = traverse (for Haxl) I'll need to continue to redefine it in our custom Prelude.
Apologies if I'm missing context, but what about replacing mapM with traverse in the source code?
What problems do the additional polymorphism create?
We could do that, but this is a DSL we provide to users who are in most cases not native Haskell programmers and the idea is to keep things as simple as possible. So we wanted to standardise on either mapM or traverse, and since mapM is more familiar (and appears in books etc.) we went with mapM. I'd also been assuming that the issue would go away in 7.10 because mapM would be equivalent to traverse. Cheers, Simon
I'm going to submit a ticket for this. However, I have a related question: Do you care about mapM_? Right now it's defined as: mapM_ f = foldr ((>>) . f) (return ()) whereas it could be: mapM_ = traverse_ Does this not affect you in the same way (because (>>) allows the same optimization as Applicative)? Or does this also need to be addressed? -- Dan On Mon, May 11, 2015 at 3:15 PM, Simon Marlow <marlowsd@gmail.com> wrote:
I was hoping that in GHC 7.10 we would make mapM = traverse for lists, but it appears this isn't the case: the Traversable instance for lists overrides mapM to be the manually-defined version in terms of foldr.
Why is this? Fusion?
Unfortunately since I want mapM = traverse (for Haxl) I'll need to continue to redefine it in our custom Prelude.
Cheers, Simon _______________________________________________ Libraries mailing list Libraries@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Yes, we also need mapM_ = traverse_. Simon On 26/05/2015 21:59, Dan Doel wrote:
I'm going to submit a ticket for this. However, I have a related question:
Do you care about mapM_? Right now it's defined as:
mapM_ f = foldr ((>>) . f) (return ())
whereas it could be:
mapM_ = traverse_
Does this not affect you in the same way (because (>>) allows the same optimization as Applicative)? Or does this also need to be addressed?
-- Dan
On Mon, May 11, 2015 at 3:15 PM, Simon Marlow <marlowsd@gmail.com <mailto:marlowsd@gmail.com>> wrote:
I was hoping that in GHC 7.10 we would make mapM = traverse for lists, but it appears this isn't the case: the Traversable instance for lists overrides mapM to be the manually-defined version in terms of foldr.
Why is this? Fusion?
Unfortunately since I want mapM = traverse (for Haxl) I'll need to continue to redefine it in our custom Prelude.
Cheers, Simon _______________________________________________ Libraries mailing list Libraries@haskell.org <mailto:Libraries@haskell.org> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
participants (5)
-
Dan Doel -
Edward Kmett -
Herbert Valerio Riedel -
Kim-Ee Yeoh -
Simon Marlow