Sums

enum Either<A, B> {
  Left(a: A);
  Right(b: B);
}

Secondly, Haxe has syntax for sum types (actually generalized algebraic data types) and pattern matching.

Whoah, wait a minute, generalized algebraic data types? That's definitely a scary term! Hopefully we'll be able to make that a little less scary as we go along here, but for the moment I do want to speak really briefly about sum types. Haxe calls them 'enums' which is helpfully suggestive for folks coming from languages like C and Java.

Unlike what's typically termed an enum, values of a sum type can carry around additional data, which you can retrieve when you pattern match on a value of that type. Each term of the 'enum' block is called a 'constructor' for that data type - just to be clear, 'Left' isn't a type, it's a constructor for a value of type 'Either of A and B'.

Types like this, where you can have multiple different constructors for values of the same type, are really, really important, so important that I kind of think that languages that lack first-class support for them are really crippled. The reason that they're so important is that, when building an application, it's really useful to think about the state space of the application, and more specifically how to minimize the number of states there are within that space. Does everybody know what I'm talking about here?

(If not, proceed down)

Finally, it does not have higher kinded types, which means that a whole lot of abstractions that folks from the Haskell and Scala worlds find invaluable are not actually representable in the language. While this is in my opinion a terrible deficiency, for the purposes of this talk I'm going to spin it as an advantage, because it forces me to use examples that are reproducible in other languages that lack higher-kinded types, like Java and C# and Swift, which are probably what many of you are stuck using. More importantly though, it means that the examples that you see will be very concrete. In functional proramming, we love to use a lot of high-level abstractions because they let us avoid writing a lot of boilerplate code and help us to avoid coupling, but in my experience for learning it's necessary to progress from concrete examples to the abstract. Here, all that you're going to see are the concrete bits, because the language doesn't actually let me represent the abstracted versions.

How Many States?

var b: Bool = /* censored */;

var i: Int = /* censored */;

typedef BoolIntPair = { b: Bool, i: Int };

enum Either<A, B> {
  Left(a: A);
  Right(b: B);
}

typedef BoolOrInt = Either<Bool, Int>;

How Many States?

var b: Bool = /* censored */;
// 2 states

var i: Int = /* censored */;
// 2^32 states

var x: { b: Bool, i: Int } = /* censored */;
// 2 * 2^32 states

var x: Either<Bool, Int> = /* censored */;
// 2 + 2^32 states

Sum Type Encodings

typedef Either<A, B> = {
  function apply<C>(ifLeft: A -> C, ifRight: B -> C): C
}

function left<A, B>(a: A): Either<A, B> = {
  function apply<C>(ifLeft: A -> C, ifRight: B -> C): C {
    return ifLeft(a);
  }
}

function right<A, B>(a: A): Either<A, B> = {
  function apply<C>(ifLeft: A -> C, ifRight: B -> C): C {
    return ifRight(a);
  }
}

One more thing before we move on, if you're not fortunate enough to work in a language that has syntax for sum types, they're still not unavailable to you so long as you have either objects or closures.

Do all of you know how to do this encoding?

In Object-Oriented languages, this sort of encoding is commonly known as the Visitor pattern. In the so-called "Gang of Four" Design Patterns book, however, they talk about a crippled version of this approach, which has their "visit" and "accept" functions returning void, which means building up your result via mutation of some shared mutable state and is just about the most awful and non-composable bastardization of a beautiful idea that one could come up with.

JSON

enum JValue {
  JObject(xs: Array<JAssoc>);
  JArray(xs: Array<JValue>);
  JString(s: String);
  JNum(f: Float);
  JBool(b: Bool);
  JNull;
}

typedef JAssoc = {
  fieldName: String,
  value: JValue
}

Here's another example of the sort of thing that sum types permit you to do - rather than using some sort of awkward map- and object-based representation of a JSON value, we can encode JSON as a recursive sum type, which we can then safely traverse, ensuring that the structure that we are expecting is present at each step.

