Scala集合的构建——基于集合的数学定义
deltamaster
posted @ Jun 20, 2014 08:38:25 PM
in Scala
with tags
Scala 集合 函数 Functional Programming
, 4405 阅读
在过程式编程语言中，我们一般用某种collection来定义集合，集合中元素的数量越多，collection就会占用越大的内存空间，如果集合元素无限多，那么collection就要占用无限大的内存空间，那么在实际的计算机上就不可行了。
为了让集合的构建更加灵活，我们需要从集合的数学定义出发来进行实现。对于一个集合S={x|p(x)}，表示如果对于x，p(x)条件为真，x就是集合S的元素。所以，集合的本质就是定义了元素x和集合关系的函数p(x)，p(x)接受某种类型的参数x，返回Boolean。
type Set = Int => Boolean
这是Scala的类型定义，含义是定义一个新类型Set，等价于接受一个Int类型参数，返回Boolean的函数。
我们再定义一个函数判断x是不是集合s的元素。
def contains(s: Set, elem: Int): Boolean = s(elem)
我们现在就可以尝试定义一个集合。
def odd: Set = {_ % 2 != 0}
def r1 = contains(odd, 1) // true
def r2 = contains(odd, 2) // false
这里odd就是所有奇数的集合。
然后让我们看看如何构建另一种基本的集合，只包含一个元素的集合。
def singletonSet(elem: Int): Set = {_ == elem}
def s: Set = singletonSet(100)
def r1 = contains(s, 100) // true
def r2 = contains(s, 101) // false
在定义s的时候使用的elem，被用于将来的比较，这样，我们通过比较传入s的参数和保存下来的elem，就可以知道传入s的参数是不是集合s的元素。
上面这些是集合的基本的building blocks，接下来让我们来定义交、并、差等集合运算，让集合产生新的集合。由于函数式编程的高阶函数特性，构建这种方法非常简单。
def union(s: Set, t: Set): Set = {
x: Int => contains(s, x) || contains(t, x)
}
def intersect(s: Set, t: Set): Set = {
x: Int => contains(s, x) && contains(t, x)
}
def diff(s: Set, t: Set): Set = {
x: Int => contains(s, x) && !contains(t, x)
}
def filter(s: Set, p: Int => Boolean): Set = {
x: Int => contains(s, x) && p(x)
}
上述函数定义完全遵循数学上集合的运算规则。
def leap: Set = union(diff({_ % 4 == 0}, {_ % 100 == 0}), {_ % 400 == 0})
def r1 = contains(leap, 2000) // true
def r2 = contains(leap, 2100) // false
上面是所有闰年的集合定义，简单组合一下上面的方法就可以构建了。
Sep 07, 2021 03:00:12 PM
I think this is one of the most significant information for me. And i’m glad reading your article. But should remark on some general things, The web site style is perfect, the articles is really great : D. Good job, cheers <a href="https://123movies.hair/">123 movies</a>
Sep 09, 2021 09:35:50 PM
I was reading your article and wondered if you had considered creating an ebook on this subject. Your writing would sell it fast. You have a lot of writing talent. https://docs.google.com/spreadsheets/d/1ntiogcbDulo3Vl9Htd7Jl9Xy-2kUp7-F33vbQ4q67Uc/edit#gid=409280497
Aug 09, 2022 06:09:35 PM
BSNL is installing Bharat Net a country-wide fiber optic cable for internet connectivity in many of the panchayats, and on the other hand, ISP brought the same fibernet technology to your doorstep directly and through TIPs. BSNL Fiber plans Telecom Infrastructure Providers (TIPs) with new Fiber plans covering many isolated pockets in all BSNL circles of the country for 50Mbps to 300 Mbps internet speed on providing with BSNL FTTH Plans along with FREE ONT as per the possibility.
Sep 12, 2022 05:56:16 PM
GSEB STD-4 Model Paper 2023 Pdf Download for Gujarat State Elementary Level Primary School 4th Class Question Paper Pdf with Answers for Gujarati Medium, Hindi Medium, English Medium & Urdu Medium Students of Gandhinagar Board at GSEB STD-4 Model Paper. Subject experts of the state and teaching staff of private schools have prepared and suggested the GSEB STD-4 Model Paper 2023 Pdf for Part-A, Part-B, Part-C and Part-D exams. Set wide solved question paper suggested as Gujarat Board 4th Class Model Paper 2023.
Jan 19, 2023 12:04:55 PM
Scala collections provide a powerful and efficient way of organizing data based on the mathematical definition of collections. This structure offers a simple method of representing and manipulating data, which makes it ideal for use in a wide range of applications. Additionally, Scala collections are thoroughly tested and optimized, ensuring that they are both reliable and performant. With these features, Scala collections are an excellent hemp oil for pain choice for developers who want to handle their data in an organized and effective way.
Jan 23, 2023 02:59:40 PM
K2 challan also referred to as Khajane 2, an integrated financial management system from the Government of Karnataka. The K2 has been brought into working with an aim to manage the financial business of the government. khajane 2 challan It works to simplify the process of remittance of departments under government by bringing an option of anywhere-anytime payment options. Firstly every department under the government of Karnataka will have access to Khajane 2 which allows their customers to remit to the government through the easy payment links provided.