How to reverse a NonEmpty in Haskell

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?

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.

The other extant answer does a good job of describing various alternatives for implementations, but those alternatives seem to appear out of whole cloth. In this answer, I will attempt to show how you could go about inventing the answer yourself. I will start by assuming you have already grokked the standard tricks for implementing reverse on plain lists, and show how with simple, local transformations you can turn that implementation into one that works on non-empty lists.

Here's the standard implementation of reverse for plain lists:

reverse xs = go [] xs where
    go as [] = as
    go as (b:bs) = go (b:as) bs

We'd like to modify this so that our recursive function is only called on non-empty lists (i.e. plain old lists that we know are not empty, not NonEmptys). So everywhere we call go, just before we do the call, we'll do a pattern match. If we would have called go on an empty list, we'll just inline what go would have done so that we don't have to call it. For example, instead of go [] xs, we'll do a case on xs to check whether it's empty and only call go when it isn't, like this:

reverse [] = [] -- inline the call go [] []
reverse (x:xs) = go [] (x:xs) {- no inlining, do the same call we would usually do -} where
    go as [] = as -- no change at all from before, since there's no recursive call
    go as (b:[]) = b:as -- inline the call go (b:as) []
    go as (b:b':bs) = go (b:as) (b':bs) -- no inlining, do the same call we would usually do

Now that we know go's argument is always non-empty, we can remove that case from the definition of go. All other cases remain exactly the same.

reverse [] = []
reverse (x:xs) = go [] (x:xs) where
    go as (b:[]) = b:as
    go as (b:b':bs) = go (b:as) (b':bs)

Now it's a bit odd that we're pattern-matching on the second argument to go to extract the first element of the list given that we know all callers have just done the same pattern match already. So let's just change the calling convention a little: callers will pass the already-matched first list element separately. Like this:

reverse [] = []
reverse (x:xs) = go [] x xs where
    go as b [] = b:as
    go as b (b':bs) = go (b:as) b' bs

Given this definition, it is now extremely easy to implement weirdReverse :: NonEmpty a -> [a]: simply ignore the first defining clause for empty inputs, since we know they don't exist! Of course we also have to change the : to a :| in the outer pattern match.

weirdReverse :: NonEmpty a -> [a]
weirdReverse (x:|xs) {- swap out constructors -} = go [] x xs where
    go as b [] = b:as
    go as b (b':bs) = go (b:as) b' bs

Finally, since go now clearly syntactically always returns a list with at least one element, it's easy to swap out the : in its return value for a :| to return a NonEmpty instead of a [].

neReverse :: NonEmpty a -> NonEmpty a
neReverse (x:|xs) = go [] x xs where
    go as b [] = b:|as -- swap out constructors
    go as b (b':bs) = go (b:as) b' bs

This pattern -- of implementing NonEmpty functions in essentially the same way as their [] counterparts, but "unrolling" each definition one layer and adding an argument for the known head -- is quite general; it should work well for things like map, foldr, zip, last, init, and so forth. I encourage you to give it a shot, as it's excellent exercise! If you want to start with a particularly similar one, try last.