Sum types are really well suited to abstract syntax trees like this. We'll see them again and again throughout the reat of the talk, and we'll expand our ideas about what kinds of things can exist in an abstract syntax tree.

Semigroup

typedef Semigroup<A> = {
  append: A -> A -> A
};

s.append(s.append(a0, a1), a2) == s.append(a0, s.append(a1, a2))

function nelSemigroup<A>(): Semigroup<NonEmpty<A>> {
  function append0(e0: NonEmpty<A>, e1: NonEmpty<A>): NonEmpty<A> {
    return switch e0 {
      case Single(a): ConsNel(a, e1);
      case ConsNel(a, rest): ConsNel(a, append0(rest, e1));
    };
  }

  return { append: append0 };
}

In practical terms, here's a common example of how you'll see semigroups used. A useful semigroup value is the semigroup for non-empty lists.

We can see from the pattern matching we're using to deconstruct the first argument to our append function that our NonEmpty type is a sum type with two constructors, one the constructor for a non-empty list of a single element, and the other the constructor which takes a head value and a non-empty tail to with that head will be prepended.

This is a useful data structure for the purpose of things like accumulating parsing errors. We'll see an example of that later on, so remember this semigroup instance.

There are actually a huge number of types for which we can write Semigroup instances, for example, for integers, both addition and multiplication are associative binary operations. Concatenation of ordinary lists or arrays (which may be empty) is also a binary associative operation. It seems like it's possible to define a semigroup for just about any data structure for which you can concieve of an "additive" operation, because those operations can so frequently be made associative. Subtractive operations, by contrast, are frequently not associative though so be cautious. The integers, for example, do not form a semigroup under subtraction or division.

Now, I've given you the name "Semigroup", described what it does (which is just combine to values into a new value of the same type, and given you an example of a semigroup implementation. It's a pretty simple idea. So, rather than calling this by a potentially unfamiliar name that comes from abstract algebra, why don't we just call this an "AssocAppender" or something? We could! However, here's a chart that I grabbed off of Wikipedia:

We don't call this an AssocAppender because to do so would rob us of centuries worth of literature and learning about how we can use associative binary operations that put together two members of a set and return another member of that same set. Calling it a Semigroup helps us identify that this operation is part of a larger framework of binary operations on sets, some of which may be useful to us in similar situations. When we look here and see that 'Monoid' is a semigroup with an identity element.

Kleisli

Kleisli

function kComposeOption<A, B, C>(f: B -> Option<C>, g: A -> Option<B>): 
    A -> Option<C> {

  return function(a: A) {
    return switch g(a) {
      case Some(b): f(b);
      case None: None;
    };
  };
}

function kComposeList<A, B, C>(f: B -> List<C>, g: A -> List<B>): 
    A -> List<C> { ... }

function kComposePromise<A, B, C>(f: B -> Promise<C>, g: A -> Promise<B>): 
    A -> Promise<C> { ... }

Let's go back to functions now, and suppose that that we want to compose a slightly more exotic class of function, namely, effectful functions. Here's an example:

Here we have another really straightforward idea, given a scary but informative name, one that's easily Googlable and can lead you to the start of a nice random walk through some interesting math and programming Wikipedia pages.

The idea is the same one that we've been looking at in every case thus far, that we want to take two values that have the same shape - in this case, functions from a value to some effectful "container" containing a value of some other type - and combine them to create a new value, a new function, having the same shape.

In each case, the resulting function fuses together the effects produced by the functions being composed.

There's something else important here. The effects being fused are fused sequentially. I think that the third example, using Promises, is a good one for this reason. A Promise represents a potentially asynchronous computation that may produce a value of the parameter type at some point in the future. When we compose these functions, it's obvious that the Promise produced by 'g' must complete and yield a value before 'f' can be evaluated to produce the final result. This is true in every case - if the Option yielded by g contains a value, it must have been evaluated completely in order for f to be invoked. In the second example, each B value produced by the that 'g' is used to invoke 'f', and the results are concatenated sequentially.

Kleisli composition is all about putting effects in order by way of introducing a data dependency between those effects.

