Fantas, Eel, and Specification 2: Type Signatures

08 Mar 2017

Greetings, traveller. I hope you’ve been having a good one since I posted the first part of this series, and I’d have a read of that before going any further. Assuming you’re up-to-date, there’s one more little thing I thought we should talk about before we go head-first into the spec: Damas–Hindley–Milner type signatures.

Don’t panic.

Intro: Java -> Haskell

Chances are you’ve seen languages with explicitly-written (static) types before. Things like Java, maybe:

public static void main(String[] args) {}

This line tells us that a function, main, takes an array of String values, and returns void (nothing). That is the function’s type signature. Damas-Hindley-Milner signatures are just a different way of writing types. Y’know what, let’s save characters and just call them type signatures from now on.

When we go through these examples, bear one thing in mind: all functions are curried. I’ve written about currying in JavaScript before, so take a look if you’re unsure. tl;dr, whereas we’d write an add declaration in a Java-looking language like this:

public static int add(int a, int b);
//                     ^ arg  ^ arg
//             ^ return

We’d write its curried type signature like this:

add :: Int -> Int -> Int
--      ^  arg ^ arg
--                    ^ return

In English, this says that our add function takes an integer x, and returns a function that takes an integer y, which returns an integer (probably x + y).

Now, yes, some of you may be wondering about uncurried functions in JavaScript, such as an add function like (Int, Int) -> Int. However, we say that this would be a one argument function whose single argument is a pair (a tuple†). JavaScript is a bit loose with this idea, as we’ll see again and again.

Let’s look at zipWith, a slightly more complicated example. Here’s a possible implementation in JavaScript:

const zipWith = f => xs => ys => {
  const length = Math.min(
    xs.length, ys.length
  )

  const zs = Array(length)

  for (let i = 0; i < length; i++) {
    zs[i] = f(xs[i])(ys[i])
  }

  return zs
}

// Returns [ 5, 7 ]
zipWith(x => y => x + y)([1, 2])([4, 5, 6])

Our beautiful zipWith takes the values at each index of the two arrays (until the shortest one runs out), and applies them to f, returning an array of the results. If it isn’t clear how this function works, play around with some examples before continuing. Let’s think about types:

  • The f function must take two arguments of two types (we’ll call them a and b), and these must be the respective types of xs’ and ys’ array values.

  • The return type of zipWith is an array of the return type of f. So, if f returns some type c, then zipWith(f) must return an array of c.

How do we write that as a type signature? Just like this:

zipWith :: (a -> b -> c)
  -> [a] -> [b] -> [c]

We’ve used type variables to represent places where we can take different types (you might know this as polymorphism). You don’t have to call them a, b, and c - you could just as easily call them x, dog, and jeff (but don’t). The only rule here is that type variables always start with a lowercase letter, and concrete types always start with an uppercase letter.

Because we could fill the a variable with any type (as long as our f and xs agree!), we can write one zipWith signature that works for any type a. Neat, huh? In fact, zipWith is a great example of a tool that we see all over functional code because its variables make it so flexible:

// a = Int
// b = String
// c = Bool

// Returns [ true, false ]
zipWith(x => y => y.length > x)
  ([3, 5])(['Good', 'Bad'])

Here, our a is filled in with Int, b with String, and c with Bool. However, we could just as easily make them all Int and zip with x => y => x + y! I sure hope you can handle all this excitement. Here’s one last example of a function with a type variable:

// Filter an array by a predicate.
// filter :: (a -> Bool) -> [a] -> [a]
const filter = p => xs => xs.filter(p)

Our function will work for any a as long as our p function knows how to turn an a into a Bool. Yay!

Notice that both filter and zipWith have an argument that happens to be a function. To represent it in the signature, we “nest” its (bracket-wrapped) signature into our overall one.

Phew! That’s basically all there is to it. We break up each type with an ->, so the one at the end is the return value, and all the others are the arguments. In fact, this is all you need to read and write Elm type signatures - go write some Elm!

For this series, though, we’re going to have to complicate matters and introduce a couple more things…

Type Constraints

zipWith and filter are great, because their type variables can be any type. Sometimes, however, we don’t have that luxury. We might have to deal with signatures like these:

equals :: Setoid a => a -> a -> Bool

The => is new notation. What this means is that the signature to its right is valid if all the conditions to its left are satisfied. In the case of equals, the signature a -> a -> Bool is valid if a is a Setoid. Don’t worry about what a Setoid is just yet, as we’ll be covering exactly what it means in the next article. For now, just think of a Setoid as a type for which we can check whether two of its values are equivalent.

Constraints are very important. When we have a signature that involves a type variable with no constraints, we know that the function can’t manipulate it in any way. We know by looking at the signature id :: a -> a that all it could ever do is return the value it has been given, because we know nothing else about a - it could be a number, or a function, or anything! This feeds into an idea called parametricity that we’ll come back to several times in this series.

In languages like Haskell, the compiler will make sure that the conditions on the left are satisfied at compile-time, which catches a whole host of bugs! However, for our purposes, we’ll see that it’s simply some really handy documentation.

OOP-lease Stop

It wouldn’t be JavaScript without some bodging, would it? Because JavaScript is the way it is, we tend to build our types with methods like equals attached to the prototype:

// Rather than this:
equals(first)(second)

// We do this:
first.equals(second)

Fair enough - it’s certainly neater. However, it messes with our pretty signatures because equals now isn’t a function of two arguments: it’s a method of one argument attached to a value. Remember, though, that the argument must have the same type as the object to which equals is attached. In Fantasy Land, you’ll see the following style used to express this:

equals :: Setoid a => a ~> a -> Bool

The ~> is the new symbol here. What this means is that equals is a method on the thing to the left of ~>, and the thing to the right is its signature. Back in the previous article, we saw a List.prototype.toArray method. In the Fantasy Land style, we would write the signature for this method like so:

// toArray :: List a ~> [a]
List.prototype.toArray = function () {
  return this.cata({
    Cons: (x, acc) => [
      x, ... acc.toArray()
    ],

    Nil: () => []
  })
}

We’re saying that a List of values with type a has a method called toArray that returns an array of type a. It might not be pretty, dear reader, but it’s JavaScript. If you want a little exercise to do, write out a type signature for List.prototype.map, and make sure it’s as general as possible!

finish :: Blog ~> Ending

I promise you, that’s it. That’s everything you’ll need to know to live out a fulfilling life as a functional programmer. Once you get used to this syntax, it’s just like riding a bike with weird arrows and brackets everywhere. If this article felt a bit heavy, don’t worry: just come back to it for reference if you have questions later on in the series.

Regardless, get ready. No more distractions. Next stop: Fantasy Land.

Take care ♥

* An important point here is that equivalence is much deeper than pointer equality. Just try typing (x => x) === (x => x) into your Node REPL; for functions to be a valid setoid, this should return true.

† Pronounced “toople”, regardless of which side of the pond you inhabit. Weird, right?

Related Posts