Second to last element of a list in Haskell

Question

Consider the following function for finding the second-to-last element of a list:

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

This is an O(n^2) algorithm, because length xs is O(n) and is called O(n) times. What is the most elegant way to write this in Haskell such that length stops once it gets past 1, so that the algorithm is O(n)?

Answer 1

The easiest way is to avoid length:

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

The definitive reference on patterns in Haskell is the language report: https://www.haskell.org/onlinereport/haskell2010/haskellch3.html#x8-580003.17

GHC implements a few extensions described at https://downloads.haskell.org/~ghc/latest/docs/html/users_guide/syntax-extns.html#pattern-guards.

Answer 2

what about

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