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

В курсе Стэнфорда Scala я столкнулся с следующим назначением:

Упражнение 1 - Наборы как функции:

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

type Set = Int => Boolean

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

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

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

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)

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

Ответы

Ответ 1

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

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

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

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

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

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

С помощью этой кодировки логический "или" соответствует операции set union, но я не знаю, что логическое "и" или "не" может быть легко определено.

Ответ 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.

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

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

Ответ 3

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

Ответ 4

В дальнейшем в упражнениях Coursera вводятся ограниченные множества, а затем forall() и exists() как универсальные и экзистенциальные кванторы по границам. Подмножество() не было в упражнениях, но похоже на 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)
}

Ответ 5

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

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)

Ответ 6

Если существует два набора A и B, то A пересекает B, является подмножеством A и B. Математически доказано: A ∩ B ⊆ A и A ∩ B ⊆ B. Функция может быть записана следующим образом: def filter (s: Set, p: Int = > Boolean): Set = x = > s (x) && & && р (х) или def intersect (s: Set, t: Set): Set = x = > s (x) && & т (х) def filter (s: Set, p: Int = > Boolean): Set = intersect (s, p)