Generic types

[maiermic]

How do I type a function with a type variable in rtype?

Example: map function

In functional languages you write something like this:

map :: Functor f => (a -> b) -> f a -> f b
map f a = ...

In TypeScript you use generics (ramda.map):

map<T, U>(fn: (x: T) => U, list: T[]): U[];
map<T, U>(fn: (x: T) => U, obj: any): any; // used in functors
map<T, U>(fn: (x: T) => U): (list: T[]) => U[];

[Mouvedia]

So you want the signature of Array.prototype.map?

[maiermic]

Yes, whereby the map function that I described takes the array as second parameter.

[ericelliott]

IMO, if you put too much inline, it becomes hard to read. I suggest splitting it:

Transform(a: Any) => b: Any
Map(fn: Transform, arr: []) => newArray: []

[maiermic]

Since Transform takes and returns Any I loose type information, right? Thus, this error is not recognized:

map( (text: String) => text.length, [1, 2, 3] )

[ericelliott]

Yep, but my map() signature example is intentionally generic to allow for any kind of transform. Bring your own Transform is implied. Do you have an alternative suggestion that works for every possible Transform without losing type information?

[maiermic]

intentionally generic means intentionally error-prone. It's like a leak in the type system. Everything that depends on the undefined type variable is untyped and can not be analyzed.

I already mentioned two examples of other type systems. TypeScript uses generics, but I'm not sure if it is the way we should go. I really like the way of functional type systems (simple, clear and expressive), but I'm not sure how compatible it is with the existing rtype system. I mentioned those examples, since TypeScript and Haskell are mentioned in About Rtype:

Standing on the shoulders of giants: ES6, TypeScript, Haskell, Flow, & React

[BerkeleyTrue]

@maiermic I think you missunderstood @ericelliott's comment.

MY map() signature example is intentionally generic to allow for any kind of transform. Bring YOUR OWN Transform is implied.

Meaning he supplied a generic function, You can supply a typed function.

Transform(a: String) => b: String
Map(fn: Transform, arr: [String]) => newArray: [String]

[ericelliott]

I think you missunderstood @ericelliott's comment.

:+1:

Bring your own Transform is implied.

[ericelliott]

@maiermic It's also worth noting that Haskell is polymorphic and generic programming is common in Haskell. https://wiki.haskell.org/Generics

[ericelliott]

More to your original point: currently, we don't support type variables like TypeScript's generics in function signatures, and the TypeScript syntax feels like an assault on my senses.

I'm open to the idea of adding this feature, if we can come up with syntax that doesn't make me want to claw out my eyes. I'll repeat my invitation for you to help:

Do you have an alternative suggestion that works for every possible Transform without losing type information?

[ericelliott]

It's also worth noting that just because a type isn't in a signature does not mean that the variable is untyped, and the Haskell docs actually show a map example to demonstrate:

map :: (a -> b) -> [a] -> [b]
Char.ord :: (Char -> Int)

For the expression map ord the type checker finds out that the type variable a must be bound to the type Char and b must be bound to Int and thus it concludes:

map ord :: [Char] -> [Int]

IMO, type inference should be favored as much as possible. Trying annotate every little thing can add a lot of noise.

[maiermic]

type inference :+1:

Meaning he supplied a generic function, You can supply a typed function.

Maybe I still mispreceive it. Let's try to clear up misunderstandings: Someone wrote a library with a intentionally generic function map, i.e. he types map like that:

Transform(a: Any) => b: Any
Map(fn: Transform, arr: [Any]) => newArray: [Any]

Now someone else likes to use this function like that:

var a = map( (text: String) => text.length, ['example', 'input'] );
var b = map( (x: Number) => x > 6, a );
var c = map( (text: String) => text.split('p'), b );

In case a map is used with types

Transform(a: String) => b: Number
Map(fn: Transform, arr: [String]) => newArray: [Number]

In case b map is used with types

Transform(a: Number) => b: Boolean
Map(fn: Transform, arr: [Number]) => newArray: [Boolean]

In case c map is used with types

Transform(a: String) => b: String
Map(fn: Transform, arr: [Boolean]) => newArray: [Number]

Since Any is compatible with any type (including Boolean, Number and String) those type definitions are all compatible with the original type

Transform(a: Any) => b: Any
Map(fn: Transform, arr: [Any]) => newArray: [Any]

