Functional list implementation in Swift

List.swift

public final class Box<T> {
    public let value: T

    public init(_ value: T) {
        self.value = value
    }
}

/// Immutable list of elements of type T
/// 
/// Several methods are implemented using simple naive recursive
/// algorithms, which may use a lot of stack space. Beware of
/// stack overflows when using large lists.
public enum List<T>: Printable, ArrayLiteralConvertible, CollectionType {
    case Nil
    case Cons(Box<T>, Box<List<T>>)

    /// Construct list from head and tail
    public static func cons(head: T, _ tail: List<T>) -> List<T> {
        return .Cons(Box(head), Box(tail))
    }

    /// Construct list from array of elements
    public static func fromArray(elements: [T]) -> List<T> {
        var list: List<T> = .Nil
        for elem in lazy(elements).reverse() {
            list = cons(elem, list)
        }
        return list
    }

    /// Construct list from a sequence
    public static func fromSequence<S : SequenceType where S.Generator.Element == T>(s: S) -> List<T> {
        var list: List<T> = .Nil

        // It seems like we should be able to do "for elem in s { ... }" here, but
        // the compiler gives us error messages about the types.  Workaround is to
        // explicitly use the generator and annotate the types.
        //
        // Credit: https://gist.github.com/airspeedswift/a40d9e70f813863ab324

        var generator = s.generate()
        while let elem: T = generator.next() {
            // Note that this builds the list from back to front, so we'll need to reverse the result
            list = cons(elem, list)
        }
        return list.reverse()
    }

    /// Initialize from array literal
    public init(arrayLiteral elements: T...) {
        self = List.fromArray(elements)
    }

    /// Get string representation
    public var description: String {
        switch self {
        case .Nil:
            return "Nil"
        case let .Cons(h, t):
            return "\(h.value), \(t.value.description)"
        }
    }

    /// Determine whether list is empty
    public var isEmpty: Bool {
        switch self {
        case .Nil: return true
        default: return false
        }
    }

    /// Get number of elements
    public var count: Int {
        switch self {
        case .Nil: return 0
        case .Cons(_, let t): return 1 + t.value.count
        }
    }

    /// Get first element
    public var head: T {
        switch self {
        case let .Cons(h, _): return h.value
        default: assert(false, "cannot evaluate Nil.head")
        }
    }

    /// Get remaining list without first element
    public var tail: List<T> {
        switch self {
        case let .Cons(_, t): return t.value
        default: assert(false, "cannot evaluate Nil.tail")
        }
    }

    /// Get list of the first N elements
    public func take(n: Int) -> List<T> {
        assert(n >= 0, "take argument must be non-negative")
        return n == 0 ? .Nil : List.cons(head, tail.take(n - 1))
    }

    /// Get list with the first N elements removed
    public func drop(n: Int) -> List<T> {
        assert(n >= 0, "drop argument must be non-negative")
        return n == 0 ? self : tail.drop(n - 1)
    }

    /// Return list of elements in reversed order
    public func reverse() -> List<T> {
        return List.reverse(self, accumulator: .Nil)
    }

    private static func reverse(remainder: List<T>, accumulator: List<T>) -> List<T> {
        switch remainder {
        case .Nil:
            return accumulator
        case let .Cons(h, t):
            return reverse(t.value, accumulator: List<T>.cons(h.value, accumulator))
        }
    }

    /// Return list with new element added to the tail
    public func append(newElement: T) -> List<T> {
        switch self {
        case .Nil:
            return List.cons(newElement, .Nil)
        case let .Cons(h, t):
            return List.cons(h.value, t.value.append(newElement))
        }
    }

    /// Return list with new elements appended to the tail
    public func extend(newElements: List<T>) -> List<T> {
        switch self {
        case .Nil:
            return newElements
        case let .Cons(h, t):
            return List.cons(h.value, t.value.extend(newElements))
        }
    }

    /// Return the result of repeatedly calling `combine` with an
    /// accumulated value initialized to `initial` and each element of
    /// `self`, in turn
    public func reduce<U>(initial: U, combine: (U, T) -> U) -> U {
        return Swift.reduce(self, initial, combine)
    }

    /// Return a list containing the results of calling
    /// `transform(x)` on each element `x` of `self`
    public func map<U>(transform: (T) -> U) -> List<U> {
        switch self {
        case .Nil:
            return .Nil
        case let .Cons(h, t):
            return List<U>.cons(transform(h.value), t.value.map(transform))
        }
    }

    /// Return a list containing the elements of `self` for which
    /// `includeElement(x)` is true
    public func filter(includeElement: (T) -> Bool) -> List<T> {
        switch self {
        case .Nil:
            return .Nil
        case let .Cons(h, t):
            if includeElement(h.value) {
                return List.cons(h.value, t.value.filter(includeElement))
            }
            else {
                return t.value.filter(includeElement)
            }
        }
    }

    /// Return a copy of the list sorted according to `isOrderedBefore`
    public func sorted(isOrderedBefore: (T, T) -> Bool) -> List<T> {
        // Instead of using a list-sort algorithm, just convert
        // to an array, sort that, then convert back to a list
        let sortedArray = self.toArray().sorted(isOrderedBefore)
        return List.fromArray(sortedArray)
    }

    /// Return array of list elements
    public func toArray() -> Array<T> {
        return Array<T>(self)
    }

    /// Return sequence generator
    public func generate() -> ListGenerator<T> {
        return ListGenerator(self)
    }

    /// The position of the first element in a non-empty list
    public var startIndex: Int {
        return 0
    }

    /// The collection's "past the end" position.
    public var endIndex: Int {
        return count
    }

    public subscript(index: Int) -> T {
        assert(index >= 0, "subscript argument must be non-negative")
        if index == 0 {
            return head
        }
        else {
            return tail[index - 1]
        }
    }
}

/// Sequence generator for a List<T>
public struct ListGenerator<T>: GeneratorType {
    var list: List<T>

    public init(_ list: List<T>) {
        self.list = list
    }

    public mutating func next() -> T? {
        switch list {
        case .Nil:
            return nil
        case let .Cons(h, t):
            self.list = t.value
            return h.value
        }
    }
}

/// Create a list from elements
public func list<T>(elements: T...) -> List<T> {
    return List<T>.fromArray(elements)
}


// Examples

// List of integers
let intList = list(1, 2, 3, 4, 5, 6, 7, 8, 9)
intList.description
intList.count
intList.head
intList.tail.description
intList.take(3).description
intList.drop(3).description
intList.reverse().description
let intArray = intList.toArray()

intList[2]

intList.append(777).description
list(1, 2, 3).extend(list(4, 5, 6)).description

intList.reduce(0, combine: +)

let intListToDoubleList = intList.map { Double($0) }
intListToDoubleList.description

let oddIntList = intList.filter { $0 % 2 == 1 }
oddIntList.description

list(6, 5, 4, 3, 22, 45).sorted(<).description

// List of strings
let stringList = list("Hello", "world")
stringList.description
stringList.head
stringList.tail.description
stringList.reverse().description

// List of doubles, constructed from array literal
let doubleList: List<Double> = [1.23, 4.56, 7.89, 10]
doubleList.description
doubleList.head
doubleList.tail.description