performance - 为什么 `filterM + mapM_`比 `mapM_ + when`慢得多，且列表很大？

Question

我对Haskell优化在内部的工作方式不太了解，但我一直在使用过滤器，希望它们可以被优化为等效于C++的简单过滤器。例如

mapM_ print $ filter (\n -> n `mod` 2 == 0) [0..10]

将编译为

for (int i = 0; i < 10; i++)
    if (i%2 == 0)
        printf("%d\n", i);

对于长列表(10000万个元素)，对于基本的 filter似乎是正确的，但是如果我使用monadic filterM，则会有很大的不同。我为此速度测试编写了一段代码，很明显，与使用 filterM的更强制性方法相比， when的使用时间更长(250倍)。

import Data.Array.IO
import Control.Monad
import System.CPUTime

main :: IO ()
main = do
  start <- getCPUTime
  arr <- newArray (0, 100) 0 :: IO (IOUArray Int Int)
  let
    okSimple i =
      i < 100

    ok i = do
      return $ i < 100
    -- -- of course we don't need IO for a simple i < 100
    -- -- but my goal is to ask for the contents of the array, e.g.
    -- ok i = do
    --   current <- readArray arr (i `mod` 101)
    --   return$ i `mod` 37 > current `mod` 37
    
    write :: Int -> IO ()
    write i =
      writeArray arr (i `mod` 101) i

    writeIfOkSimple :: Int -> IO ()
    writeIfOkSimple i =
      when (okSimple i) $ write i

    writeIfOk :: Int -> IO ()
    writeIfOk i =
      ok i >>= (\isOk -> when isOk $ write i)

  -------------------------------------------------------------------
  ---- these four methods have approximately same execution time ----
  ---- (but the last one is executed on 250 times shorter list)  ----
  -------------------------------------------------------------------
  -- mapM_ write$ filter okSimple [0..10000000*250] -- t = 20.694
  -- mapM_ writeIfOkSimple [0..10000000*250]        -- t = 20.698
  -- mapM_ writeIfOk [0..10000000*250]              -- t = 20.669
  filterM ok [0..10000000] >>= mapM_ write          -- t = 17.200

  -- evaluate array
  elems <- getElems arr
  print $ sum elems

  end <- getCPUTime
  print $ fromIntegral (end - start) / (10^12)

我的问题是:两种方法(使用 writeIfOk/使用 filterM ok和 write)是否应该编译为同一代码(迭代列表，询问条件，写入数据)？如果不是，我是否可以做一些事情(重写代码，添加编译标志，使用内联编译指示等)使它们在计算上等效，或者在性能至关重要时我应该始终使用 when吗？

Answer 1

将此问题归结为实质，您会问到两者之间的区别

f (filter g xs)

和

f =<< filterM (pure . g) xs

这基本上归结为懒惰。 filter g xs根据需要逐步生成其结果，仅使 xs走得足够远才能找到结果的下一个元素。 filterM定义如下:

filterM _p [] = pure []
filterM p (x : xs)
  = liftA2 (\q r -> if q then x : r else r)
           (p x)
           (filterM p xs)

由于 IO是“严格”的应用程序，因此在遍历整个列表之前，它根本不会产生任何结果，从而将 p x结果存储在内存中。