replicateM space leak with lists

See mater ticket #1168

Summary

base:Control.Monad.replicateM uses too much memory when m a = [a] and the arguments are not small.

Steps to reproduce

import Control.Monad (replicateM)

shapes bias p =
  [ s
  | m <- [0 .. p]
  , s <- replicateM (fromInteger m + 2) [1 .. p]
  , p == sum (zipWith (*) (map (bias +) s) (tail s))
  ]

main = mapM_ (print . length . shapes 0) [1..10]

uses 500MB after 1min wall-clock time, and eventually gets OOM-killed on a 32GB desktop.

Expected behavior

Run to completion using small constant space.

Probable cause

liftA2 (:) f (loop (cnt - 1)) retaining in memory the result of the recursive call to use for each element of the list f, which at top level has size (length f)^(n - 1).

Possible solution

I wrote an alternative implementation solves this for me in my use case, very happy to donate it to this project but I don't know:

2. whether it is more frugal for all m
3. whether it is correct for all m, or even for m = []
4. whether it is faster for all m.

It is certainly much more complicated than the current implementation, and I don't know fully how/why it works so effectively.

{-# LANGUAGE ApplicativeDo #-}
replicateM' :: Applicative m => Int -> m a -> m [a]
replicateM' n ls = go n (pure id)
  where
    go n fs
      | n <= 0 = do
          f <- fs
          pure (f [])
      | otherwise = go (n - 1) gs
          where
            gs = do
              f <- fs
              l <- ls
              pure (f . (l:))

Unfortunately I don't have resources at the moment to spend on researching/verifying/proving points 1,2,3 above; I imagine this task would be much easier for a ghc developer who would be familiar with the process involved in swapping the implementation and running the test suite?

More details including heap profile graphs at https://mathr.co.uk/blog/2022-06-25_fixing_replicatem_space_leak.html

Environment

• GHC version used: 8.8.4
• Operating System: Debian Bullseye
• System Architecture: amd64

$ apt-cache policy ghc
ghc:
  Installed: 8.8.4-2
  Candidate: 8.8.4-2
  Version table:
 *** 8.8.4-2 990
        990 http://ftp.uk.debian.org/debian bullseye/main amd64 Packages
        100 /var/lib/dpkg/status

Note: I don't think the replicateM implementation has changed since base-4.13.0.0.