ListWithGC.swift

import Foundation

struct IntList {
    static let NIL = IntList()

    var isEmpty: Bool {
        return cell == nil
    }

    var head: Int? {
        if cell == nil {
            return nil
        } else {
            return cell.memory.value
        }
    }

    var tail: IntList {
        if cell == nil {
            fatalError("getting tail of [].")
        }
        return IntList(cell: cell.memory.nextPtr)
    }

    var cell: Cell.Pointer

    init() {
        cell = nil
    }

    init(cell: Cell.Pointer) {
        self.cell = cell
    }

    init(range: Range<Int>) {
        var lis = IntList()
        for i in range.reverse() {
            lis = cons(i, lis)
        }
        self = lis
    }

    // cons
    init(_ v: Int, _ list: IntList) {
        let cdr = list.cell
        cell = Cell.alloc()
        cell.memory.value = v
        cell.memory.nextPtr = cdr
    }
}

func cons(v: Int, _ list: IntList) -> IntList {
    return IntList(v, list)
}

extension IntList {
    func toArray() -> [Int] {
        var array = [Int]()
        var xs = self
        while let v = xs.head {
            array.append(v)
            xs = xs.tail
        }
        return array
    }

    func length0() -> Int {
        if !isEmpty {
            return 1 + tail.length0()
        }
        return 0
    }

    func length() -> Int {
        var (len, xs) = (0, self)
        while !xs.isEmpty {
            (len, xs) = (len+1, xs.tail)
        }
        return len
    }

    func reverse() -> IntList {
        var (acc, xs) = (IntList.NIL, self)
        while let v = xs.head {
            (acc, xs) = (cons(v, acc), xs.tail)
        }
        return acc
    }


    func map(f: Int -> Int) -> IntList {
        if let v = head {
            return cons(f(v), tail.map(f))
        }
        return IntList.NIL
    }

    func filter(pred: Int -> Bool) -> IntList {
        if let v = head {
            if pred(v) {
                return cons(v, tail.filter(pred))
            }
            return tail.filter(pred)
        }
        return IntList.NIL
    }

    func append(xs: IntList) -> IntList {
        if let v = head {
            return cons(v, tail.append(xs))
        }
        return xs
    }
}

//////////////

enum List<T> {
    case Nil
    indirect case Cons(T, List<T>)
}

func cons<T>(x: T, _ xs: List<T>) -> List<T> {
    return .Cons(x, xs)
}

extension List {
    func filter(pred: T -> Bool) -> List<T> {
        if case let .Cons(x, xs) = self {
            if pred(x) {
                return .Cons(x, xs.filter(pred))
            }
            return xs.filter(pred)
        }
        return .Nil
    }

    func map<U>(f: T -> U) -> List<U> {
        guard case let .Cons(x, xs) = self else {
            return .Nil
        }
        return .Cons(f(x), xs.map(f))
    }

    func reverse() -> List {
        var (acc, ys) = (List.Nil, self)
        while case let .Cons(x, xs) = ys {
            (acc, ys) = (cons(x, acc), xs)
        }
        return acc
    }

    func append(ys: List<T>) -> List {
        if case let .Cons(x, xs) = self {
            return cons(x, xs.append(ys))
        }
        return ys
    }

    func length0() -> Int {
        if case let .Cons(_, xs) = self {
            return 1 + xs.length0()
        }
        return 0
    }

    func length() -> Int {
        var (len, ys) = (0, self)
        while case let .Cons(_, xs) = ys {
            (len, ys) = (len+1, xs)
        }
        return len
    }
}