Как отменить NonEmpty в Haskell

Вы можете определить его с помощью функции reverse для таких списков:

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

Однако этот подход не является оптимальным, поскольку он проходит по списку дважды, reverse и ++.

Другая возможность - вспомогательная функция аккумулятора, например:

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

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

Это решение многократно создает и разрушает непустой конструктор :|.

В Data.List.NonEmpty обратная функция определяется как поднятие обратной функции списка:

reverse = lift List.reverse

Этот подход является наиболее эффективным, потому что он выполняет некоторое преобразование в постоянное время, линейный проход и окончательное преобразование в постоянное время.

Другой существующий ответ хорошо описывает различные альтернативы для реализации, но эти альтернативы, похоже, появляются из цельного полотна. В этом ответе я попытаюсь показать, как вы могли бы придумать ответ самостоятельно. Я начну с предположения, что вы уже разобрались со стандартными трюками для реализации reverse в простых списках, и покажу, как с помощью простых локальных преобразований вы можете превратить эту реализацию в такую, которая работает с непустыми списками.

Вот стандартная реализация reverse для простых списков:

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

Мы хотели бы изменить это так, чтобы наша рекурсивная функция вызывалась только для непустых списков (т. е. простых старых списков, которые, как мы знаем, не пусты, а не NonEmptys). Итак, везде, где мы вызываем go, непосредственно перед тем, как сделать вызов, мы делаем сопоставление с образцом. Если бы мы вызвали go в пустом списке, мы просто встроим то, что сделал бы go, чтобы нам не пришлось его вызывать. Например, вместо go [] xs мы выполним проверку xs, чтобы проверить, пусто ли оно, и вызывать go только тогда, когда это не так:

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

Теперь, когда мы знаем, что аргумент go всегда непуст, мы можем удалить этот случай из определения go. Все остальные случаи остаются точно такими же.

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

Теперь немного странно, что мы сопоставляем шаблон со вторым аргументом go, чтобы извлечь первый элемент списка, учитывая, что мы знаем, что все вызывающие объекты только что выполнили одно и то же сопоставление шаблона. Так что давайте просто немного изменим соглашение о вызовах: вызывающие будут передавать уже совпадающий первый элемент списка отдельно. Так:

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

Учитывая это определение, теперь его чрезвычайно легко реализовать weirdReverse :: NonEmpty a -> [a]: просто игнорируйте первое определяющее предложение для пустых входных данных, поскольку мы знаем, что они не существуют! Конечно, мы также должны заменить : на :| во внешнем совпадении с шаблоном.

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

Наконец, поскольку go теперь явно синтаксически всегда возвращает список, содержащий хотя бы один элемент, легко заменить : в возвращаемом значении на :|, чтобы вернуть NonEmpty вместо [].

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

Этот шаблон реализации функций NonEmpty практически таким же образом, как и их аналоги [], но «развертывание» каждого определения на один слой и добавление аргумента для известного заголовка — довольно общий; он должен хорошо работать для таких вещей, как map, foldr, zip, last, init и так далее. Я призываю вас попробовать, так как это отличное упражнение! Если вы хотите начать с особенно похожего, попробуйте last.