一个"Nil"携带值的列表？

Question

有没有一些标准的 Haskell 库定义了这样一个数据类型

data ListWithEnd e a = Cons a (ListWithEnd e a)
                     | End e

这是一个列表，其终止元素携带有指定类型的值？

因此，ListWithEnd()同构于[]，ListWithEnd Void同构于无限流。或者可以换个角度看，ListWithEnd e a非常接近于ConduitM () a Identity e。

- Petr

---

我没有看到过它。也许（就使用预定义函数而言）定义newtype ListWithEnd e a = LWE ([a], e)会更容易？ - Thomas M. DuBuisson

尝试用标准术语表达，我想到了 type LWE e a = Free ((,) a) e。 - András Kovács

你不能只是使用 ([a],e) 吗？ - Omar Antolín-Camarena

这句话的意思是：“那不完全相同，因为列表不一定必须有一个结尾。特别地，([a], Void) 与 Void 同构，而不是无限流。” - Tikhon Jelvis

@AndrásKovács，您能否将您的评论转换为答案，以便我可以接受它？ - Petr

Answer 1

我们可以将ListWithEnd定义如下：

import Control.Monad.Free

type LWE a e = Free ((,) a) e

通常我们期望抽象或通用表示法应该让我们的样板代码总体减少。让我们看看这种表示法给我们提供了什么。

无论如何，我们将为“cons case”定义一个模式同义词：

{-# LANGUAGE PatternSynonyms #-}

pattern x :> xs = Free (x, xs)
infixr 5 :>

我们可以对结尾元素进行映射、折叠和遍历：

fmap (+1) (0 :> Pure 0) == (0 :> Pure 1)
traverse print (0 :> Pure 1) -- prints 1

Applicative实例为我们提供了非常简洁的连接方式：

xs = 1 :> 2 :> Pure 10
ys = 3 :> 4 :> Pure 20

xs *> ys          == 1 :> 2 :> 3 :> 4 :> Pure 20 -- use right end
xs <* ys          == 1 :> 2 :> 3 :> 4 :> Pure 10 -- use left end
(+) <$> xs <*> ys == 1 :> 2 :> 3 :> 4 :> Pure 30 -- combine ends

我们可以对列表元素进行映射，虽然有点费劲：

import Data.Bifunctor -- included in base-4.8!

hoistFree (first (+10)) xs == 11 :> 12 :> Pure 10

当然，我们可以利用iter。

iter (uncurry (+)) (0 <$ xs) == 3 -- sum list elements

如果LWE可以成为Bitraversable（以及Bifunctor和Bifoldable），那就太好了，因为这样我们可以以更通用和原则性的方式访问列表元素。为此，我们绝对需要一个新类型：

newtype LWE a e = LWE (Free ((,) a) e) deriving (lots of things)

instance Bifunctor LWE where bimap = bimapDefault
instance Bifoldable LWE where bifoldMap = bifoldMapDefault
instance Bitraversable LWE where bitraverse = ...

但是在这一点上，我们考虑将纯ADT写出来并用几行代码编写Applicative、Monad和Bitraversable实例。或者，我们可以使用lens为列表元素编写一个Traversal：

import Control.Lens

elems :: Traversal (LWE a e) (LWE b e) a b
elems f (Pure e)  = pure (Pure e)
elems f (x :> xs) = (:>) <$> f x <*> elems f xs

进一步思考这个问题，我们应该为结束元素制作一个Lens。这比通用的Free接口多了一个奖励，因为我们知道每个有限的LWE必须包含一个结束元素，并且我们可以通过为其创建一个Lens（而不是Traversal或Prism）来明确表示此元素。

end :: Lens (LWE a e) (LWE a e') e e'
end f (Pure e)  = Pure <$> f e
end f (x :> xs) = (x :>) <$> end f xs

- András Kovács