Recursive enumeration in Swift 4.2

RecursiveEnumerations.swift

import UIKit

// Helpers

// takes a list and checks if a given predicate is true for every element O(n)
func all<T>(_ xs: [T], predicate: (T) -> Bool) -> Bool {
    for x in xs {
        if !predicate(x) {
            return false
        }
    }
    return true
}

// Recursive enumerations

// Implement Set Library

func emptySet<T>() -> Array<T> {
    return []
}

func isEmptySet<T>(set: [T]) -> Bool {
    return set.isEmpty
}

func setContains<T: Equatable>(x: T, set: [T]) -> Bool {
    return set.contains(x)
}

func setInser<T: Equatable>(x: T, set: [T]) -> [T] {
    return setContains(x: x, set: set) ? set : [x] + set
}


// Improving performance Binary Search tree with enums

enum Tree<T> {
    case leaf
    indirect case Node(Tree<T>, T, Tree<T>)
}

/// Usage Example

let leaf: Tree<Int> = Tree.leaf
let five: Tree<Int> = Tree.Node(leaf, 5, leaf)

/// create a tree with a single values

func single<T>(x: T) -> Tree<T> {
    return Tree.Node(Tree.leaf, x, Tree.leaf)
}

/// Count number of elements in a tree recursevely:

func count<T>(tree: Tree<T>) -> Int {
    switch tree {
    case .leaf: return 0
    case .Node(let leftTree, _, let rightTree):
        let value = 1
        return value + count(tree: leftTree) + count(tree: rightTree)
    }
}

/// Calculate the array of elements stored in a tree:

func elements<T>(tree: Tree<T>) -> [T] {
    
    switch tree {
    case .leaf: return []
    case .Node(let leftTree, let value, let rightTree):
        return elements(tree: leftTree) + [value] + elements(tree: rightTree)
    }
}

print(elements(tree: five))


/// Building Set library again but with recursive enumeration
func emptySet<T>() -> Tree<T> {
    return Tree.leaf
}

func isEmptySet<T>(tree: Tree<T>) -> Bool {
    switch tree {
    case .leaf: return true
    case .Node(_,_,_): return false
    }
}

/// Writing an inefficient assert function to validate if a Tree is a binary search tree.

func isBST<T: Comparable>(tree: Tree<T>) -> Bool {
    
    switch tree {
    case .leaf: return true
    case .Node(let leftTree, let value, let rightTree):
        let leftElements = elements(tree: leftTree)
        let rightElements = elements(tree: rightTree)
        return all(leftElements) { $0 < value }
            && all(rightElements) { $0 > value }
            && isBST(tree: leftTree)
            && isBST(tree: rightTree)
    }
}

func setContains<T: Comparable>(x: T, tree: Tree<T>) -> Bool {
    
    switch tree {
    case .leaf: return false
    case .Node(_, let value, _) where x == value: return true
    case .Node(let leftTree, let value, _) where x < value: return setContains(x: value, tree: leftTree)
    case .Node(_, let value, let rightTree) where x > value: return setContains(x: x, tree: rightTree)
    default: fatalError("The impossible occur")
    }
}

func setinsert<T: Comparable>(x: T, tree: Tree<T>) -> Tree<T> {
    
    switch tree {
    case .leaf: return single(x: x)
    case .Node(_, let value, _) where x == value: return tree
    case .Node(let leftTree, let value, let rightTree) where x < value: return Tree.Node(setinsert(x: x, tree: leftTree), value, rightTree)
    case .Node(_, let value, let rightTree) where x > value: return setinsert(x: x, tree: rightTree)
    default: fatalError("The impossible occur")
    }
}

// Functional Programming in Swift page 92.