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中描述的一些扩展.

Answer 2

关于什么

myButLast []     = error "oho"
myButLast [x,_]  = x
myButLast (_:xs) = myButLast xs

Answer 3

开发zip:

\l -> fst . last $ zip l (tail l)

还有一种毫无意义的混淆风格:

fst . last . (zip <*> tail)

甚至没有括号(感谢@melpomene):

fst . last . ap zip tail

其他变种:

last . ap (zipWith const) tail