Should the spec not define a mechanism to associate instances and types?

[ivenmarquardt]

Static land replaces prototypes with explicit type dictionaries. While the spec defines how this dictionaries have to be constructed and which rules their static methods have to follow, it says nothing about the mechanism, how a specific instance should be associated with its corresponding type.

Javascript's prototype system guarantees that each instance of a type is always implicitly associated with the right prototype. There is no such guarantee with explicit type dictionaries. So in a way the spec offers an approach that is even less type safe than the prototype system.

Should the spec not at least point out that a static land compliant implementation must provide a mechanism, which guarantees that an instance can only be used with its corresponding type dict.

Here is an example of such an mechanism (the implementation is not static land compliant). Please note that upper case identifiers represent values wrapped in a functor:

const cons = sym => x => 
 Object.defineProperty([].concat(x), "tag", {value: sym});

const List = {
  tag: Symbol.for("ftor/list"),
  cata: o => X => o[X.tag](X),
  fold: f => X => List.cata({[List.tag]: f}) (X),
  map: f => X => List.fold(
    xs => cons(List.tag) (xs.map(f))
  ) (X)
};

const Maybe = {
  some: Symbol.for("ftor/some"),
  none: Symbol.for("ftor/none"),
  cata: o => X => o[X.tag](X[0]),
  fold: f => g => X => Maybe.cata(
    {[Maybe.some]: f, [Maybe.none]: g}
  ) (X),
  map: f => X => Maybe.fold(
    x => cons(Maybe.some) (f(x))
  ) (K(X)) (X)
};

const K = x => y => x;
const sqr = x => x * x;

const x = cons(List.tag) ([1,2,3]);
const y = cons(Maybe.some) (1);

List.map(sqr) (x); // [1,4,9]
List.map(sqr) (y); // TypeError

[rpominov]

I think there're two separate issues here:

1. Type Dictionary methods should type check their inputs

List.map(f, [1, 2, 3]) // should work
List.map(f, Maybe.of(1)) // should throw

Not sure if spec should dictate anything here. It's up to implementers to do that checks or not. Even more, they might decide to do something special in cases when incorrect values are passed. For example List.map(f, undefined) may return a function Array<a> => Array<b> (i.e. method may support Ramda-style currying).

2. It would be cool to be able to get access to Type Dictionary if we have a value of a type.

This can be solved by requiring a special property on values, say @@static-land that points to a corresponding Type Dictionary. So for example we could write code like this:

function incrementInner(v) {
  return v[`@@static-land`].map(x => x + 1, v)
}

And this exactly what is proposed in https://github.com/fantasyland/fantasy-land/issues/199 . I recommend you to take a look at that discussion, and comment there if you have any questions ideas etc.

[rpominov]

Not sure how parametricity related to this issue, but to answer the question: spec basically requires that methods must be parametrically polymorphic (e.g. in T.of(x) it's not allowed to analyze x and take different code branches depending on it).

What is the purpose of the spec then?

Main purpose is to define algebraic laws.

[gcanti]

a static land compliant implementation must provide a mechanism, which guarantees that an instance can only be used with its corresponding type dict

This is a strong statement, I'm not sure is possible and practical (without a static type checker).

[ivenmarquardt]

For what it's worth (and since you haven't closed this issue yet), here is my suggestion:

Many of the types we're dealing with are sums. Hence constructors for values of such a sum type need to enrich them with some meta information. Since prototypes are avoided, values should reference their corresponding type dict. For each choice of a sum type a distinct value constructor must be defined, which tags its constructed value, so that pattern matching (or rather duck typing) can be applied:

// tagged union type

const Option = {};

Option.cata = pattern => ({tag, x}) => pattern[tag](x);

Option.fold = f => g => fx => Option.cata({some: f, none: g}) (fx);

Option.concat = type => ({tag: tagy, x: y}) => ({tag: tagx, x: x}) => tagx === "none"
 ? tagy === "none"
  ? None()
  : Some(y)
 : tagy === "none"
  ? Some(x)
  : Some(type.concat(y) (x));

// (value) constructors

const Some = x => ({type: Option, tag: "some", x: x});
const None = () => ({type: Option, tag: "none"});

// auxiliary functions

const cata = type => type.cata;
const concat = type => type.concat;
const fold = type => type.fold;

// mock data/functions

