De-generalise replicateM (and possibly other things), and add replicateA, etc.
Edit: I thought I knew what was going on here, but now that I'm trying to construct a minimal example, I'm less certain. I'll reopen if I manage to figure it out.
Motivation
Just now, we had a beginner on #haskell with an issue of space performance in their seemingly straightforward program to generate a bunch of passwords and hash them all to do a brute force search (for a homework exercise). The program was using replicateM
with the list monad to generate a list of the passwords to search through. It was eventually discovered that the problem was caused by the generalisation of replicateM
to Applicative
: since the recursive application of replicateM (n-1)
is no longer underneath a lambda, the large list generated by it is naturally retained and shared between each of the choices made for the first element of the list. Rewriting replicateM
in the obvious way using the Monad
operations fixed the issue.
This is obviously a disaster, and issues like this may be causing all sorts of unknown performance regressions in older applications and libraries.
Proposal
It seems like it would be a good idea, at least for replicateM
and replicateM_
, if not a number of other similar functions with M in their name whose existence I'm uncertain of, to back off of the generalisation to Applicative
, and invent "-A" suffixed versions which work using Applicative
to replace any occurrences where the generalisation is important.
These are really just two entirely different algorithms with different performance characterstics, and the difference in space and time performance can be dramatic depending on what any given program needs. In other cases, the sharing/retention of replicateA
(i.e. the current implementation of replicateM
) might be useful, and of course, in some cases, the generalisation is necessary, so having such a thing around would be desirable, but overwriting replicateM
seems to have been problematic.