可以在do-notation/enumfom中进行模式匹配，从而减慢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：大约5秒;

c'100 98：大约70秒;

正如我提到的，结果是相同的。

所以，我每次都对生成[a..b]感到不安，但是我做了一小部分，并且有人建议Haskell不会立即进行模式，但由于懒惰而延迟了 - 评估，会引起大量c'的额外呼叫。但是，第二个理论并不完全存在：我直接从GHCI命令提示符中设置了一个断点，以监视n的值，这表明并非如此。

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

Answer 1

将您的True <- return $ (l - 1 <= n)更改为True <- return $ (l <= n)，以匹配第一个摘要所做的工作，使我对我的时间均等（不更改答案）。

没有这种更改，您的第二个摘要浪费了很多时间，试图在数字[1..l-1]之间找到长度 l的减小序列（对于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，仅在下一行中丢弃这些选择。生成选择仅丢弃它们的选择可以减慢您的程序。