const All = {
  concat: y => x => x && y
}

const Any = {
  concat: y => x => x || y
}

const sqr = x => x * x;
const K = x => _ => x;
const I = x => x;

const v = Some(true)
const w = Some(false)
const x = Some(5);
const y = Some(2);
const z = None();

// application

// pattern matching à la cata:

cata(Option) ({some: sqr, none: K(0)}) (x); // 25
cata(Option) ({some: sqr, none: K(0)}) (z); // 0

// foldable/semigroup

fold(Option) (I) (K(0)) (x); // 5
fold(Option) (I) (K(0)) (z); // 0

concat(Option) (All) (v) (w); // {...false}
concat(Option) (Any) (v) (w); // {...true}
concat(Option) (All) (z) (z); // {}

// there is always an implicit reference to the type dict

invokeVia = ({type}) => prop => type[prop];
invokeVia(x) ("fold") (sqr) (K(0)) (x); // 25

Does this belong to the spec? I guess yes, at least more than a whole section about parametricity.

[polytypic]

[Static land spec] says nothing about the mechanism, how a specific instance should be associated with its corresponding type.

The way I see it, the Static Land spec and descriptions of the spec actual do say something about it.

Here is an excerpt from the README:

• We can implement many types for same values. For example we can implement two Monoids for numbers: Addition and Multiplication.

I interpret this to mean that there can be multiple "algebraic types" per "instance". This means that the premise of associating an instance with the algebraic type is something that is not compatible with the Static Land spec.

Here is an excerpt from the spec:

An algebra is a set of values (type instances, and other values) [...]

I interpret this to mean that the spec is not just about "type instances", but also about other primitive values.

Javascript's prototype system guarantees that each instance of a type is always implicitly associated with the right prototype.

However, primitive values like null and undefined do not have an associated prototype. The Static Land spec seems to be specifically written to allow one to define Algebraic Types also over such values.

Should the spec not at least point out that a static land compliant implementation must provide a mechanism, which guarantees that an instance can only be used with its corresponding type dict.

IMHO, the short answer should be no. Longer answer could be to encourage the use of static typing or having type dictionary methods to check their inputs.

[ivenmarquardt]

Hm, maybe my understanding of types is wrong. For me, Monoid is not a type per se, but a type class that defines some behavior for several types. A type can implement such a type class as a constraint.

In my sketch above All and Any are distinct instances of the Semigroup type class for the Boolean primitve type.

On the other hand Option is a type, a sum type or tagged union, which implements the Foldable and the Semigroup type classes. A value produced with the Some/None constructor should of course stick with its type through the whole program, unless there is an implicit coercion or an explicit type cast.

Additionally, since static land removes prototypes from the menu, there must be some sort of alternative association of values with their corresponding types, or you won't be able to write programs which go beyond a few lines.

Since static land seems to merely define a couple of type classes, it may be legitimate to restrict the specification to their definition. All I'm saying is, that instead of explaining parametricity, which shouldn't be part of this spec (because it is not specific to static land), the spec should offer at least an advice, how to implement an alternative association mechanism.

[polytypic]

For me, Monoid is not a type per se [...]

Yes, the terminology is not standard. Personally I would say that Monoid is an algebraic structure. I would also say that a Monoid is not a type class, but you can approximate the concept of a Monoid using type classes (and many other programming language constructs to varying degrees—some better than type classes).

[rpominov]

Agree with everything @polytypic said 😄

I was working with unicode and emoji lately and thinking about building a SL compatible library of utils for unicode and emoji. It would define several SL dictionaries, that all use strings as their "instances", but interpreted them differently.

One could interpret a string as a collection of code points: CodePoints.map(codePointNum => ..., string).

Another one could interpret it as collection of combined characters.

Another one as a collection of emoji. Its map would act only on emoji, ignoring all other characters.

All that dictionaries will implement at least map and chain, and will work with strings but will do very different stuff.

I want SL to support that kind of things.

Edit: after thinking more I've realized that these examples actually won't be correct functors, but you get the idea.

---

We could still describe optional filed like instance['@static-land'] = TypeDictionary, that people may choose to add to their types. But it can't be mandatory IMO.

Btw, I hope to have some free time soonish and use it to do the rewrite discussed in #32 , and maybe also will add description of the '@static-land' property.

[kwijibo]

