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

我是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)

问题:

为什么第二个版本效率较低？

有更有效的实施方式initLast吗？

Daniel Wagne.. 9

像往常一样:编译,如果你要进行性能测试.编译版本对两者使用大约相同的时间,但是67MB,initLast而只有6MB initLast'.

1> Daniel Wagne..：

---

像往常一样:编译,如果你要进行性能测试.编译版本对两者使用大约相同的时间,但是67MB,initLast而只有6MB initLast'.

---

@ user2407038真的.它们不等同,因为前者对数据进行了两次传递(因此必须在第一次传递期间将整个输入列表保存在内存中),而后者仅使用一次.也许你没有用优化或其他东西进行编译......？

---

@DanielWagner我很确定某些编译器和/或库支持这种循环融合.在Haskell中肯定有类似事情的工作,但它有点超过我的头脑.