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,可用的部分结果.我们可以在不接触尾部的情况下检查该结果的头部.堆栈溢出也没有危险:在任何时候transform xs,列表尾部最多只有一个未评估的thunk(如前例所示).如果你需要更多的元素,thunk将被推回更远,并且前一个thunk的堆栈帧可以被垃圾收集.

如果我们总是完全评估列表,那么两个函数的性能应该是相似的,或者甚至懒惰版本可能会因为缺少反转或额外的++-s而更快.因此,通过切换到第二个功能,我们会失去懒惰并且不会获得额外的性能.