2017-12-03 24 views
-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") 

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

+0

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

+1

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

+1

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

回答

4

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

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,intersectdifference

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

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

1

要建立在什麼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整個的一點是要傳遞fx只有f x返回。

相關問題