I thought the key point of static-land was (contrary to fantasyland) to separate data and behaviour. If instances were linked to their TypeDictionarys, what advantage would that have over fantasyland's linking of instances to their constructors?

What would the advantage be of the option of defining an instance['@static-land'] = TypeDictionary, since consumers of the instance cannot rely on it being present?

[ivenmarquardt]

@kwijibo OK, I assumed that static land is about overcoming the limitations of Javascript's prototype system, not to replace it with no type system at all. Sorry for the confusion.

[kwijibo]

@ivenmarquardt well, this is just my take on it :)

[polytypic]

static land is about overcoming the limitations of Javascript's prototype system

I believe that is a reasonable way to describe an aspect of Static Land.

In JavaScript's prototype system an object only has one prototype chain and when you invoke a method from an instance x, like x.map(...) or x.chain(...), the call always goes to a single method in the prototype chain.

In Static Land, however, one does not invoke methods through the prototype chain. One rather has a separate, explicit dictionary M of methods to invoke, like in M.map(..., x) and M.chain(..., x).

This overcomes at least three limitations of JavaScript's prototype system:

1. A function taking a Static Land dictionary can, in a polymorphic fashion, use multiple sets of functions (multiple different algebraic types) to operate on objects independently of the prototypes of those objects.

2. A function taking a Static Land dictionary can, in a polymorphic fashion, operate on primitive values that do not have prototypes or whose prototypes are built-in and modifying them may not be desirable.

3. A function taking a Static Land dictionary can, in a polymorphic fashion, use the dictionary to create values without having prior access to such values (or, consequently, prototypes of such values) (a motivating example).

[rpominov]

What would the advantage be of the option of defining an instance['@static-land'] = TypeDictionary, since consumers of the instance cannot rely on it being present?

I think one doesn't contradict to another. For example a library author may say in documentation that library's API works only with values that do have @static-land property. This can allow for a simpler library's API, but would require library's users to care about providing values that have the property, and would limit them to only that SL dictionaries that do add the property when create new instances.

This was discussed in detail in https://github.com/fantasyland/fantasy-land/issues/199 in particular in this comment https://github.com/fantasyland/fantasy-land/issues/199#issuecomment-258568380 I describe how I think this could be described in a spec.

[polytypic]

@rpominov I must apologise for not doing my homework on this (I mean, there might a solution that I just don't see clearly discussed in the threads I've glanced over and I should go and read everything in the Fantasy Land spec repos in detail), but how does Fantasy Land solve the number 3 item I mentioned above?

You see, sometimes values of an algebraic type only appear at covariant positions, like this:

problem :: (Traversable t, Applicative f) => (a -> f b) -> t a -> f (t b)

In the above, values of type f _ only appear at covariant positions and consequently the function does not have direct access to any value of such type. (By contrast, a value of type t a appears at a contravariant position.) Furthermore, the traversable t a maybe empty. This is the problem encountered here.

Now, traverse (aka problem) is just one function, and you can "navigate" around it, but how does Fantasy Land spec truly solve this problem in the general case? In the general case you can have any number of algebraic types whose values only appear at covariant positions.

[rpominov]

FL probably doesn't solve this. But still if someone doesn't need to solve problems like that, and don't want to pass dictionaries around, they could rely on the @static-land property.

I mean the approach with @static-land is more limited compared to passing dictionaries explicitly. But it still can be used in cases when these limitations don't matter so much.

[ivenmarquardt]

First of all, thanks for taking the time @polytypic.

My original approach to overcome the mentioned limitations was to utilize a WeakMap in order to extend built-ins. From a practical angle primitives have prototypes too, because of implicit type coercion (the only exceptions are null and undefined, but the latter doesn't count because it shouldn't be used in userland anyway). Now I can extend built-in composite and primitive types:

const All = {
  empty: () => true,
  concat: (x, y) => x && y
};

// type dictionary as a WeakMap

const typeDict = new WeakMap();

typeDict.set(Boolean.prototype, {
  monoid: All
});

const lookup = o => typeDict.get(o.constructor !== undefined 
 ? o.constructor.prototype
 : Reflect.getPrototypeOf(o));

const foldl = xs => xs.reduce(
  lookup(xs[0]).monoid.concat, lookup(xs[0]).monoid.empty()
);

foldl([true, true, true]); // true
foldl([true, true, false]); // false

