Функция набора Scala

Question

В курсе Stanford Scala я наткнулся на следующее задание:

Упражнение 1 - Устанавливает как функции:

В этом упражнении мы представим множества как функцииот Ints до Booleans:

type Set = Int => Boolean

a ) Напишите функцию "set", которая принимает параметр Int и возвращает Set, содержащий этот Int.

b ) Напишите функцию «содержащий», которая принимает Set и Int в качестве параметров и возвращает true, если Int находится в множестве, и false в противном случае.

c ) Записываетфункции "union", "intersect" и "minus", которые принимают два набора в качестве параметров и возвращают набор.

d ) Можете ли вы написать функцию "подмножество", которая принимает два наборав качестве параметров и возвращает true, если первое является подмножеством второго, и false в противном случае?

Решения для a , b и c довольно просты:

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)

, но это, вероятно, не правильный путь.

Answer 1

Я не думаю, что это возможно без перебора всех целых чисел.Для псевдо-доказательства посмотрите на нужный тип:

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

Каким-то образом мы должны создать Boolean, когда все, с чем мы должны работать, это наборы (a, b) типа Int => Boolean и целочисленного равенства (Int, Int) => Boolean.Из этих примитивов единственный способ получить значение Boolean - начать со значений Int.Поскольку у нас в руках нет конкретных Int, единственный вариант - перебрать их всех.

Если бы у нас был волшебный оракул, isEmpty: Set => Boolean, история была бы другой.

Последний вариант - кодировать «ложь» как пустой набор и «истина» как что-либо еще, таким образом изменяя желаемый тип на:

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

С этой кодировкой логическое «или» соответствует операции объединения объединения, но я не знаю, что логические «и» или «нет» могут быть легко определены.

Answer 2

У нас есть

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.

Не установлен A эквивалентно Set B

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

Answer 3

Вот еще одна версия с использованием функции содержит:

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)

Answer 4

Если есть два набора A и B, то пересечение A B является подмножеством A и B. Математически доказано: A ∩ B ⊆ A and A ∩ B ⊆ B. Функция может быть написана так:

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

или

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

Answer 5

Позже в упражнениях Coursera вводятся ограниченные множества, а затем forall () и существует () как универсальные и экзистенциальные квантификаторы через границы.subset () не был в упражнениях, но похож на forall.Вот моя версия subset ():

// 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)
}

Answer 6

Я согласен с Киптоном Барросом, вам нужно будет проверить все значения для 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)