Haskell 中函数的求值顺序 – 调用 ++

Question

我是 Haskell 新手，不明白如何评估以下函数：

    test1 1 ls = ls
    test1 p ls = test1 (p - 1) ls ++ [p]

通过下面的简单方案，我假设答案应该是 [3, 2]， 但 ghci 中的评估给出了 [2, 3]。这是为什么？

    {-
    test1 3 [] =
        test1 2 []++[3] =
            test1 1 []++[3]++[2]
    -}

Answer 1

函数应用通常优先于运算符，因此：

test1 1 ls = ls
test1 p ls = test1 (p - 1) ls ++ [p]

解释为：

test1 1 ls = ls
test1 p ls = (test1 (p - 1) ls) ++ [p]

因此，这将被评估为：

test1 3 []
  -> (test1 2 []) ++ [3]
  -> (test1 1 [] ++ [2]) ++ [3]
  -> ([] ++ [2]) ++ [3]
  -> [2, 3]

但是该算法效率不是很高：将 𝓞(n) 和 n 左侧子列表的项目数追加到右侧，使得

test1

函数在 𝓞(n²) 中运行。我们可以在这里使用累加器：

test1 1 ls = ls
test1 p ls = test1 (p-1) (p:ls)

这使得算法𝓞(n)。例如，如果

ls

已经是一个非常大的列表，并且还可以节省内存，那么这尤其有用，因为我们不复制

ls

，而只是重用

ls

列表。