Thus, the type conflict in case c is not recognized. Who should supply a typed function? Author or user? Where and how should it be supplied? It would be an imposition and error-prone for the user to add a concrete type signature before each usage of map. Therefore, we need type variables the author can use.

Do you have an alternative suggestion that works for every possible Transform without losing type information?

TypeScript uses generics to define type variables

map<T, U>(fn: (x: T) => U, list: T[]): U[];

You can pass type variables to other gerneric type definitions:

Transform<T, U>(x: T) => U
map<T, U>(fn: Transform<T, U>, list: T[]): U[];

You don't need to specify generic types on each call just in the definition.

Generics are widespread and established, but they are considered to be quite complex.

TypeScript syntax feels like an assault on my senses

What do you not like? Maybe we can find a better solution, if you describe your feelings in more detail.

By the way, we already use generics under the hood to describe arrays, don't we? String[] is the same as Array<String>.

[ericelliott]

By the way, we already use generics under the hood to describe arrays, don't we? String[] is the same as Array<String>.

Yes, and I even considered TypeScript's generic syntax for that purpose, but I think there's something about the angle brackets that drives me crazy. Reminds me of C++ templates or something (which I have bad memories of).

Are there any other generic syntaxes we could use as inspiration?

[BerkeleyTrue]

:-1: For angle brackets

[maiermic]

Scala uses square brackets:

def map[T,U](fn: T => U, list: List[T]): List[U] = ...

We could write Array[T] instead of T[] in rtype. We might use [T] as short version of Array[T]. One benefit of writing the generic type in brackets is better readablity of type expressions: (Number | String)[] vs. [Number | String] or Array[Number | String]

[Mouvedia]

:-1: for the long version We shouldn't use the constructor for that: it's too confusing.

[maiermic]

We shouldn't use the constructor for that: it's too confusing.

Array is not the constructor. It is the type interface Array. The constructor Array is a function with type

function Array[T](...elements: Array[T]): Array[T] { ... }

But I would say that is even more confusing :wink:

We could use another name ArrayInstance or IArray for the type interface of an array to avoid misunderstandings (see example of the documentation):

function Array[T](...elements: ArrayInstance[T]): ArrayInstance[T] { ... }

or

function Array[T](...elements: IArray[T]): IArray[T] { ... }

Whereby the short syntax is more readable, but less explicit (special case)

function Array[T](...elements: [T]): [T] { ... }

We characterize the naming conventions. That's why should think carefully about naming predefined types. ArrayInterface may be considered, too.

Some more examples of generic types (not considering one of these naming conventions):

Stream[T]
Map[K, V]
Object[K, V] // Object that is used like a map (might be controversal, but is common in JS world)
Pair[A, B]

[ericelliott]

I like the square bracket syntax MUCH BETTER. I'm OK with this:

Stream[T]
Map[K, V]
Object[K, V] // Object that is used like a map (might be controversal, but is common in JS world)
Pair[A, B]

[Mouvedia]

I don't think we should reuse square brackets since in JS it's for arrays. We need a new syntax that doesn't use (), {} or [] but still conveys inclusion. I don't like <> either but it has the advantage of not being confusing.

Promise::String:: Would that work?

[tomek-he-him]

Wouldn’t square brackets mentally collide with our syntax for typed arrays? Object[] vs Object[String, Number] vs Object[String, Number][].

Elm just uses spaces for that. Similarly to Haskell, it has lowercase for generics and uppercase for concrete types:

Stream t
Map k v
Object k v
Pair a b

Transform t u: (x: t) => u
Map t u: (fn: Transform t u, list: t[]) => u[]

[ericelliott]

This is my favorite suggestion so far. :+1: @tomekwi

Advantages:

• No ambiguity with arrays
• No jarring angle brackets
• Clean, readable syntax
• Follows existing conventions (Elm, Haskell)

[tomek-he-him]

Woohoo :tada:! Let’s wait what the others say.

[stoeffel]

@tomekwi love your suggestion. I'm a fan of the Hindley-Milner type system. (https://en.m.wikipedia.org/wiki/Hindley%E2%80%93Milner_type_system)

[tomek-he-him]

Whooah, looks hardcore! :wink:

[Mouvedia]

So simple yet so clear.

:+1: on space

[koresar]

The following looks very bright and logical. Although, rather unreadable. Let me explain.

Stream t
Map k v
Object k v
Pair a b
Transform t u: (x: t) => u
Map t u: (fn: Transform t u, list: t[]) => u[]

