Haskell-style Typeclasses

[ericelliott]

When I first started rtype, I was tempted to just steal Haskell's Hindley-Milner type annotations and just start using them, but I saw several problems with that:

1. Haskell types are all curry all the time. I wanted to be able to express: add2(a: Number, b: Number) => Number.
2. How do you deal with this?
3. I wanted to be able to name parameters for clearer documentation. Haskell's types are very expressive and clean-looking, but it's sometimes hard to figure out what the type variables represent in real code.

So, we abandoned Hindley-Milner altogether, and forgot all about typeclasses. Ever since, we've been struggling with the question: How do we represent type polymorphism, and especially, higher order functions like map. Take Haskell's Functor type:

fmap :: Functor f => (a -> b) -> f a -> f b

In this example, a and b are both type variables, and f a and f b mean "functor of a" and "functor of b", respectively.

The Functor f => is called a type constraint. It basically says, "in this definition, f represents the Functor typeclass". Like generic type constructors in other languages, a typeclass takes a type parameter, so f a represents a type that is a member of the Functor typeclass, and f b represents a possibly different type that also a member of the Functor typeclass.

We currently have no way to express this in rtype, and because I do a lot of functional programming, I have been falling back on Haskell's Hindley-Milner types in a lot of my writing.

I'm frustrated with that because as I mentioned already, switching from rtype to Hindley-Milner or vice verse, we lose a lot of valuable information. Haskell's Hindley-Milner notation doesn't express enough about the names and purposes of variables, lacks ...rest, etc..., and also doesn't naturally allow for uncurried multi-arg functions.

If we try to express a lot of higher-order functions in rtype, it falls flat. To complicate matters, I'm building lots of types that implement a bunch of stuff with methods, meaning I need a way to say that map is a method on a Functor type, and takes this as an argument.

We need the best of both worlds.

Proposal

What if we could do this in rtype?

fmap = (a => b) => Functor(a) => Functor(b)

And for Mappables using this:

interface Mappable {
  map: Functor(a) ~> (a => b) => Functor(b)
}

Where Functor(a) is the type of this in the map method. The ~> for this syntax is lifted from the Fantasyland specification.

Instead of specifying a type constraint with a variable name, we'll explicitly say Functor(a) or Functor(b) instead of f a or f b.

updateWhere = Predicate => (a => b) => Functor(a) => Functor(b)

updateWhere() is a curried function that takes a predicate, an updater function from a to b, (where a and b represent any type, and may refer to the same type), and a Functor of a, and returns a new Functor of b, with the matching elements replaced with updated versions.

[davidchambers]

Perhaps Sanctuary can provide some guidance. Here's the definition of S.map:

S.map = def('map', {f: [Z.Functor]}, [Fn(a, b), f(a), f(b)], Z.map);

String representation:

S.map.toString();
// => 'map :: Functor f => (a -> b) -> f a -> f b'

Possible type errors:

S.map(x => x, 'XXX');
// ! TypeError: Type-class constraint violation
//
//   map :: Functor f => (a -> b) -> f a -> f b
//          ^^^^^^^^^                ^^^
//                                    1
//
//   1)  "XXX" :: String
//
//   ‘map’ requires ‘f’ to satisfy the Functor type-class constraint; the value at position 1 does not.

S.map(n => n < 0 ? null : Math.sqrt(n), [9, 4, 1, 0, -1]);
// ! TypeError: Type-variable constraint violation
//
//   map :: Functor f => (a -> b) -> f a -> f b
//                             ^
//                             1
//
//   1)  3 :: Number, FiniteNumber, NonZeroFiniteNumber, Integer, ValidNumber
//       2 :: Number, FiniteNumber, NonZeroFiniteNumber, Integer, ValidNumber
//       1 :: Number, FiniteNumber, NonZeroFiniteNumber, Integer, ValidNumber
//       0 :: Number, FiniteNumber, Integer, ValidNumber
//       null :: Null
//
//   Since there is no type of which all the above values are members, the type-variable constraint has been violated.

