0

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

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功能上，还是有其他原因？

4

2 回答 2

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以丢弃下一行中的这些选择。仅生成选择以丢弃它们会减慢您的程序速度。

于 2019-03-03T16:02:54.943 回答
1

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

如果没有此更改，您的第二个片段会浪费大量时间尝试在数字中找到长度递减的序列l（[1..l-1]对于 的许多不同值l），这是一项注定要完成的任务。

于 2019-03-04T18:26:11.400 回答