Thousands of C++/Java/C# developers are currently being converted to JS developers, you all know that. Students in (high)schools study the C++/Java/C#. I would recommend to make sure these people can read rtype easily without browsing the documentation (JSDoc is quite readable, btw, thus popular).

Haskell is known but an exotic language yet. For C++/Java/C# developers it is counter intuitive that the space symbol have a special syntactic meaning. Frankly speaking, I still do not understand what's that: Transform t u: (x: t) => u.

I would recommend to level the readability up to the highest level possible, gentlemen.

Haskell is still not readable unfortunately. TypeScript syntax is readable to most developers. They would easily understand that:

Transform(a: T) => U
Map<T, U>(fn: Transform<T, U>, list: T[]) => U[]

But not many would understand this (hopefully I understood it correctly):

Transform t u: (x: t) => u
Map t u: (fn: Transform t u, list: t[]) => u[]

C++/Java/C#/TypeScript languages have so called "generics". I'd recommend utilizing it's syntax - i.e. chevrons < and >.

[koresar]

Let me list "arguments" against the angle brackets you have expressed:

... something about the angle brackets that drives me crazy. Reminds me of C++ templates or something (which I have bad memories of).

---

:-1: For angle brackets

---

I don't like <> either

---

No jarring angle brackets

Do you feel like those are far from being an argument? :)

[Mouvedia]

Converted by force? I think we should concentrate on our community needs. The newcomers already added class to ES, that's plenty enough in my opinion.

[koresar]

Those "converted" people are also our community.

[ericelliott]

Do you feel like those are far from being an argument?

I used C++ and Java for years, and I never got accustomed to angle brackets in signatures. I can't express in a way that sounds like a just argument except that to my brain, they are extremely noisy to the point that it makes it really difficult for me to read.

For some reason, angle brackets don't bother me for HTML/JSX, but when they're mixed in with the rest of the syntax noise of a function signature, they scramble my brains.

On the flipside, I find the lack of syntax noise here produces crystal clarity without any loss of meaning:

Transform t u: (x: t) => u
Map t u: (fn: Transform t u, list: t[]) => u[]

I'm completely baffled that you find this harder to read.

I'm tempted to HARD VETO the angle brackets, but I don't want to shut down the discussion. =)

I'll just leave you with a reminder of my original stance on TypeScript's syntax:

"TypeScript syntax feels like an assault on my senses."

That hasn't changed, and no amount of logical argument is going to change it if 15 years' exposure to similar syntax hasn't made it any more bearable.

[ericelliott]

Those "converted" people are also our community.

IMO, they deserve a break from the angle bracket torture. ;)

"Generics in C++ and Java Melt My Brain" https://www.youtube.com/watch?v=_kXiH1Yiemw?t=25:17

[BerkeleyTrue]

TypeScript syntax feels like an assault on my senses.

Agreed. I enjoy reading well written JavaScript. TypeScript is horrendous mutation.

[koresar]

If rtype doesn't need wide adoption then use spaces. :)

Transform t u: (x: t) => u remove u Transform t: (x: t) => u remove t Transform: (x: t) => u why there is double colon?

Which is correct Transform: (x: t) => u, Transform (x: t) => u, or Transform(x: t) => u and why?

Why some types in rtype are upper case, but the u and t above are lower case?

Now, let me embed Transform into the map function:

Map t u: (fn: Transform t u: (x: t) => u, list: t[]) => u[]

^ First of all those double colons frustrate me. Second, what if I don't need the Transform function at all and want to make it all single line? Is the following correct?

Map t u: (fn: t u: (x: t) => u, list: t[]) => u[]

[ericelliott]

"TypeScript is horrendous mutation."

I wouldn't go that far. TypeScript has tons of cool ideas & it's been a major source of inspiration for this project. It's just this particular angle bracket syntax that bothers me. =)

[koresar]

I want to make function F to accept and return the same type Map. First generic argument of the Map would be string, and second would be a function which takes and returns strings.

F(map: Map String (str: String) => String) => Map String (str: String) => String

^ see the => arrow chaining. So you still think that's readable?

UPD: Now, I want to drop the word Map as I don't need it for some reason. Is the following correct? Is it readable?

F(map: String (str: String) => String) => String (str: String) => String

Borrowing most of the syntax from JS and Flow you borrowed an incompatible Haskel/Elm syntax.

[ericelliott]

