基于右 Kan 扩展的列表

在``用于程序优化的 Kan 扩展 http://www.cs.ox.ac.uk/ralf.hinze/Kan.pdfRalf Hinze 所著的列表类型的定义基于来自幺半群范畴的健忘函子的右 Kan 扩展（第 7.4 节）。论文给出Haskell实现如下：

newtype List a = Abstr {
  apply :: forall z . (Monoid z) => (a -> z) -> z
  } 

我能够定义通常的 nil 和 cons 构造函数：

nil :: List a
nil = Abstr (\f -> mempty)

cons :: a -> List a -> List a
cons x (Abstr app) = Abstr (\f -> mappend (f x) (app f))

通过 Maybe 函子的 Monoid 类的以下实例，我成功地定义了 head 函数：

instance Monoid (Maybe a) where
  mempty = Nothing
  mappend Nothing m = m
  mappend (Just a) m = Just a

head :: List a -> Maybe a
head (Abstr app) = app Just

Question: 如何定义tail函数？

这是一个相当有原则的解决方案，可以一次性实现头和尾（完整要点 https://gist.github.com/gallais/ef7330d74161c46a401b):

首先，我们知道如何追加列表（稍后会很有用）：

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

然后我们引入一个新类型Split我们将用它来检测是否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 to Split a using List a's apply:

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

head and tail最终可以简单地导出split:

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

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