However, since I use prototypes as keys, there is no way to additionally define the monoid of the logical disjunction. Obviously I can avoid this limitation, when I pass types explicitly:

const foldl = f => acc => xs => xs.reduce(f, acc);
foldl((x, y) => x || y) (false) ([true, true, false]); // true

This is much more expressive. On the other hand it is more error prone, since I can pass the wrong empty element or the wrong reducer. I don't get any support of Javascript's type system anymore.

AFAIK, exactly this happens as soon as you implement static land - but not limited to individual functions, but throughout the program. There is no (proto-)type safety any more, none at all.

So when you claim that static land overcomes the limitations of Javascript's prototype system, I think the spec achieves this by replacing prototypes with...well, nothing. I would hardly call this an improvement.

I still think static land could be useful, as soon as people start to examine the described (and probably other) trade-offs and how to reduce/fight them. And this process/discussion should be reflected in the spec.

Anyway, the issue is closed and this is fine for me. Maybe I didn't do my homework either.

[rpominov]

AFAIK, exactly this happens as soon as you implement static land - but not limited to individual functions, but throughout the program. There is no (proto-)type safety any more, none at all.

I should say I also feel this way sometimes. Especially if simple objects like {type: 'just', value: 1} are used as instances.

[polytypic]

@ivenmarquardt BTW, your example

const All = {
  empty: () => true,
  concat: (x, y) => x && y
};

// type dictionary as a WeakMap

const typeDict = new WeakMap();

typeDict.set(Boolean.prototype, {
  monoid: All
});

const lookup = o => typeDict.get(o.constructor !== undefined 
 ? o.constructor.prototype
 : Reflect.getPrototypeOf(o));

const foldl = xs => xs.reduce(
  lookup(xs[0]).monoid.concat, lookup(xs[0]).monoid.empty()
);

exhibits the number 3 problem solved by Static Land and the problem I linked to: foldMapOf fails with an empty target. Here is what happens if you call foldl with an empty list:

foldl([]);
Uncaught TypeError: Cannot read property 'constructor' of undefined
    at lookup (<anonymous>:1:35)
    at foldl (<anonymous>:2:3)
    at <anonymous>:1:1

This is one of the reasons why I switched to using Static Land in my partial.lenses library (which also implements folds).

[gcanti]

Longer answer could be to encourage the use of static typing

@polytypic I'm working on a functional library in TypeScript in which you can (hopefully) mix and match static-land and fantasy-land styles, I'd love to hear your feedback. Here's a branch (WIP), I think I found a way to fake some behaviours of Haskell type-classes (I mean the definition / instances part). There's a preliminary explanation here.

Long story short: I'd like to have

• static type checking (TypeScript)
• higher kinded types (faked by interface)
• polymorphic functions (through module augmentation)
• fantasy-land style for automatic dictionary selection (through prototype) and as a surrogate of the do notation (.map, .chain chainable APIs)
• static-land style for primitives or when it's not possible to apply FL style (as you noted above)

EDIT: lib is committed in if you want to give it a try (npm install gcanti/fp-ts#haskell)

[ivenmarquardt]

@rpominov @polytypic, since I started this mess I should probably give a reasonable conclusion:

Static land undoubtedly solves actual problems. But giving up the prototype system isn't for free, because we lose the remnant of type safety Javascript provides. This might lead to more laborious development of large-scale programs.

There seem to be essentially four alternatives:

• just deal with it
• use static land along with a static type checker (MS Typescript seems to be optimized for OO-style though)
• consider Javascript as a compile target and use purescript (which is essentially Haskell for the web but without lazy eval and an replacement for IO)
• use FL when possible and SL when necessary

[gcanti]

Static land along with a static type checker works well (and Flow is pretty solid when doing functional programming in static-land style).

However chaining without do notation is awkward

const double = (n: number): number => n * 2
const length = (s: string): number => s.length
const inverse = (n: number): Maybe<number> => maybe.fromPredicate((n: number) => n !== 0)(n)

const o1 = maybe.chain(
  inverse, maybe.map(
    double, maybe.map(
      length, Just('hello'))))

vs

const o2 = Just('hello')
  .map(length)
  .map(double)
  .chain(inverse)

Here is where fantasy-land style really shines.

PureScript is great, but it's hard to introduce in a team.

I'd say that the best balance is mixing FL and ST along with TypeScript or Flow