How to reverse a NonEmpty in Haskell

Question

This time, I am faced with the task of reversing a NonEmpty.

I am trying this (I know that it does not do what we require it to, yet assume this is a MWE):

reverseNonEmpty :: NonEmpty a -> NonEmpty a
reverseNonEmpty (x :| []) = x :| []
reverseNonEmpty (x :| xs) = (x :| tail xs)

main :: IO ()
main = do
  print (reverseNonEmpty (1 :| [2, 3, 4])) -- Prints "1 :| [3,4]"

The above snippet is the first version that compiles. However, I am puzzled with Haskell syntax for NonEmpty's (I am a beginner here).

Q: How do I make it reverse input NonEmptys?

Answer 1

You can define it in terms of the reverse function for lists like this:

reverseNonEmpty :: NonEmpty a -> NonEmpty a
reverseNonEmpty (x :| xs) = case Prelude.reverse xs of
                            []     -> x :| []
                            (y:ys) -> y :| (ys ++ [x])

This approach however is not optimal because it traverses the list twice, reverse and ++.

Another possibility is with an accumulator helper function for example:

reverseNonEmpty (x :| xs) = reverseAcc xs (x :| [])

reverseAcc :: [a] -> NonEmpty a -> NonEmpty a
reverseAcc []     acc = acc
reverseAcc (x:xs) acc = reverseAcc xs (x :| toList acc)

This solution repeatedly constructs and destructs the nonempty constructor :|.

In Data.List.NonEmpty the reverse function is defined as a lifting of the list reverse function:

reverse = lift List.reverse

This approach is the most efficient, because it does some constant time conversion, a linear pass and a final constant time conversion.