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!"

[ericelliott]

Further, we can eliminate the clarifying names and only include necessary type information. The question is, does it make it more readable, or less?

mixin(a) => b: a & e

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

[ericelliott]

Ping @Mouvedia @tomekwi @koresar @Raynos

[koresar]

• mixin is a function from a to b where b is a member of both a and e

Does this mean that a and e are both types? I'm confusing what's a type, what's a variable name, and what's a property name. Could you please capitalize all the types in that last (shortest) example?

[ericelliott]

a and e are both type variables: variables that represent membership in different type classes.

In the last (shortest) example, a, b, and e are type variables in scope within the definition of mixin. mixin itself is a variable that represents membership in the type, (a) => b: a & e.

Within the composeMixins() definition, mixins, o, m, and e are all type variables inside the scope of the composeMixins definition. composeMixins is a type variable, too.

Similar to function scope in JS, type variables defined inside the definition of a signature are only in scope for that signature, so e from mixin may be different from e from composeMixins.

[Mouvedia]

I just wanna point out that mix: (...mixins) => o => (m: o & e) seems hard to read due to the chained =>; separators of some sort might come in handy. I am not a big fan of bi-directional inference: if you refactor the originator it will break in cascade. Apart from that, I don't think I'll be of a big help on this issue.

I wanted a signature notation that would be easy for JavaScript developers to read, even if they were not familiar with rtype signatures.

This is primordial.

[ericelliott]

@Mouvedia The "chained" arrow functions are just currying. Anybody familiar with arrow function currying in JavaScript, or Haskell type notation should recognize it immediately. Related: "Familiarity Bias is Holding You Back: It's Time to Embrace Arrow Functions"

[ericelliott]

Define:

• bi-directional inference
• Originator

[Mouvedia]

In this comment, you are inferring numerous types; by bi-directional I meant that you will have to scan in both direction to find the reason. The "originator" either has a type explicitly set or a predefined type and does not depend on another "type variable".

[ericelliott]

If a type variable has not been defined, a new type variable is created automatically in the scope of the signature. You're correct in saying that we can infer things about the type based on how it's used, but generally speaking, that's a concern for static analysis tools. Developers can just use the types and not worry about how the inference works.

[ericelliott]

Note to self: Update the syntax, clarify any lingering questions, create a PR.

I'm already using higher kinded types in lots of documentation.

[ericelliott]

Updated original proposal description. I've been using this syntax for quite a while now and testing it in mentorship sessions. Mentees seem to pick up what's going on quickly, and people familiar with Haskell should be able to use what they know about Haskell to learn the ropes.