在Haskell中定義爲Maybe的列表？爲什麼不？

Question

你不見於Ger.Offen看到0​​除了錯誤處理，例如，因爲名單是有點Maybe自己：他們有自己的「Nothing‘：[]和自己的’Just」：(:)。 我用Maybe和函數將標準轉換爲「實驗」列表編寫了一個列表類型。 toStd . toExp == id。

data List a = List a (Maybe (List a)) 
    deriving (Eq, Show, Read) 

toExp [] = Nothing 
toExp (x:xs) = Just (List x (toExp xs)) 

toStd Nothing = [] 
toStd (Just (List x xs)) = x : (toStd xs) 

您怎麼看待它，試圖減少重複，推廣？

樹木也可以使用這些列表來定義：

type Tree a = List (Tree a, Tree a) 

我沒有測試過這最後一段代碼，雖然。

Answer 1

所有的ADT是同構的（幾乎 - 見端）的(,)，Either，()，(->)，Void和Mu一些組合，其中

data Void --using empty data decls or 
newtype Void = Void Void 

和Mu計算函子的不動點

newtype Mu f = Mu (f (Mu f)) 

例如

data [a] = [] | (a:[a]) 

相同

data [a] = Mu (ListF a) 
data ListF a f = End | Pair a f 

其本身是同構的

newtype ListF a f = ListF (Either() (a,f)) 

因爲

data Maybe a = Nothing | Just a 

同構

newtype Maybe a = Maybe (Either() a) 

你有

newtype ListF a f = ListF (Maybe (a,f)) 

可在萬畝內聯到

data List a = List (Maybe (a,List a)) 

和你的定義

data List a = List a (Maybe (List a)) 

只是在穆的展開和消除外部的可能（對應於非空列表）

你就完成了......

幾件事情

1. 使用自定義的ADT增加清晰度和類型安全

2. 這普遍性有用：看GHC.Generic

---

好吧，我說幾乎是同構的。它不完全是，即

hmm = List (Just undefined) 

在列表的[a] = [] | (a:[a])定義中沒有等價值。這是因爲Haskell數據類型是coinductive，並且已被a point of criticism of the lazy evaluation model。你可以只用嚴格的資金和產品得到解決這些問題（和值函數調用），並加入一個特殊的「懶惰」的數據構造

data SPair a b = SPair !a !b 
data SEither a b = SLeft !a | SRight !b 
data Lazy a = Lazy a --Note, this has no obvious encoding in Pure CBV languages, 
--although Laza a = (() -> a) is semantically correct, 
--it is strictly less efficient than Haskell's CB-Need 

，然後所有的同構可以忠實地編碼。

Answer 2

您可以根據Maybe定義列表，但不是那樣。您的List類型不能爲空。或者你打算Maybe (List a)是[a]的替代品。這看起來很糟糕，因爲它不能區分列表和類型。

這會工作

newtype List a = List (Maybe (a, List a)) 

這有一些問題。首先使用它比通常的列表更冗長，其次，域不與列表同構，因爲我們在那裏有一對（可以是未定義的;在域中增加一個額外的級別）。

Answer 3

你可以在Haskell中用很多方式定義列表。例如，作爲功能：

