list - Haskell 列表复杂度

Question

抱歉，如果这个问题已经被问过，我没有找到。并为我糟糕的英语感到抱歉。

我正在学习 Haskell 并尝试使用列表。
我编写了一个函数，它按照特定模式转换列表，我现在无法检查它是否有效，但我认为可以。

这个函数不是尾调用函数，所以我认为用一个大列表来计算这个函数会很糟糕:

transform :: [Int] -> [Int]
transform list = case list of
  (1:0:1:[])  -> [1,1,1,1]
  (1:1:[])    -> [1,0,1]
  [1]         -> [1,1]
  (1:0:1:0:s) -> 1:1:1:1: (transform s)
  (1:1:0:s)   -> 1:0:1: (transform s)
  (1:0:s)     -> 1:1: (transform s)
  (0:s)       -> 0: (transform s)

所以我想到了另一个功能，它会“更好”:

transform = reverse . aux []
  where
    aux buff (1:0:[1])   = (1:1:1:1:buff)
    aux buff (1:[1])     = (1:0:1:buff)
    aux buff [1]         = (1:1:buff)
    aux buff (1:0:1:0:s) = aux (1:1:1:1:buff) s
    aux buff (1:1:0:s)   = aux (1:0:1:buff) s
    aux buff (1:0:s)     = aux (1:1:buff) s
    aux buff (0:s)       = aux (0:buff) s

问题是我不知道它是如何编译的，如果我对第二个函数有误。你能解释一下列表是如何工作的吗？最后使用 (++) 还是反转列表更好？

预先感谢您的回答

Answer 1

第一个功能非常好，在我看来比第二个更可取。

原因是懒惰。如果您有 transform someList表达式中的表达式，除非您要求，否则不会评估结果列表。特别是，将仅在需要时对列表进行评估； print $ take 10 $ transform xs将比 print $ take 20 $ transform xs 做更少的工作.

用严格的语言transform确实会妨碍堆栈，因为它必须在返回任何使用的东西之前评估整个列表(以非尾递归方式)。在 Haskell transform (0:xs)计算结果为 0 : transform xs ，一个可用的部分结果。我们可以在不触及尾部的情况下检查这个结果的头部。也没有堆栈溢出的危险:在任何时候，列表尾部最多有一个未计算的 thunk(如前面示例中的 transform xs)。如果您需要更多元素，则 thunk 只会被推到更远的位置，并且可以对前一个 thunk 的堆栈帧进行垃圾收集。

如果我们总是对列表进行全面评估，那么这两个函数的性能应该是相似的，或者即使这样，惰性版本也可能会更快一些，因为缺少反转或额外的 ++ -s。因此，通过切换到第二个函数，我们失去了惰性并且没有获得额外的性能。