「無」帶有值的列表？

是否一些標準的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

「無」帶有值的列表？

回答

相關問題