在Haskell中，爲什麼沒有TypeClass可以像列表一樣工作？

Question

我讀Learn You a Haskell，我不知道爲什麼有這麼多的東西都表現得像一個列表，並沒有什麼前奏是使用類型類的本地設備進行此設置：

「的字節串版本of：被稱爲cons它需要一個字節和一個字節字符串，並將字節放在開始位置，雖然很懶，所以即使字符串中的第一個字節未滿，它也會創建一個新的塊，這就是爲什麼它最好使用嚴格版本的缺點，缺點'如果你要在字節串的開頭插入大量的字節。「

爲什麼沒有一個類型類可列或東西，它提供了:功能統一Data.ByteString，Data.List，Data.ByteString.Lazy等？是否有這個原因，還是僅僅是遺留Haskell的元素？使用:作爲一個例子是一種一個保守的，也從LYAH：

否則，字節串模塊具有的是類似於那些在Data.List模塊，包括功能的負載，但不限於，頭，尾時，init，NULL，長度，地圖，反向，與foldl，foldr相似，concat，則takeWhile，過濾器等

Answer 1

，它提供了：功能來統一Data.ByteString，Data.List模塊，Data.ByteString 。拉齊等？

已經有人試圖想出一個好的a）序列接口，b）容器接口，但是統一不同類型的數據類型，不同類型的約束，通常會導致結果不夠規範很難想象將它們放在基礎庫中。同樣，對於數組，雖然Vector包中有一個相當一般的接口（基於關聯的數據類型）。

有幾個項目用統一的接口來統一這些不同的半相關數據類型，所以我希望我們很快會看到一個結果。類似的容器類型。結果雖然不是微不足道的。

Answer 2

ListLike包似乎提供你在找什麼。我從來不明白爲什麼它不是更受歡迎。

ListLike除此之外，Prelude中沒有實現的一個原因是因爲如果不調用某些語言擴展（多參數類型類和fundeps或關聯類型），就無法做得很好。有三類容器來考慮：不關心，在他們所有的元素

1. 容器（如[]）
2. 容器，只爲特定元素實現（如字節串）
3. 集裝箱它們是元素上的多態，但需要一個上下文 （例如Data.Vector.Storable，它將使用可存儲的 實例保存任何類型的數據。

這裏是一個非常基本的ListLike風格類，而無需使用任何擴展：

class Listable container where 
    head :: container a -> a 

instance Listable [] where 
    head (x:xs) = x 

instance Listable ByteString where --compiler error, wrong kind 

instance Listable SV.Vector where 
    head v = SV.head --compiler error, can't deduce context (Storable a) 

這裏container有種*->*。這對於字節串不起作用，因爲它們不允許任意類型;他們有種類*。它也不適用於Data.Vector.Storable向量，因爲該類不包含上下文（Storable約束）。

你可以通過改變你的類定義要麼解決這個問題

class ListableMPTC container elem | container -> elem where 

或

class ListableAT container where 
    type Elem container :: * 

現在container有種*;它是一個完全應用的類型構造函數。也就是說，你的實例看起來像

instance ListableMPTC [a] a where 

但你不再是Haskell98。

這就是爲什麼即使是一個簡單的Listable類型接口也不重要的原因;當你有不同的集合語義來解釋時（例如隊列），它會變得更難一些。另一個非常大的挑戰是可變數據與不可變數據。到目前爲止，我所見過的每一次嘗試（除了一次）都會通過創建一個可變接口和一個不可變接口來解決這個問題。我所瞭解的將這兩者統一起來的界面之一是大腦彎曲，引發了一系列擴展，並且性能相當差。

附錄：字節串

完全猜想我的一部分，但我認爲我們堅持以字節串作爲進化的產物。也就是說，它們是低性能I/O操作的第一個解決方案，使用Ptr Word8來連接IO系統調用是有意義的。對指針的操作需要可存儲，並且最有可能的必要擴展（如上所述）使多態性工作不可用。現在很難克服它們的勢頭。具有多態性的類似容器當然是可能的，可存儲的vec​​torvector包實現了這一點，但它並沒有受到任何的歡迎。

字節串是否是多態的，對元素沒有任何限制？我認爲最接近Haskell的是這個數組類型。這不如低級IO的字節串好，因爲數據需要從指針解壓縮到數組的內部格式。數據也被裝箱，這增加了顯着的空間開銷。如果你想要無箱的存儲空間（更小的空間）和高效的C接口，指針是最好的選擇。一旦你有了一個Ptr，你需要Storable，然後你需要在類型類中包含元素類型，所以你需要擴展。這就是說，我認爲，通過適當的擴展可用，這對於任何單個容器實現（modulo mutable/immutable API）來說基本上是一個解決的問題。現在比較困難的部分是提出一組可用於許多不同類型結構（列表，數組，隊列等）的靈活類，並且足夠靈活以實用。我個人預計這會比較簡單，但我可能是錯的。

Answer 3

ByteString不是泛型類型。

在其他語言中，對於所有類似列表的數據結構，都有類似Sequence的東西。 我想這樣的作品，以正確的擴展名：

class Seq a b | a -> b where 
    head :: a -> b 
    isTail :: a -> Bool 

# ([a]) is a sequence of a's 
instance Seq [a] a where 
    head (x:xs) = x 
    isTail = (== []) 

# ByteString is a sequence of chars 
instance Seq ByteString Char 

或者試試呢？

type BS a = ByteString 
instance List BS 

Answer 4

在Haskell中爲類列表數據提供類型類沒有什麼價值。爲什麼？ 因爲懶惰。您可以編寫一個函數將數據轉換爲列表，然後使用該列表。該列表只會按照它的子列表和元素的要求進行構建，只要沒有引用保留在前綴中，它們的內存就有資格收集。

提供通用toList函數的類型類的值有所不同 - 但是，該函數已存在於Data.Foldable中。

所以基本上，解決的辦法是實現Data.Foldable並使用它的toList函數。

Answer 5

這樣的類的主要問題是，即使它存在，它只會提供表面相似性。

使用不同結構構建的相同算法的漸近線會有很大的不同。

在嚴格字節串的情況下，使用cons來建立它們是糟糕的，因爲每當你添加另一個字符時，你都會複製整個字符串。這個O（1）在列表上的操作將它變成對Bytestring操作的O（n）。

這導致O（n^2）行爲，當你實現第一個算法可能會想到，地圖，而建立一個列表或Data.Sequence.Seq與cons是線性時間，它可以是實現在O（n）字節串或向量以及一點點想法。

事實證明，這樣的類的實用程序，因爲這比實際更膚淺。

我不是說沒有找到好的設計，但是這樣的設計很難使用，並且優化設計的可用版本並且可能不會被認爲是Haskell 98.

我已經在我的keys包中提供了這個設計空間的一部分，它提供了很多用於索引到容器等的函數，但是我故意避免提供一個類似列表的API a），因爲它已經完成之前幾乎沒有成功，b。）因爲上面的漸近關注。

tl; dr您通常想要在底層操作的漸近性發生變化時非常不同地實現算法。

Answer 6

有兩種類型稱爲Foldable和Traversable，其目的是抽象列表和其他順序數據結構的一些common1行爲。並不是所有的數據結構都具有這些實例，但我不知道它們是否足夠透明，以至於它仍然可以對它們進行優化（是否有人對此有所瞭解？）

來源：Foldable and Traversable
又見這個答案 Why is Haskell missing 「obvious」 Typeclasses