Sanctuary's checking happens at run time, though, so the ideas may not translate to this project.

[ericelliott]

Thanks for your input, @davidchambers -- very interesting.

I started working on rtype because I felt a need for a standard way to describe JavaScript function signatures and object interfaces that projects like TypeScript, Flow, and Haskell's signatures don't solve.

Haskell's signatures seem to come the closest to what I was looking for, but I also wanted to include parameter names in the signature, describe default values, etc... My thinking about how to express those concepts was heavily influenced by JavaScript itself. I wanted a signature notation that would be easy for JavaScript developers to read, even if they were not familiar with rtype signatures.

I use rtype signatures in documentation, blog posts, and books, the same way you'd use a Haskell signature to describe a function's type before expanding on it in a prose description.

We do want to build runtime type checking and static analysis tools that can benefit from Rtype, but those efforts haven't had much attention, yet.

[ericelliott]

Clarifying the Meaning of :

In Rtype, we already have the : symbol in our type annotations. At the root level, they mean "the thing on the left belongs to the type on the right".

Since Rtype is already a structural type system, that means that the left side symbol might belong to many types: 1:Many.

What if we take this thinking a bit farther? Currently, we expect the thing on the left to always represent the name of a parameter. What if the thing on the left is just a type variable, just like the thing on the right?

Then we could say things like this:

mixin(a: Object) => b: a & (e: Object)

composeMixins(...mixins: [...mixin]) => (
  instance = {}: (o: Object),
  mix: (...mixins) => o => (m: o & (e: Object))
) => m

In this example:

• mixin is a function from a to b where b is a member of both a and e
• a is a member of Object
• e is a member of Object, which may not be a member of a
• b is a member of both a & e, meaning it is also a member of Object
• mixins is a type representing an array of zero or more mixin functions
• instance is a type variable which is a member of o,
• o is a type variable which is a member of Object
• mix is a function from that takes any number of functions and returns a function from o to m
• m is a type that is a member of both o and e
• e is a type that is a member of Object
• o and e are probably different. While both are members of Object, o may not be a member of e and vice versa.

In other words, in all cases, the type variable on the left-hand side of the : is a member of the type specified to the right of the :.

We can make a few inferences, to reduce the amount of syntax noise in the example above:

A. Because b contains properties from a and e, we can infer that a, b, and e are all members of Object (everything with properties is a member of type Object):

mixin(a) => b: a & e

A. Since instance defaults to {}, we can infer that o is a member of Object:

  instance = {}: o,

B. Since e extends the properties of o, we can also infer that it is a member of Object:

  mix: o => (m: o & e)

So, we can represent the composeMixins signature like this:

mixin(a) => b: a & e

composeMixins(...mixins: [...mixin]) => (
  instance = {}: o,
  mix: (...mixins) => o => (m: o & e)
) => m

Here's the implementation:

const composeMixins = (...mixins) => (
  instance = {},
  mix = (...fns) => x => fns.reduce((acc, fn) => fn(acc), x)
) => mix(...mixins)(instance);

And here's how it's used:

/*
withFlying(instance: o) => m: o & {
  fly() => m, effects(change flight status to 'Flying'),
  land() => m, effects(change flight status to 'Not flying'),
  getFlightStatus() => 'Flying' | 'Not flying'
}
*/
const withFlying = instance => {
  let isFlying = false;

  return Object.assign(instance, {
    fly () {
      isFlying = true;
      return instance;
    },
    land () {
      isFlying = false;
      return instance;
    },

    getFlightStatus: () => isFlying ? 'Flying' : 'Not flying'
  });
};

const withQuacking = text => instance => Object.assign(instance, {
  quack: () => console.log(text)
});

// Compose mixins:
const createDuck = composeMixins(withFlying, withQuacking('Quack!'));
const malard = createDuck();
console.log(malard.fly().getFlightStatus()); // Flying
malard.quack(); // "Quack!"