Реализация множества без использования переменных на Scala

January 29, 2019 14:58

Множество - это тип и структура данных, являющаяся реализацией обычного математического объекта "множество". Множества позволяют хранить в себе данные: ограниченное число значений некоторого типа, но без установленного порядка. Кроме того, значения не должны повторяться. В программировании нет возможности сделать множество абсолютно бесконечным - и это единственное отличие от математического множества (конечность и бесконечность). Реализация множества должна предусматривать некоторые стандартные операции над множествами:

  • задание множества;
  • проверка на содержание элемента в множестве;
  • объединение;
  • пересечение;
  • разность;
  • и другие.

Пример реализации множества без использования переменных на языке программирования Scala:

object lab_06 {
    
    type Set = Int => Boolean
    
    def contains(s: Set, elem: Int): Boolean = s(elem)
    
    def singletonSet(elem: Int): Set = _ == elem

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

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

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

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

    //  -1000 до 1000

    def forall(s: Set, p: Int => Boolean): Boolean = {
        def _forall(current: Int): Boolean = {
            if (current > 1000) true
            else if (s(current)) p(current) && _forall(current + 1)
            else _forall(current + 1)
        }   

        _forall(-1000)
    }

    def exists(s: Set, p: Int => Boolean): Boolean = {
        def _exists(current: Int): Boolean = {
            if (current > 1000) false
            else if (s(current)) p(current) || _exists(current + 1)
            else _exists(current + 1)
        }

        _exists(-1000)
    }

    def map(s: Set, f: Int => Int): Set = v => exists(s, p => f(p) == v)

    def main(args: Array[String]) {
        val set = union(
                    union(
                        union(
                            singletonSet(1), singletonSet(2)), 
                        singletonSet(3)), 
                    singletonSet(4))

        println(set(1), 
                set(2), 
                set(3), 
                set(4), 
                set(5))

        println(forall(set, _ > 0), 
                forall(set, _ > 1), 
                exists(set, _ > 3), 
                exists(set, _ > 4))

        println(set(1), 
                set(2), 
                set(3), 
                set(4), 
                set(5))

        val mapped = map(set, _ * 10)

        println(mapped(10), 
                mapped(2), 
                mapped(3), 
                mapped(40), 
                mapped(5))
    }    
}