"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 :>

我们可以在end元素上进行映射,折叠和遍历:

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