And, as with function composition, Kleisli composition is associative. This is important here for the same reasons that it was important when we were composing functions where the output type of the first matched the input type of the second. We want functions like this, where the output value is wrapped in some effect, to be able to be written and reasoned about independently, composed based upon their input and output types, and then be confident that their meaning doesn't change based upon the order in which we performed the compositions.

Applicative Functor

Applicative Functor

function liftA2Zip<A, B, C>(f: A -> B -> C): ZipList<A> -> ZipList<B> -> ZipList<C>;

function liftA2Par<A, B, C>(f: A -> B -> C): Par<A> -> Par<B> -> Par<C>;

function liftA2Val<E, A, B, C>(f: A -> B -> C, s: Semigroup<E>): 
    Validation<E, A> -> Validation<E, B> -> Validation<E C>

Let's talk now about a composition of effects that does not necessarily demand to be sequenced by way of data dependency.

The interesting thing to look at here is the result types of these liftA2 variants. You can think of Par as a type alias (really a newtype) for Promise that demands parallel execution, rather than the data-dependant, sequential evaluation that Kleisli composition gives us. ZipList is a similar newtype wrapper for ordinary lists. In both cases we're using a distinct type to distinguish how these types of values compose, so as not to confuse the parallel versions with their sequential variants.

Anyway, the result type of liftA2Par is a function that directly fuses two values representing asynchronous effects, but without any data dependency between the first effect and the second forcing an ordering of evaluation upon us. The two inputs can be evaluated, as you might expect, in parallel, and then the provided function applied to both results when they become available.

So, we're just composing things again! Applicatives are about nothing more than fusing together these effects, just in a slightly different way than Kleisli composition does it.

One more example, this is another really common use of applicative composition, one that I use every day. If you have a function that does some validation of input and potentially parsing of a wire form like JSON to a type, it's useful to be able to accumulate any failures and return them all at once. For this kind of purpose we clearly wouldn't want sequential composition with fail-on-first-error semantics, since then it might take a user multiple round-trips to discover all of their errors. Here we see another use of a semigroup - if we have a semigroup for the error type, then we can use that to collect up (dare I say compose?) all of our errors into a single value.

Free Applicative Functor

sealed trait FreeAp[F[_], A]
case class Pure[F[_], A](a: A) extends FreeAp[F, A]
case class Ap[F[_], A, I](f: F[I], k: FreeAp[F, I => A])

object FreeAp {
  def liftA2[F[_], A, B, C](f: A => B => C): 
      FreeAp[F, A] => FreeAp[F, B] => FreeAp[F, C] = ???
}

Sooner or later as you explore the world of functional programming, you're going to start running into the idea of "free" structures. Free monads are perhaps the most famous, but since we're on applicatives right now we'll cover them first.

In each of the applicatives we've looked at thus far, the specific applicative type has had some kind of intrinsic effect in addition to the fact that that effect could be composed in applicative fashion. The "free" construction is a way to separate out the applicative composition part from that additional effect.

What this means is that we're going to create a data structure that has no intrinsic effects of it own, except to wrap another parameterized type in a way that lets us implement liftA2 for that wrapped type. In languages that support higher-kinded types, we get this lifting or wrapping capability as a library; in Haxe, we have to do a little bit of extra work because we lack the abstractive capability, but we can get a similar result.

This brings me to an important point. Even in languages that lack some very important features, like higher-kinded types, it's often possible to achieve the same compositional properties, at the cost of a loss of abstraction - repeated code. Here I'm jumping into Scala for a moment to give you an idea of what this looks like in the general case - we're able to implement liftA2 without choosing ahead of time what F is. Moreover, it's the only operation we can implement, because we have no additional structure.

So what can we do with this thing, if the only operation we can perform is this particular type of composition? Here's an example.

enum Schema<A> {
  BoolSchema: Schema<Bool>;
  FloatSchema: Schema<Float>;
  IntSchema: Schema<Int>;
  StrSchema: Schema<String>;
  UnitSchema: Schema<Unit>;

