2011-08-05 235 views
11

在斯坦福斯卡拉當然,我已經遇到了以下任務:斯卡拉設置功能

練習1 - 設置爲功能:

在這個練習中,我們將代表從INTS到布爾臺的功能:

type Set = Int => Boolean 

一個)寫功能的「設置」接受一個int參數,並返回包含該詮釋一個集。

b)編寫一個函數「contains」,它將Set和Int作爲參數,如果Int在Set中則返回true,否則返回false。

c)編寫函數「union」,「intersect」和「minus」,它們以兩個集合作爲參數並返回一個Set。

d)你能寫一個函數「子集」,它將兩個集作爲參數,並返回true,如果第一個是第二個子集,否則返回false?

一個bç是相當簡單:

def set(i: Int): Set = n => n == i 

def contains(s: Set, i: Int) = s(i) 

def union(a: Set, b: Set): Set = i => a(i) || b(i) 

def intersect(a: Set, b: Set): Set = i => a(i) && b(i) 

def minus(a: Set, b: Set): Set = i => a(i) && !b(i) 

但是是有d任何優雅的解決方案? 當然,嚴格來說,答案d是「是」,我可以寫的東西,如:

def subset(a: Set, b: Set) = Int.MinValue to Int.MaxValue filter(a) forall(b) 

但這可能是不正確的做法。

+2

我認爲*爲*正道。 – Malvolio

+0

該課程與斯坦福大學沒有任何關係 –

+0

@Seth從斯坦福大學的課程中,不是當前Coursera的課程,即使第二個任務幾乎相同。請注意,它沒有綁定/綁定提示,這btw回答了我的問題。 – Grozz

回答

9

我不認爲這是可能的,如果沒有迭代所有的整數。對於僞證據,看看所需的類型:

def subset: (a: Set, b: Set): Boolean 

不知怎的,我們必須產生Boolean當所有我們必須用Int => Boolean類型是一組(ab),以及整平等工作(Int, Int) => Boolean。從這些原語中,獲得Boolean值的唯一方法是從Int值開始。由於我們手中沒有任何特定的Int,唯一的選擇是遍歷所有這些。

如果我們有一個神奇的預言,isEmpty: Set => Boolean,故事會有所不同。

最後一個選項是編碼「假」作爲空集和「真」作爲別的,從而改變了所希望的類型:

def subset: (a: Set, b: Set): Set 

通過這種編碼,邏輯「或」對應到設定的聯合操作,但我不知道邏輯「和」或「不是」可以很容易地定義。

0

我同意基普頓巴羅斯,你將不得不檢查Ints的所有值,因爲你想證明forall x, a(x) implies b(x)

關於它的優化,我可能會寫:

def subset(a: Set, b: Set) = Int.MinValue to Int.MaxValue exists(i => !a(i) || b(i)) 

因爲!a(i) || b(i)相當於a(i) implies b(i)

+0

從哪裏獲得該功能「存在」?它是在什麼地方定義的,或者你沒有定義它? –

+1

「Int.MinValue to Int.MaxValue」表達式創建了一個Range類型,它繼承自IterableLike,TraversableLike,TraversableOnce,最後來自GenTraversableOnce,這是定義函數exists的地方。查看http://www.scala-lang.org/api/current/index.html#scala.collection.immutable.Range –

+1

上的文檔。謝謝,那一天,我似乎無視它是一個方法調用的範圍內。 –

0

在Coursera練習後來有界引入集,然後FORALL()和存在()作爲邊界上的普遍量詞和存在量詞。 subset()不在練習中,但與forall相似。這裏是我的版本的子集的():

// subset(s,p) tests if p is a subset of p returning true or false 
def subset(s: Set, p: Set): Boolean = { 
    def iter(a: Int): Boolean = { 
    if (a > bound) { true 
    } else if (contains(p, a)) { 
     if (contains(s, a)) iter(a + 1) else false 
    } else iter(a+1) 
    } 
    iter(-bound) 
} 
1

我們有

Set A = 
    Returns the intersection of the two given sets, 
    the set of all elements that are both in `s` and `t`. 

Set B = 
    Returns the subset of `s` for which `p` holds. 

沒有設置相當於集合B

def filter(s: Set, p: Int => Boolean): Set = intersect(s, p) 
-1

如果有兩套A和B那麼A相交B是A和B的子集。數學證明:A∩B⊆A和A∩B⊆B.函數可以這樣寫: def filter(s:Set,p:Int => Boolean): Set = x => s(x)&(s:Set,p:Int => Boolean))()()xx xx xx xx xxx xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx :設置=相交(S,p)

+0

雖然聲明是正確的,但它不提供和回答問題。 – mins

+0

@mins答案由Ronak給出。我只想說兩組交集是這兩組中任何一組的集合。我也添加了確切的答案。 – Icoder

0

下面是使用它的另一個版本包含的功能:

def union(s: Set, t: Set): Set = x => contains(s,x) || contains(t,x) 

def intersect(s: Set, t: Set): Set = x => contains(s,x) && contains(t,x) 

def diff(s: Set, t: Set): Set = x => contains(s,x) && !contains(t,x) 

def filter(s: Set, p: Int => Boolean): Set = x => contains(s, x) && p(x)