Basis

The Basis is an exploration of pure declarative programming and reasoning in Swift. It by no means contains idiomatic code, but is instead intended to be a repository for structures and ideas grounded in theory and mathematics. Present in this repository are the necessary components to handle system interaction, control, data flow, and a number of extensions and improvements to the Swift Standard Library and its structures. Higher-level APIs and structures are generally excluded from the Basis to be implemented in other libraries.

It Gets Better!

Swift provides an excellent opportunity to not just witness, but actually understand the formalization of many seemingly "complex" and abstract algebraic structures without having to learn Haskell or ML or any of the other famous FP languages. The documentation of types in this repository serves as a way to deserialize a lot of the complex terms and jargon you may come across in these languages. In this way, the Basis can be regarded as an encyclopedia of common techniques and practices rather than a simple tutorial. As such, if the documentation is too dense or unreadable, it means this library is failing one of its unit tests! Clarification or rewrites of documentation to serve the broader community are a priority and a promise.

Any questions or comments should be made into issues, or pull requests if you feel you can word it better.

Let's make the world a bit less scary.

Getting Started

Basis comes wrapped up as a framework and iOS and OS X. Simply add the project as a submodule, drag it to your project's file tree, and add it as a framework dependency for your build. When all is said and done, just

import Basis

Introduction

Because The Basis places emphasis on functions over structures, the majority of the functions in this repository are free and combinatorial. Programming with them then becomes a matter of selecting the proper combinators and compositional operators to achieve a desired type signature.

To take a famous example from Haskell:

/// 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)
    }
}

Or perhaps a more convoluted example:

/// 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 } } }
}

With such an architecture in place, we can replace the classic if-let pattern for optionals with calls to liftA2:

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)

We can also exploit the tools Swift has given us for laziness and use them to build up infinite data structures despite having only a finite amount of memory.

/// 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"])

Or even use laziness to help with control flow.

/// 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()

We're no strangers to the Real World either. Swift is a profoundly imperative language at heart, but that doesn't mean we can't do something about it. Enter the IO Monad. Our IO Monad is the incarnation of an effect that has yet to happen.

/// 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()

System Requirements

The Basis supports OS X 10.9+ and iOS 7.0+

License

The Basis is released under the MIT license.

Further Reading

• SML
• Haskell
• TTFP