  ObjectSchema<B>(propSchema: ObjAp<B, B>): Schema<B>;
  ArraySchema<B>(elemSchema: Schema<B>): Schema<Array<B>>;

  // schema for sum types
  OneOfSchema<B>(alternatives: Array<Alternative<B>>): Schema<B>;

  // This allows us to create schemas that parse to newtype wrappers
  IsoSchema<B, C>(base: Schema<B>, f: B -> C, g: C -> B): Schema<C>;

  Lazy<B>(s: Void -> Schema<B>): Schema<B>;
}

enum Alternative<A> {
  Prism<B>(id: String, base: Schema<B>, f: B -> A, g: A -> Option<B>);
}

enum PropSchema<O, A> {
  Required<B>(field: String, vschema: Schema<B>, accessor: O -> B): 
      PropSchema<O, B>;

  Optional<B>(field: String, vschema: Schema<B>, accessor: O -> Option<B>): 
      PropSchema<O, Option<B>>;
}

enum ObjAp<O, A> {
  Pure(a: A);
  Ap<I>(s: PropSchema<O, I>, k: ObjAp<O, I -> A>);
}

This is a set of data structures that describe a typed schema for JSON data. It suppports a set of combinators that allow you to build up values of the Schema type. They're mostly trivial, so I'm just going to show you an example of how they're used.

class Person {
  public var name: String;
  public var age: Option<Int>;
  public var children: Array<Person>;

  public function new(name: String, age: Int, children: Array<Person>) {
    this.name = name; this.age = age; this.children = children:
  }

  public static var schema: Schema<Person> = ObjectSchema(
    liftA3(
      Person.new,
      Required("name", StrSchema, function(x: Person) return x.name),
      Optional("age", IntSchema, function(x: Person) return x.age),
      Required("children",
               ArraySchema(Lazy(function() return Person.schema)),
               function(x: Person) return x.children)
    )
  );
}

So here we have a bit of code defining a person class, and a schema for this type. Fine. So what can we do with it? If the only effect that the "Free" part gives us over the underlying sum type is that it permits us to compose values as we see here, then the only sensible way to make use of such a composed value is to deconstruct it. What can we do with such a deconstruction?

What's it good for?

function parseJSON<A>(schema: Schema<A>, v: JValue): Either<ParseErrors, A>

function renderJSON<A>(schema: Schema<A>, a: A): JValue

function toJsonSchema<A>(schema: Schema<A>): JValue

function gen<A>(schema: Schema<A>): Gen<A>

Each of these functions is an interpreter - it deconstructs the schema a piece at a time, accumulating the information that was captured during its composition and using that to construct the output. We put the Schema value together just so that we could take it apart and allow its structure to guide the composition of some other data structure.

Lenses

class PLens<S, T, A, B> {
  public var get(default, null): S -> A;
  public var set(default, null): B -> (S -> T);

  public function new(get: S -> A, set: B -> (S -> T)) {
    this.get = get;
    this.set = set;
  }

  public function modify(f: A -> B): S -> T {
    return function(s: S) {
      return this.set(f(this.get(s)))(s);
    };
  }
}

One more, and we'll be done. This is a lens. Anybody want to guess what it's good for?

function view<S, T, A, B>(s: S, la: PLens<S, T, A, B>): A {
  return la.get(s);
}

function update<S, T, A, B>(s: S, la: PLens<S, T, A, B>, b: B): T {
  return la.set(b)(s);
}

function compose<S, T, A, B, C, D>(stab: PLens<S, T, A, B>, abcd: PLens<A, B, C, D>): 
    PLens<S, T, C, D> {

  return PLenses.pLens(
    function(s: S): C return abcd.get(stab.get(s)),
    function(d: D): S -> T return stab.modify(abcd.set(d))
  );
}

You can use a lens to pick a component out of a data structure, or to create a copy of a data structure with that component replaced by a new value.

And, of course... this is almost getting redundant at this point, right? You can compose lenses, so that the composed value can act on composed data structures.