2011-09-26 71 views
15

有沒有人可以向我解釋爲什麼Haskell中沒有定義Set數據類型?爲什麼Haskell中沒有內置的Set數據類型?

旁註: 我只是在學習Haskell作爲集合論非常重要的邏輯課程的一部分,因此在Haskell中擁有集合的概念將非常方便。有一個列表和刪除重複(可能排序)會導致一組,但我很好奇,如果有一個特定的原因,爲什麼它不是內置的?

+3

**版主說明**這個問題下的評論主要是噪音,或對噪音的反應,他們已被刪除。請保持評論建設性和主題。 –

+0

我看到建議使用列表的答案/評論。一份清單並不是一套有效的替代品。在無序列表中查找元素的時間隨着列表大小的增加而增加,在一個集合中,預計會保持不變。 – ribamar

回答

26

正如其他答案指出的那樣,「爲什麼Haskell中沒有設置數據類型?」被誤導:there is a Set data type

如果你想知道爲什麼Set不是「內置」給Haskell的,你可能會問兩件事之一。

要回答前者,這是因爲該語言足夠強大,足以表達一個集合的概念,而無需將其烘焙。作爲一種高度重視函數式編程的語言,元組和列表的特殊語法內置,但即使簡單的數據類型,如Bool在Prelude中定義。

爲了回答後者,再一次強調函數式編程,大多數Haskeller傾向於使用列表。列表monad表示非確定性選擇,並且通過允許重複,您可以表示加權選項。

備註how similar list comprehension syntax is to set notation。必要時,您總是可以使用Set.fromList將列表轉換爲「真實」組。作爲對Barry的beg sh聲,這與使用Python的set()方法相似; Python也具有列表解析功能。

+0

從技術上講,'Data.Set'在GHC中,但它不在GHC中的Haskell 98或2010報告中 – user102008

+0

@ user102008「?它在[Haskell Platform](http://hackage.haskell.org/platform/)中包含的[containers package](http://hackage.haskell.org/package/containers)中,我不確定你的意思是說它在「GHC」中。 –

+0

@DanBurton,即使你沒有獲得平臺,GHC也可以使用'containers'軟件包。 – ivanm

9

它存在爲Data.Set。然而,正如你所說,它可以在list之上實現,因此不需要來構建語言,我認爲這就是爲什麼它在模塊中而不是語言本身定義的一部分。

+0

那麼,列表也可以使用其他的東西來定義... –

+0

@DietrichEpp是的,但如果你添加到列表作爲一個明確的缺點鏈的話,語法將非常沉重。 – mb14

+1

@ mb14'(:) == Cons';對於顯式有限列表和作爲各種'枚舉{From} {Then} {To}'函數的包裝,只有語法糖。 – ivanm

11

在更哲學的層面---一個集合的數學概念和一個Haskell集合實現之間永遠不可能存在嚴格的對應關係。爲什麼不?那麼,類型系統,對於初學者來說。一個數學集可以有任何東西:{x | x is a positive integer, i < 15}是一組,但也是{1, tree, ham sandwich}。在Haskell中,Set a需要保存某種特定的類型。將雙精度和浮點數放入同一個集合將不會檢測。正如其他人所說,如果你需要做一些類似設置的事情,不介意類型限制,Data.Set存在。它不在Prelude中,因爲列表通常更實用。但實際上,從語言設計的角度來看,把數學集作爲一種數據類型是沒有意義的。集合比這更基礎。你沒有集合,數字和列表;你有一組數字和一組列表。遞歸類型的力量往往掩蓋了這種區別,但它仍然是真實的。

雖然在Haskell中有一個地方,我們定義任意集合,然後在這些集合上定義函數。 Haskell中最接近的集合數學概念是類型系統本身。

+1

很多時候,數學中的集合被認爲是在「宇宙」(http://en.wikipedia.org/wiki/Universe_(mathematics))的背景下 – user102008

+0

@Zopa:你仍然可以用sum-類型。 – ivanm

+0

的確如你所說,「在Haskell中,一個'Set a'需要保存某種特定的類型」。但是'a'實例化的類型可能是一種存在類型,其中'1''''''''''''''''''''''''''''''''''''''''''''''''''假設'樹'和'火腿三明治'本身是很好的類型術語......你可以用這樣的一套有意義的方式來做這件事我不知道;)但是我同意你的結論,那就是_types本身_是Haskell對數學集合的概念最接近的東西。 –

相關問題