Список, основанный на правильном расширении Kan

Ответ 1

Вот довольно принципиальное решение для реализации головы и хвоста за один раз (полный текст):

Прежде всего, мы знаем, как добавлять списки (это будет полезно позже):

append :: List a -> List a -> List a
append (Abstr xs) (Abstr ys) = Abstr (\ f -> xs f <> ys f)

Затем мы вводим новый тип Split, который мы будем использовать, чтобы определить, является ли a List пустым или нет (и получить в случае, если он не пуст, голова и хвост):

newtype Split a = Split { outSplit :: Maybe (a, List a) }

Этот новый тип образует моноид: действительно, мы знаем, как добавить два списка.

instance Monoid (Split a) where
  mempty = Split Nothing
  mappend (Split Nothing)        (Split nns)            = Split nns
  mappend (Split mms)            (Split Nothing)        = Split mms
  mappend (Split (Just (m, ms))) (Split (Just (n, ns))) =
    Split $ Just (m, append ms (cons n ns))

Это означает, что мы можем получить функцию от List a до Split a с помощью List a apply:

split :: List a -> Split a
split xs = apply xs $ \ a -> Split $ Just (a, nil)

head и tail окончательно могут быть тривиально получены из Split:

head :: List a -> Maybe a
head = fmap fst . outSplit . split

tail :: List a -> Maybe (List a)
tail = fmap snd . outSplit . split

Ответ 2

Эта реализация списков в виде бесплатных моноидов представлена ​​в пакете fmlist, который отмечает некоторые интересные свойства (в отличие от большинства реализаций списков, которые правы -biased, это действительно беспристрастно, вы можете сделать произвольное дерево, и хотя, конечно, моноидные законы заставляют вас видеть его сглаженным, вы все равно можете наблюдать некоторые различия в бесконечном случае. Это почти причуда Хаскелла - обычно, свободные моноиды). Он также имеет реализацию tail, поэтому вы можете ответить на свой вопрос (но см. Ниже).

С этими видами представлений (а не только с этим конкретным, но также, например, с списками forall r. (a -> r -> r) -> r -> r) обычно выполняются некоторые операции (например, добавление), а некоторые (например, zip и tail) становятся более сложными, Это обсуждается немного в разных местах, например. Как принять tail функционального потока.

Более внимательно рассмотрев fmlist, его решение довольно неудовлетворительное: оно просто преобразует красивое сбалансированное дерево, которое вы даете ему в правый смещенный список, используя foldr, что позволяет ему выполнять регулярные операции с списком, но теряет моноидальную структуру. Хвост "среднего бесконечного" списка уже не "средний-бесконечный", он просто прав-бесконечен, как обычный список.

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

nail :: FM.FMList a -> FM.FMList a
nail (FM.FM k) = FM.FM $ \f -> foldMap f (nail' (k N))

nail' :: N a -> N a
nail' NEmpty = error "nail' NEmpty"
nail' (N x) = NEmpty
nail' (NAppend l r) =
  case normalize l of
    NEmpty -> nail' r
    N x -> r
    l' -> NAppend (nail' l') r

-- Normalize a tree so that the left side of a root NAppend isn't an empty
-- subtree of any shape. If the tree is infinite in a particular way, this
-- won't terminate, so in that sense taking the tail of a list can make it
-- slightly worse (but you were already in pretty bad shape as far as
-- operations on the left side are concerned, and this is a pathological case
-- anyway).
normalize :: N a -> N a
normalize (NAppend l r) =
  case normalize l of
    NEmpty -> normalize r
    l' -> NAppend l' r
normalize n = n