基于右Kan扩展的列表

Question

在Ralf Hinze的“程序优化的Kan扩展”中，有一个列表类型的定义，它是基于从单子类中的遗忘函子的右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))

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

Answer 1

在包fmlist中提供了将列表作为自由monoid的这种实现，其中说明了它的一些有趣的属性（与大多数列表实现不同，这些实现是右偏的，而这个实现是真正无偏的；您可以创建一个任意树，当然，尽管monoid定律迫使您将其视为平坦的，但在无限情况下，您仍然可以观察到一些差异。这几乎是Haskell的一个怪癖--通常是自由monoid）。它还有一个tail的实现，所以这是对您问题的某种回答（但请参见下面）。

对于这些类型的表示（不仅仅是这个特殊的表示，还包括所有r.(a->r->r)->r->r列表的)，通常有些操作（例如追加）变得更容易，有些操作（例如zip和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