CODEWITHSUNDEEP
haskell
Elliot Gorokhovsky
Elliot Gorokhovsky

Reputation: 3762

Second to last element of a list in Haskell

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)?

Upvotes: 4

Views: 3927

Answers (6)

MyLifeisPi
MyLifeisPi

Reputation: 83

Here is my solution using the tail function from prelude

myButLast :: [Int] -> Maybe Int
myButLast (x:xs) | ((null xs) || null (tail xs)) = Just x
                 | otherwise                     = myButLast(xs)
myButLast []                                     = Nothing

Upvotes: 1

Will Ness
Will Ness

Reputation: 71119

Another zip-based solution, without exlicitly zipping. Throw in some safety for good measure.

import Data.Maybe

g :: Int -> [a] -> Maybe a
g i = (head <$>) . listToMaybe . reverse         -- quick'n'dirty safe-last
                 . getZipList . traverse ZipList 
                 . sequence [id, drop i] 

g  1 [1..10] => Just 9
g  3 [1..10] => Just 7
g 13 [1..10] => Nothing

Upvotes: 1

w.b
w.b

Reputation: 11238

Another solution:

myButLast [] = error "List is empty"
myButLast [x] = error "List is a singleton"
myButLast xs = last $ init xs

Upvotes: 4

chi
chi

Reputation: 116174

Exploiting zip:

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

Also available in a pointless, obfuscated style:

fst . last . (zip <*> tail)

or even without parentheses (thanks to @melpomene):

fst . last . ap zip tail

Other variants:

last . ap (zipWith const) tail

Upvotes: 5

melpomene
melpomene

Reputation: 85887

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.

Upvotes: 9

Random Dev
Random Dev

Reputation: 52290

what about

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

Upvotes: 6

Related Questions