{-# LANGUAGE RankNTypes #-} 

newtype List a = List { runList :: forall b. (a -> b -> b) -> b -> b } 

nil :: List a 
nil = List (\_ z -> z) 

cons :: a -> List a -> List a 
cons x xs = List (\f z -> f x (runList xs f z)) 

isNil :: List a -> Bool 
isNil xs = runList xs (\x xs -> False) True 

head :: List a -> a 
head xs = runList xs (\x xs -> x) (error "empty list") 

tail :: List a -> List a 
tail xs | isNil xs = error "empty list" 
tail xs = fst (runList xs go (nil, nil)) 
    where go x (xs, xs') = (xs', cons x xs) 

foldr :: (a -> b -> b) -> b -> List a -> b 
foldr f z xs = runList xs f z 

訣竅這個實現的是，名單被表示爲在列表的元素進行摺疊功能：

fromNative :: [a] -> List a 
fromNative xs = List (\f z -> foldr f z xs) 

toNative :: List a -> [a] 
toNative xs = runList xs (:) [] 

在任何情況下，真正事項是合同（或法律），類型和其操作遵循，和性能的實施。基本上，任何滿足合同的實現都會給你正確的程序，而更快的實現會給你更快的程序。

列表的合同是什麼？好吧，我不打算來表達它的完整細節，但名單服從陳述這樣的：

1. head (x:xs) == x
2. tail (x:xs) == xs
3. [] == []
4. [] /= x:xs
5. 如果xs == ys和x == y，然後x:xs == y:ys
6. foldr f z [] == z
7. foldr f z (x:xs) == f x (foldr f z xs)

編輯：而綁這augustss'回答：

newtype ExpList a = ExpList (Maybe (a, ExpList a)) 

toExpList :: List a -> ExpList a 
toExpList xs = runList xs (\x xs -> ExpList (Just (x, xs))) (ExpList Nothing) 

foldExpList f z (ExpList Nothing) = z 
foldExpList f z (ExpList (Just (head, taill))) = f head (foldExpList f z tail) 

fromExpList :: ExpList a -> List a 
fromExpList xs = List (\f z -> foldExpList f z xs) 

Answer 4

如果它是一個列表，它應該是Functor一個實例，對不對？

instance Functor List 
    where fmap f (List a as) = List (f a) (mapMaybeList f as) 

mapMaybeList :: (a -> b) -> Maybe (List a) -> Maybe (List b) 
mapMaybeList f as = fmap (fmap f) as 

這裏有一個問題：你可以讓List的Functor一個實例，但你也許清單並非如此：即使Maybe是不是已經在自己的權利的的Functor實例，你不能直接進行施工像Maybe . List到任何東西的實例（你需要一個包裝類型）。

與其他類型類似。

---

說了這麼多，你的配方，你可以做到這一點，你不能用標準Haskell的待辦事項列表：

instance Comonad List 
    where extract (List a _) = a 
     duplicate x @ (List _ y) = List x (duplicate y) 

。也許列表仍然不會comonadic雖然。

Answer 5

當我第一次開始使用Haskell時，我也儘可能地用現有的類型來表示事物，理由是避免冗餘是很好的。我目前的理解（移動目標！）往往涉及更多的多維網絡權衡理念。我不會在這裏給出任何「答案」，就像粘貼示例一樣，並問「你明白我的意思嗎？」我希望它無論如何都有幫助。

讓我們來看看一點點的darcs代碼：

data UseCache = YesUseCache | NoUseCache 
    deriving (Eq) 

data DryRun = YesDryRun | NoDryRun 
    deriving (Eq) 

data Compression = NoCompression 
       | GzipCompression 
    deriving (Eq) 

你有沒有注意到這三種可能都已經Bool的？你爲什麼認爲Darcs黑客決定在代碼中引入這種冗餘？再舉一個例子，這裏是一段代碼，我們改變了幾年前：

type Slot = Maybe Bool     -- OLD code 
data Slot = InFirst | InMiddle | InLast -- newer code 

你認爲爲什麼我們決定第二次代碼是在第一的改進？

最後，這是我一些日常工作中的一些代碼。它使用newtype語法augustss提到，

newtype Role = Role { fromRole :: Text } 
    deriving (Eq, Ord) 

newtype KmClass = KmClass { fromKmClass :: Text } 
    deriving (Eq, Ord) 

newtype Lemma = Lemma { fromLemma :: Text } 
    deriving (Eq, Ord) 

在這裏，你會發現，我已經做了考慮一個非常好的Text類型，然後它包裝成三個不同的東西很奇怪的事情。與普通舊Text相比，這三件事沒有任何新功能。他們只是在那裏有所不同。說實話，我不完全確定這是否是一個好主意。我暫時認爲這是因爲我由於許多原因操縱了許多不同的文本片斷，但時間會證明這一點。

你能看到我想要的嗎？