"Nil" 带有值的列表？

Question

某些标准 Haskell 库是否定义了这样的数据类型

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

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

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

Answer 1

我们可以这样定义ListWithEnd：

import Control.Monad.Free

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

我们通常期望抽象或通用表示应该通过整体减少样板来奖励我们。让我们看看这种表示法为我们提供了什么。

在任何情况下，我们都应该为 cons 情况定义一个模式同义词：

{-# 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 必须恰好包含一个结束元素，我们可以通过为它（而不是 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

"Nil" 带有值的列表？

A list whose "Nil" carries a value?

haskell

list

algebraic-data-types

pattern-synonyms