“无”带有值的列表？

是否一些标准的Haskell库这样定义“无”带有值的列表？

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

这是一个列表，其端接元件中携带的指定类型的值的数据类型？

所以ListWithEnd()与[]是同构的，而ListWithEnd Void是同构于无限流。或者，不同的观察，ListWithEnd e a非常接近ConduitM() a Identity e ..

来源

2015-03-30 Petr Pudlák

我还没有看到它。也许它会更容易（与预定义函数一起工作）来定义'newtype ListWithEnd e a = LWE（[a]，e）'？ – 2015-03-30 17:41:05

@ ThomasM.DuBuisson我最终需要'e'来构造函数，因为我正在试验构造列表时计算'e'的函数。 – 2015-03-30 17:47:02

+12

试图用标准的东西表达它，“想到类型LWE e a = Free（（，）a）e'。 – 2015-03-30 17:51:03

我们可以定义ListWithEnd如下：

import Control.Monad.Free 

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

我们通常有一个期望，抽象的或通用的表述应该奖励我们的样板整体下降。让我们看看这个表示为我们提供了什么。

在任何情况下，我们应定义为利弊情况的模式同义词：

{-# 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

我们可以映射在列表ELEM经济需求，如果有点曲折：

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：

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

来源

2015-03-31 21:03:13

“无”带有值的列表？

回答

相关问题