do-notation / enumFromTo中的模式匹配会减慢Haskell代码的速度吗？

Question

我一直在解决一个非常简单的问题：生成L长度的所有递减序列，由1到M的自然数字组成，按字典顺序排列。然而，我遇到了一个非常奇怪的问题。看一看：

c :: (Ord a, Num a, Enum a) => a -> a -> [[a]]
c m 1 = map return [1..m]
c m l = do
          n   <- [l..m]
          res <- c (n - 1) (l - 1)
          return $ n:res

c' :: (Ord a, Num a, Enum a) => a -> a -> [[a]]
c' m = helper 1 m where
 helper :: (Ord a, Num a, Enum a) => a -> a -> a -> [[a]]
 helper a b 1 = map return [a..b]
 helper a b l = do
                  n    <- [a..b]
                  True <- return $ (l - 1 <= n)
                  res  <- helper a (n - 1) (l - 1)
                  return (n:res)

显然，这两个函数完全相同（我在一些测试中检查过它们，它们都给出了正确的结果）但是如果你试图在GHCi中评估c 100 98和c' 100 98，你会看到一个巨大的差异。时间：

c 100 98: around 5 seconds;

c' 100 98: around 70 seconds;

As I've mentioned, the result is the same。

所以，我对每次生成[a..b]都感到不安，但我做了一点询问，并且有人建议Haskell不能直接模式匹配，但由于懒惰的评估而延迟它，这导致了大量额外的c'电话。然而，第二个理论并不完全适用：我在我的代码中直接从GHCi命令提示符设置了一个断点来监视n的值，这表明延迟的模式匹配并非如此。

问题可能实际上与enumFromTo功能有关，还是有其他原因？

Answer 1

将你的True <- return $ (l - 1 <= n)改为True <- return $ (l <= n)，以匹配第一个片段所做的，为我平衡两者的时间（不改变答案）。

没有这个改变，你的第二个片段浪费了大量的时间试图在数字l（对于许多不同的[1..l-1]值）中找到长度l的递减序列，这是一个注定的任务。

Answer 2

这两个函数似乎有一个完全不同的实现：

c m l = do
      n   <- [l..m]
      res <- c (n - 1) (l - 1)
      return $ n:res

这里，在每次递归调用时，参数l都会递减，而参数m会变成n <- [l--m]。

通过比较，

helper a b l = do
    n    <- [a..b]
    True <- return $ (l - 1 <= n)
    res  <- helper a (n - 1) (l - 1)
    return (n:res)

这里的区间是[a..b]而不是[l..m]（顺便说一句，为什么你使用不同的名字？以这种方式比较两个片段更难。）所以，我们考虑参数a和b如何变化。参数a没有变化，而b变成n-1。

还有第三个论点l，它没有出现在第一个片段中。

我没有看到这将是如何相同的算法。它看起来与我完全不同。你可能在这里引起更多的递归调用，这会减慢速度。模式匹配是一个红色的鲱鱼 - 我认为这不会减慢速度，至少不是直接的。

另外，这部分

    n    <- [a..b]
    True <- return $ (l - 1 <= n)

看起来很可疑。应该是这样的

    n    <- [max a (l-1) .. b]

因为以上将从a计算到l-2只是为了放弃下一行中的那些选择。仅生成选项以丢弃它们会降低程序的速度。