Good questions, @koresar. Let's clean this up and align it more with our existing syntax:

Map t u: (fn: Transform t u, list: t[]) => u[]

IMO, this should be:

Map t u (fn: Transform t => u, list: t[]) => u[]

Which translates to:

Signature Map uses type variables t, and u which do not exist outside the scope of this signature. The first argument is a Transform function from type t to type u, and a list of type t. Map's second argument is an Array of type t, and it returns an array of Type u.

As with JavaScript, I think if the function needed more than one parameter, it should use parens around the arguments, so this should also be a valid representation of Transform: Transform (t) => u.

Transform (x: t) => u, or Transform(x: t) => u

Both of these seem fine to me. IMO, the space should be allowed specifically because I find this clear:

Map t u (fn: Transform t => u, list: t[]) => u[]

... and this a little less clear:

Map t u(fn: Transform t => u, list: t[]) => u[]

(Note the absence of the space after u, which makes it look to me like u is the function name).

Why some types in rtype are upper case, but the u and t above are lower case?

Visual disambiguation between concrete types and type variables.

Now, let me embed Transform into the map function:

Map t u: (fn: Transform t u: (x: t) => u, list: t[]) => u[]

The t u after Transform shouldn't be necessary, because the type variables are in scope from the Map declaration:

Map t u (fn: Transform t => u, list: t[]) => u[]

First of all those double colons frustrate me

Me too. Consider them gone.

what if I don't need the Transform function at all and want to make it all single line? Is the following correct?

`Map t u: (fn: t u: (x: t) => u, list: t[]) => u[]`

Type names are optional if you're not reusing them, so this is probably the shortest valid expression of Map:

Map t u (t => u, t[]) => u[]

[Mouvedia]

Both of these seem fine to me. IMO, the space should be allowed specifically because I find this clear:

Map t u (fn: Transform t => u, list: t[]) => u[]

IMO it should be mandatory in that case.

[ericelliott]

I want to make function F to accept and return the same type Map. First generic argument of it would be string, and second would be a function which take and returns strings.

This example doesn't make sense and probably shouldn't be considered valid because String is not a type variable, and your desired signature doesn't need type variables. If I understand you correctly, it should be written like this:

F(Map(str: String) => String) => Map(str: String) => String

But this violates DRY, and should instead by written like this:

Map(str: String) => String
F(Map) => Map

Which looks perfectly clear to me. Is it possible to write confusing signatures with the syntax we have now? Sure. But it's also possible to take that same signature and write it in a way that looks clean and sane.

[ericelliott]

@Mouvedia

IMO it should be mandatory in that case.

Referring to the space after the u declaration:

Map t u (fn: Transform t => u, list: t[]) => u[]
       ^

:+1: I agree, that seems like a reasonable style rule.

[koresar]

Thanks Eric for that:

F(Map(str: String) => String) => Map(str: String) => String

Map(str: String) => String
F(Map) => Map

But there is a mistake. Please read:

First generic argument of Map would be string, and second would be a function which take and returns strings.

Map is a key->value map. Where key is string and value is predicate. Let me attempt to tackle it.

Map String (str: String) => String
F(Map) => Map

Unwrapping:

F(Map String (str: String) => String) => Map String (str: String) => String

Removing the word Map as not needed:

F(String (str: String) => String) => String (str: String) => String

Removing the variable name str.

F(String (String) => String) => String (String) => String

Dropping unnecessary parenthesis:

F(String String => String) => String String => String

Replace String with t to make it more generic as suggested above:

F(t t => t) => t t => t

Is it still valid? Have I made a mistake at any step?

[ericelliott]

Consider this:

Map t u (t => u, t[]) => u[]

What if we wanted to map over streams instead of Arrays?

Assuming, Map t u (t => u, t[]) => u[] is short for:

Map t u (t => u, Array t) => Array u

And then these become valid:

Map t u (t => u, Stream t) => Stream u

Map t u (t => u, Promise t) => Promise u

Or did I miss a better implied representation for this idea?

[koresar]

Thanks Eric. Although I'm trying to understand how rtype works. I'm considering it for company-wide usage. Although, this question bothers me very much. Was I correct in my logic chain above?

[ericelliott]

First generic argument of Map would be string, and second would be a function which take and returns strings.

This is still confusing me.

"First generic argument of Map would be string" -- if we know it's a String, it's not generic, right? It's not a type variable, it's a known parameter type, String.

