/// Sorts a list by recursively partitioning its elements into sublists around a
/// pivot element.
func quickSort<T : Comparable>(l : [T]) -> [T] {
    switch destruct(l) {
        case .Empty:
            return []
        case let .Cons(x, xs):
            let lesser  = xs.filter({ $0 < x })
            let greater = xs.filter({ $0 >= x })
            return quickSort(lesser) + [x] + quickSort(greater)
    }
}

/// Lift any 1-ary function to a function over Maybes.
func liftA<A, B>(f : A -> B) -> Maybe<A> -> Maybe<B> {
    return { a in Maybe.pure(f) <*> a }
}

/// Lift any 2-ary function to a function over 2 Maybes.   
func liftA2<A, B, C>(f : A -> B -> C) -> Maybe<A> -> Maybe<B> -> Maybe<C> {
    return { a in { b in Maybe.pure(f) <*> a <*> b } }
}

/// Lift any 3-ary function to a function over 3 Maybes.
func liftA3<A, B, C, D>(f : A -> B -> C -> D) -> Maybe<A> -> Maybe<B> -> Maybe<C> -> Maybe <D> {
    return { a in { b in { c in Maybe.pure(f) <*> a <*> b <*> c } } }
}

let a = Maybe.just(6)
let b = Maybe<Int>.nothing()
let c = Maybe.just(5)

/// The result of adding 6 to Nothing is Nothing.
let nothing = liftA2(curry(+))(a)(b)

/// The result of adding 5 and 6 is 11
let something = liftA2(curry(+))(a)(c)

/// The result of packing 6, 5, and Nothing into a tuple is Nothing.
let noTupleHere = liftA3(pack3)(a)(b)(c)

/// Returns a stream of every Natural Number.  Because Streams are built up 
/// iteratively only on demand, we needn't load every element at once, 
/// just one at a time as they are requested. 
///
/// arr[0] == 0, arr[1] == 1, arr[2] == 2, ..., arr[n] == n
let naturalNumbers = iterate({ 1 + $0 })(0)

/// Returns a stream consisting of only the items in a given list.
///
/// arr[0] == "You", arr[1] == "Say", arr[2] == "Goodbye", arr[4] == "You", ...
let butISayHello = cycle(["You", "Say", "Goodbye"])

/// A version of the factorial function that, while appearing recursive,
/// actually evaluates in a constant amount of stack space.  As such it will
/// never smash the stack no matter how large an input it is given. 
func noSmashFactorial(x : Double, _ acc : Double = 1.0) -> Trampoline<Double> {
    if x <= 1 {
        return now(acc)
    }
    return later(noSmashFac(x - 1, acc * x))
}

/// The result of invoking this function is about 10^10^5.328.  Obviously, such
/// a number is completely unrepresentable in any bitwidth Swift gives us.  The 
/// thing to notice is that we would have pushed 50,000 frames onto the stack.  
/// Instead we push just 1. 
let inf = noSmashFactorial(50000).run()

/// An effect that, when executed, will pause for input from the terminal, then
/// shout it back at you.
let eff = interact(pack • map({ $0.toUpper() }) • unpack)
/// ...
/// Executes the effect with the current state of the world.
eff.unsafePerformIO()