創建Set數據類型

-2

所以我需要在Haskell中創建一個Set數據類型。創建Set數據類型

所以，我的問題的第一部分，我需要定義

type Set a = ...

我把它設置爲

type Set a = Set [a]

因爲套裝也只是α的名單，對不對？或者，將正確的方式做到這一點是

type Set a = ([a])

然後，在接下來的一部分，我需要實現的功能

setSuchThat :: (a -> Bool) -> (Set a)

功能需要一個特徵函數f並返回一組這樣僅當f（x）爲真時，值x（適當類型）纔在該集合中。因此，它在使用中的例子是，

setSuchThat (\x -> x == "coke")

所以我的問題是，現在，是該函數我基本上需要評估該功能讓「可樂」，然後將其添加到我的設置。我想我只是不明白，在這個功能中，我會去做這件事。

來源

2017-12-03 Frank

查找'filter'的源代碼。你會發現'setSuchThat = filter'。 – Alec

這將是不可能的。有無數的可能的字符串。程序如何知道它具有所有返回「真」的值？更現實的解決方案是使用'filter'。 – 4castle

如果你唯一需要實現的功能是'setSuchThat'，那麼讓我建議'輸入Set a = a - > Bool'。你應該找到'setSuchThat'這個微不足道的東西。 –

繼丹尼爾·瓦格納的建議，你可以定義一組作爲謂語指示元素是否在集合：

type Set a = a -> Bool

良好的措施，我將使用一個newtype，以使其更清晰這裏我們使用集：

newtype Set a = Set { contains :: a -> Bool }

然後setSuchThat只是包裝一個謂語Set：

setSuchThat :: (a -> Bool) -> Set a 
setSuchThat = Set

您可以使用contains功能的一組測試成員：

> setSuchThat (== "coke") `contains` "coke" 
True 

> setSuchThat (== "coke") `contains` "pepsi" 
False

所以空集只是setSuchThat (const False) - 對於任何給定的元素，它總是回答這個問題：「請問一套包含此元素？「沒有」。

insert :: (Eq a) => a -> Set a -> Set a 
insert x s = Set $ \ x' -> x == x' || s `contains` x' 

> insert "pepsi" (setSuchThat (== "coke")) `contains` "pepsi" 
True

像union其他功能很容易：

然後你就可以實現諸如insert由組成現有contains功能與新的功能擴展集新元素

union :: Set a -> Set a -> Set a 
union s1 s2 = Set $ \ x -> s1 `contains` x || s2 `contains` x 

> let sodas = setSuchThat (== "coke") `union` setSuchThat (== "pepsi") 

> sodas `contains` "coke" 
True 

> sodas `contains` "pepsi" 
True 

> sodas `contains` "water" 
False

作爲練習，請嘗試執行其他設置功能，如delete,intersect和difference。

此方法的一個缺點是每個查找都是線性-O（n） - 插入或刪除元素的數量。此外，你不能簡單地枚舉集將其轉換爲A的所有元素列表中，你只能列舉值和測試每一個是否是一個元素。不過，其中一個的優勢就是讓您輕鬆表示無限集;例如，setSuchThat (> 0)包含所有非負數。

這就是爲什麼標準Data.Set類型使用基於樹的數據結構，而不是功能，代表元素，它們的實際值。用這種方法，值可在不增加集的大小被刪除，並且，因爲它使用Ord代替Eq，實現了更有效的對數O（log n）的-lookups和插入。

來源

2017-12-03 04:19:21

要建立在什麼Jon Purdy打下了：

你需要考慮的Set a = a -> Bool的作爲，你必須一起工作的限制。當您看到setSuchThat :: (a -> Bool) -> (Set a)時，您可以將其讀取爲與setSuchThat :: (Set a) -> (Set a)或setSuchThat :: (a -> Bool) -> (a -> Bool)相同。 setSuchThat有點像一個mcguffin，它只是在那裏使用更清晰的功能 - 這是沒有必要的。你正在做

一切都是以功能f並將其應用到變量x。的setSuchThat整個的一點是要傳遞f和x只有f x返回。

來源

2017-12-03 07:42:40 Fiend394

創建Set數據類型

回答

相關問題