haskell - 在 Haskell 中编写 (init, last) 的最有效方法

Question

我是 Haskell 新手，所以作为练习，我想实现一个类似于 uncons 的函数，它返回 init 和 last 列表中的元素。编写此函数的简单方法是

initLast :: [a] -> ([a], a)
initLast xs = (init xs, last xs)

我是编写 Haskell 程序的新手，但这对我来说似乎效率低下，因为它必须遍历列表两次。我想出了另一个函数，我认为它可能更好，因为不需要多次迭代列表:

initLast' :: [a] -> ([a], a)
initLast' [x] = ([], x)
initLast' (x:xs) = let (xs', y) = initLast' xs
                   in (x:xs', y)

但事实证明，当我在 ghci 中运行这些版本时，我发现第二个版本慢了一倍，并且使用了大约 3 倍的内存!

ghci> :set +s
ghci> snd (initLast [1..1000000])
1000000
(0.28 secs, 122242144 bytes)
ghci> snd (initLast' [1..1000000])
1000000
(0.71 secs, 434147544 bytes)

问题:

1. 为什么第二个版本效率较低？
2. 是否有更有效的方法来实现 initLast？

Answer 1

像往常一样:如果要进行性能测试，请进行编译。编译版本两者使用的时间大约相同，但 initLast 为 67MB，initLast' 仅 6MB。