haskell - Haskell 中列表的倒数第二个元素

Question

考虑以下用于查找列表的倒数第二个元素的函数:

myButLast (x:xs) = if length xs > 1 then myButLast xs else x

这是一个 O(n^2) 算法，因为 length xs是 O(n)，称为 O(n) 次。在 Haskell 中编写此内容的最优雅方式是什么，例如 length一旦超过 1 就停止，所以算法是 O(n)？

Answer 1

最简单的方法是避免length :

myButLast (x : _ : []) = x  -- base case
myButLast (_ : xs)     = myButLast xs

Haskell 模式的权威引用是语言报告: https://www.haskell.org/onlinereport/haskell2010/haskellch3.html#x8-580003.17

GHC 实现了一些在 https://downloads.haskell.org/~ghc/latest/docs/html/users_guide/syntax-extns.html#pattern-guards 中描述的扩展.