and second would be a function which take and returns strings.

And a function which takes and retuns Strings is also not generic, it has the concrete signature: fn: String => String.

Map is a key->value map. Where key is string and value is predicate. Map String (str: String) => String

Still confused. Where is key? Where is value? Where is the Predicate type (which is built into rtype)?

It sounds like you're describing a data structure rather than a function. If I were translating your English prose to an rtype signature, it would look like this:

interface PredicateMap {
  key: String,
  Predicate
}

Assuming you really do mean a function, it would look something like this:

PredicateMap(key: String) => Predicate // Predicate is a function that returns a `Boolean`

I have no idea what you mean by this. AFAIK, it's not valid rtype:

F(String (String) => String) => whatever

The way I read it, it translates into this nonsense:

F is a function that takes a String as the first parameter. At which point it blows up: "Error: Expected comma and instead got a function signature."

[koresar]

I beg you pardon for my broken English.

Map is a key->value map. Where key is string and value is function which takes string and returns string. In JS it would be this:

var map = {};
map.a = function (str) { return str; };

"a" string is a key. The function is the predicate.

Yes, it is a data structure.

Let's forget about strings and use type t instead. Ok?

Predicate:

Predicate t (t) => t

Data structure (map):

interface PredicateMap t {
  key: t,
  Predicate t
}

The F function:

F(PredicateMap t) => PredicateMap t

Is that correct to your thinking?

[tomek-he-him]

I’m a bit confused as well. After the discussion with Eric at https://github.com/ericelliott/rtype/commit/7730287320d00c539052aa922921a5714aa47cbf#commitcomment-15619201 I wanted to apologize and correct my mistake. Instead of

Transform t u: (x: t) => u
Map t u: (fn: Transform t u, list: t[]) => u[]

…I meant rather

interface Transform t u: (x: t) => u
interface Map t u: (fn: Transform t u, list: t[]) => u[]

That could be expressed without the intermediary type:

interface Map t u: (fn: t => u, list: t[]) => u[]

…or as a type annotation and not an interface:

//  map(fn: t => u, list: t[]) => u[]
const map = (fn, list) => …

Is that right? Notice the colons in interfaces and the lack of colons and generics in the annotation.

[tomek-he-him]

And by the way, we could use the generic interfaces to “fill” them with concrete types later on:

//  Transform String Boolean
const isLong = str => (str.length > 5);

@koresar, that would be the difference between uppercase (concrete types) and lowercase (generics). I think it makes for a nice separation. But it’s the syntax of Haskell and Elm – we don’t have to adopt it.

[koresar]

@tomekwi can you help me with my trouble above? I can't figure out syntax for my simple case.

[tomek-he-him]

@koresar, I’ll try – though the ins and outs of the syntax aren’t very clear to me.

I assume that by using Map before defining it beforehand you mean JS’s native Map. But as it’s not a builtin yet, we need to define it beforehand:

interface Map k v {
  key: k,
  value: v,
}

Then what you called Map in F(Map) => Map is no longer the almost-built-in type Map, but it’s a concrete type (without generics) based on Map:

interface StringMap:
   Map String (String) => String

interface F:
  (StringMap) => StringMap

The shortest way to express that would be:

interface F:
  (Map String (String) => String) => Map String (String) => String

– and I do agree that it’s unreadable and ambiguous. I suggest that we force parens around literals when using them as “arguments” for generic types:

interface StringMap:
   Map String (String => String)

interface F:
  StringMap => StringMap

…and the WET, eye-squelching version:

interface F:
  (Map String (String => String)) => Map String (String => String)

As for your comment about making things more generic, I think it only makes sense when your function/interface really is generic. But if your code really is so abstract then the type annotations are bound to be abstract too:

interface TypeMapTransformer a:
  (Map a (a => a)) => Map a (a => a)

If you ask me, the last example doesn’t look bad or unreadable. It’s complex becuse what you’re trying to express is complex. Try documenting that with jsDoc!

[tomek-he-him]

Here’s the DRY version:

interface TypeMap a:
   Map a (a => a)

interface TypeMapTransformer a:
  TypeMap a => TypeMap a

[tomek-he-him]

By the way, if this goes through, I’d take the opportunity to revise builtins. I’m not sure if we need Any if we have generics. Array and Object could be more specific: Array a and Object k v. As well as that, the type system will be expressive enough to pull in the new players: Iterator a, Set a, Map k v, etc.