fantasyland/static-land

Specification for common algebraic structures in JavaScript based on Fantasy Land

Static Land

This is a specification for common algebraic structures in JavaScript based on Fantasy Land.

• Specification

Difference from Fantasy Land

Fantasy Land uses methods to define interfaces that a type must implement in order to support a particular Algebra. For example values of a type that implements the Monoid algebra must have fantasy-land/empty and fantasy-land/concat methods on them.

Static Land takes a different approach. Instead of methods, we use static functions, that are grouped together in modules.

For example, here is an Addition module that uses numbers as values and satisfies the Monoid algebra requirements:

const Addition = {

  empty() {
    return 0
  },

  concat(a, b) {
    return a + b
  },

}

Pros

• No name clashes. Since a module is just a collection of functions that don't share any namespace we don't have problems with name clashes.
• We can implement many modules for one type, therefore we can have more than one instance of the same Algebra for a single type. For example, we can implement two Monoids for numbers: Addition and Multiplication.
• We can implement modules that work with built-in types as values (Number, Boolean, Array, etc).

Cons

• We have to pass around modules when we write generic code. In Fantasy Land most of generic code can be written using only methods, only if we need methods like of or empty we might need to pass the type representative. (This can be fixed!)

How to add compatibility with Static Land to your library

Simply expose a module that works with types that your library provides or with types defined in another library or with native types like Array.

Modules don't have to be simple JavaScript objects; they can also be constructors if desired. The only requirements are:

• this object contains some static methods from Static Land; and
• if it contains a method with one of the names that Static Land reserves, that method must be the Static Land method (obey laws etc).

Example 1. Static Land module for Array

const SArray = {

  of(x) {
    return [x]
  },

  map(fn, arr) {
    return arr.map(fn)
  },

  chain(fn, arr) {
    // ...
  },

}

export {SArray}

Example 2. Static Land module as a Class

class MyType {

  constructor() {
    // ...
  }

  someInstanceMethod() {
    // ...
  }

  static someNonStaticLandStaticMethod() {
    // ...
  }


  // Static Land methods

  static of(x) {
    // ...
  }

  static map(fn, value) {
    // ...
  }

}

export {MyType}

Example 3. Static Land module as ECMAScript modules

// mytype.js

// Static Land methods

export function of(x) {
  // ...
}

export function map(fn, value) {
  // ...
}

Import as

import * as MyType from "./mytype" // MyType is now a Static Land module

Compatible libraries

We have a list in the wiki. Feel free to add your library there.

• Compatible libraries

static-land's Issues

Better type signatures for methods

While thinking about #32, I've realized that we have another flaw in type signatures that we use. For example:

traverse :: (Traversable t, Applicative f) => Type t ~> (Type f, (a → f b), t a) → f (t b)

Here we say that t must be a Traversable and f must be an Applicative, but that doesn't make sense. We can't require from a type to support an algebra, we can require that only from a module (I use terminology from this comment).

I think we could use something like this instead:

traverse :: (Traversable T t, Applicative A f) => T ~> (A, (a → f b), t a) → f (t b)

which reads as:

• for module T that supports Traversable algebra and works with type t,
• and for module A that supports Applicative algebra and works with type f,
• T has a method traverse,
• that takes module A, a function a → f b, and a value t a,
• and produces f (t b).

---

Somewhat related: #31

chain signature

Hello,

in PureScript and Haskell the signature is

bind :: Bind m => (m a, a → m b) → m b

while in static land is

chain :: Chain m => (a → m b, m a) → m b

Is there a particular reason for that? At first sight having m a near the chain call seems more handy

// current spec
monad.chain((a) => {



  ... long snippet of code ...




}, ma) // <= this is far away from the chain call

Add Filterable

See fantasyland/fantasy-land#274 .
This is just a TODO, for me or anyone else interested.

Equivalent of fantasy-laws?

Is there a way to programmatically test types for compliance with the various laws, similar to using fantasy-laws for Fantasy Land?

Which library implement this?

Remove angle brackets from type signatures

My understanding is that the current signature format exist to match that of Flow and TypeScript, which makes sense. But those signatures exist as they do to match those of C# and Java if I'm not mistaken.

My contention is that the angle brackets, while familiar to users of Flow and TypeScript, are noisy and unnecessary.

ChainRec<T> {
  chainRec: <a, b>((a => Next<a>, b => Done<b>, a) => T<Next<a> | Done<b>>, a) => T<b>
}

This is full of visual noise and makes it difficult for me, the consumer of the spec, to parse.

ChainRec T {
  chainRec: a, b ((a => Next a, b => Done b, a) => T (Next a | Done b), a) => T b
}

This format provides all of the same information with far fewer distracting characters.

Logo

Fantasy Land has a great logo!

We need one too. Anyone with art skills?

Ord compare

what about Ord's compare function?

type Ordering = -1 | 0 | 1
interface Ord<A> extends Setoid<A> {
  compare(a: A, b: A): Ordering
}

In Haskell's hackage about Data.Ord

Minimal complete definition: either compare or <=. Using compare can be more efficient for complex types.

Profunctor and bifunctor

fantasyland/fantasy-land#137
fantasyland/fantasy-land#124

Flow/TypeScript

I have no idea what can be done in this area yet, but wanted to open an issue for general discussion on the topic.

Some relevant links:

https://github.com/donnut/typescript-ramda/
facebook/flow#172

Contravariant Functor?

Would you be interested in a contravariant functor added to the spec?

It would have a method contramap :: Contravariant f => (a -> b, f b) -> f a. It would become a dependency to profunctor. The laws are pretty much the same as for functor, but with a flip on the functions in composition

Happy to make a PR for you to look over

Use traverse instead of sequence for Traversable

See fantasyland/fantasy-land#135

PR is welcomed or I'll do it eventually by myself.

Registry of types to simplify writing polymorphic code

It could look something like this:

const registry = Registry.create()
const polymorphicMap = registry.map

// we don't have code for Nothing, but it doesn't matter for this example
const Maybe = {
  of(value) {
    return {value, __$$type: 'maybe'}
  },
  map(fn, m) {
    return Maybe.of(fn(m.value))
  },
}

// we pass a type object, 
// and a predicate that can tell whether a value can be handled by this type
registry.addType(Maybe, m => m && m.__$$type === 'maybe')

polymorphicMap(x => x + 1, Maybe.of(41)) // Maybe(42)

See also: https://github.com/puffnfresh/bilby.js

Does empty need to be a function?

Currently the empty of Monoid is specified as a nullary function rather than a plain value. Is there a plausible use case that benefits from empty being a function or requires it to be a function?

At the moment, I'm tempted to specify empty as a plain value in a use case of monoid.

Looking for feedback.

Hello all,

Over the past week or so I've been combining what I've learned from static-land and fp-ts into a Deno specific library at https://deno.land/x/hkts. I'm chiming in here to get some feedback and to see if anyone is still interested in static-land implementations.

Additionally, it would be great to know if there is an active community around static land. If so, where do you guys hang out and can I ask you dumb but well prepared questions?

Hope you're all doing well!

Update fromFLType() to Fantasy Land 1.0

Prefixed names and ap's flip...

Better term for what we currently call Type or Type Dictionary

"Type" is the central artefact in the spec, but the name is confusing. The word "type" already has a different meaning in JavaScript, we have types like Array, number, Promise etc.

Fantasy-land recently introduced term "Type Representative". And if we use it in static-land that will be an improvement, but still not good enough. The word "representative" is good, this thing certainly represents something. But does it represent a type? For example what if we have two representatives:

const Addition = {
  empty() {
    return 0
  },
  concat(a, b) {
    return a + b
  },
}

const Multiplication = {
  empty() {
    return 1
  },
  concat(a, b) {
    return a * b
  },
}

What types they represent exactly? Do they both represent number? That doesn't sound right. What they actually represent are collections of operations on type number. Addition represent one such collection and Multiplication another one. So a correct name would be "Collection of Operations Representative", but that is a terrible name of course.

As far as I understand in OCaml similar things are called "modules", that would be a good name if that word didn't already have a different meaning in JS community.

Any suggestions on a better name?

This was previously discussed here #30 (comment) .

/cc @tel @isiahmeadows

Should we use chainRec (if avalible) in runGenerator()?

It might be a good idea. Need to investigate...

Add ChainRec

See fantasyland/fantasy-land#152

Should ap be parallel?

Comonad/Extend implementation

In fantasy land Extend implements Functor, in static land Extend is by itself and Comonad implements both Functor and Extend.
Just would like to figure out who is more right :)

Reconsider currying

The spec currently require that all methods of each type must be curried. Which is cool, but might be problematic sometimes.

Some problems are:

• It might affect performance
• It makes call stack ugly which is a problem when debugging etc.
• One have to depend on a module that provides a curry function
• We can't have optional arguments in a curried function

We could change the spec in a way that it won't require methods to be curried, but also won't require otherwise, so people could choose to use currying or not by themselves.

Related: #2

Help needed to proofread the spec

I'm not a native english speaker myself and know that everything I write can be improved (grammar, wording, etc.)

Would really appreciate if someone could proofread the spec and other documents (readme, api ref.)

Feel free to send PRs. Thanks!

Add traversable to the spec

Reference to a canonical module in values

I propose adding the following section to the specification:

---

Any value may have a reference to a canonical module that works with values of that value's type. The reference should be in the static-land/canonical property. For example:

const ListModule = {
  of(x) {
    return {'static-land/canonical': ListModule, data: [x]}
  },
  map(f, v) {
    return {'static-land/canonical': ListModule, data: v.data.map(f)}
  }
}

In case a value has a reference to a canonical module, that module must produce values with references to itself. In the following example, list is an incorrect value, because ListModule2 does not produce values with references to itself:

const ListModule2 = {
  of(x) {
    return {data: [x]}
  },
  map(f, v) {
    return {data: v.data.map(f)}
  }
}

const list = {'static-land/canonical': ListModule2, data: [1]}

Note that the ListModule2 here is correct. Only the list value doesn't follow the specification.

---

This will allow for generic code without passing modules. For example:

function lift2(f, a, b) {
  const T = a['static-land/canonical']
  return T.ap(T.map(a => b => f(a, b), a), b)
}

lift2((x, y) => x + y, ListModule.of(2), ListModule.of(3)) // ListModule.of(5)

Any thoughts on the idea itself, or specific details, or wording of the section?

This idea was discussed before in fantasyland/fantasy-land#199

Add Semigroupoid, Category, Group

These algebras were added to Fantasy Land, we need to add them too.
This issue is more like a reminder for me, but if anyone wants to submit a PR, please do.

Standard library?

Is there a standard library for built-in types like Array, Object, Map, etc? Something like Sanctuary is for Fantasy Land, but tree-shakable? I also noticed fp-ts but I want to avoid using Typescript.

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

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

Spelling Mistake Example 2

Hello,
there is a spelling mistake in Example 2.

class A = {}

is invalid Syntax
it should be

class A {}

I opened a PR for it #53

Fantasy Land adapter

I think it may be easier to use if instead of using fromFLType, you just created generic wrappers for them. It'd be rather trivial, anyways.

What's the right order in Apply?

Hi,

What's the right order in apply.

What should be the result in the following case?

T.ap(T.Left(1), T.Left(2))

Following the same logic, what would be the right order on traverse?

ARR.traverse(T, x=>x, [T.Left(1), T.Left(2)])

Thanks.

@@functional/placeholder support

See http://ramdajs.com/0.19.1/docs/#__ and https://github.com/ramda/ramda/blob/v0.19.1/src/__.js

Having a method doesn't mean having an algebra (problem with deriveAll)

deriveAll does algebra detection based on what methods the type has. But, for example, if a type has of and chain it doesn't mean it has Monad algebra. To support an algebra a type must have certain methods, but this rule doesn't work in the reverse direction.

We probably should add an algebras argument to deriveAll. Automatic detection based on methods is a good default though.

Laziness

Laziness can be useful with algebraic types. I recently implemented an experimental approach to laziness in my partial.lenses library. The idea is briefly discussed in issue 56.

The experimental approach used in partial.lenses is based on having an optional delay operation.

Concretely, in the case of Monoids, the optional delay has a signature like:

delay :: Monoid a => (() -> a) -> a

And in the case of Applicatives, the delay has a signature like:

delay :: Applicative c => (() -> c a) -> c a

In some cases, it is possible to derive the delay operation from other operations. In the case of Monads:

const deriveDelayForMonad = M => u2xM =>
  M.chain(_ => u2xM(), M.of(undefined))

The support for laziness in partial.lenses is considered experimental partly due to not having the concept in the Static Land Specification. Perhaps Static Land could be enhanced with support for laziness?

Addition: The F# Computation Expression Zoo paper contains some relevant discussion on considerations for impure effects and delayed computations in a strict language in conjunction with algebraic types (mostly Monads).

Static-land-based Higher-Kinded-Type encoding for TypeScript

👋 I've been playing around with a HKT encoding for TypeScript, and it is my goal to have it match quite closely to the Static-Land specification. I was generally hoping to solicit some feedback to make sure I'm not doing anything obviously wrong. If this is the wrong place to ask just let me know where would be appropriate.

This encoding only works for TypeScript 4.x, which at the time of this writing is available at typescript@next and is not considered stable. However, with it's feature-set including variadic tuples, it enables some interesting features and that makes the use of HKTs in TS a bit easier over existing solutions.

Here's the link to the library https://github.com/TylorS/hkt-ts, and thank you in advance!

Traversable: missing dependencies in spec.md?

Dependencies

• Functor
• Foldable

Static Land vs FL args order

eg, apply. Does it needs to be updated? Does static-land and FL aims to share args order?

fix Compose type (it's not a valid aplicative currently)

Spec versioning

We'll probably need to change spec over time. So we can end up in a situation where two libs use different spec versions and can't be used together. We should find the least painful way for dealing with those situations.

Implementing nested type constraints

I'd love to hear your advice on how to implement nested type constraints.

Introduction

When I see the following spec

// Semigroup
concat :: Semigroup s => (s, s) → s

I automatically define the following 2 things (using pseudo code and the flow syntax in order to emphasize the types)

// Semigroup.js
export interface Semigroup<S> {
  concat(a: S, b: S): S
}

export function concat<S>(dictSemigroup: Semigroup<S>, a: S, b: S): S {
  return dictSemigroup.concat(a, b)
}

Here Semigroup<S> mimic a type class while dictSemigroup represent the Semigroup s => type contraint.

An example

const StringSemigroup = {
  concat(a: string, b: string): string {
    return a + b
  }
}

import { concat } from './Semigroup'
concat(StringSemigroup, 's1', 's2') // => 's1s2'

The problem

The problem comes when there are nested type contraints. Let's define a Semigroup instance for Maybe

// I can't implement this
const MaybeSemigroup = {
  concat<S>(a: Maybe<S>, b: Maybe<S>): Maybe<S> {
    if (isNothing(a) || isNothing(b)) {
      return Nothing
    }
    return Just(concat(?, a, b)) // <= here's the problem; I don't have an instance of Semigroup for S
  }
}

How could I implement MaybeSemigroup?

Now I'm doing something like this but I'm not entirely satisfied, are there other options?

function getMaybeSemigroup<S>(dictSemigroup: Semigroup<S>): Semigroup<Maybe<S>> {
  return concat<S>(a: Maybe<S>, b: Maybe<S>): Maybe<S> {
    if (isNothing(a) || isNothing(b)) {
      return Nothing
    }
    return Just(concat(dictSemigroup, a, b))
  }
}

Use some system for letters (names of types values etc.) in the spec

Currently it's a bit of a mess, and we need to invent some sort of naming system...

Do notation using generators

Using https://github.com/pelotom/burrido or similar approach we could make it look something like this:

import {do, SArray} from 'static-land'

const result = do(SArray, function* () {
  const x = yield [1, 2]
  const y = yield [3, 4]
  return x * y
}) 

result // [3, 4, 6, 8]

New standard for creating algebraic data types.

I'd like to propose a new standard for creating algebraic data types. Consider the following.

const Maybe = {}; // Static Land Canonical Module

const Nothing = (() => {
    function Nothing() {}
    Nothing.prototype["static-land/canonical"] = Maybe;
    return new Nothing; // Singleton Pattern
})();

function Just(value) {
    if (this instanceof Just) this.value = value;
    else return new Just(value); // Hack for calling the constructor without `new`.
}

Just.prototype["static-land/canonical"] = Maybe;

The primary advantage of defining algebraic data types like we did above, is good console logs.

> Nothing
Nothing {}
> Just(10)
Just { value: 10 }

Pattern matching is also standardized. You can use pattern matching with built-in types too.

Maybe.map = (mapping, maybe) => {
    switch (maybe.constructor.name) {
        case "Nothing": return Nothing;
        case "Just": return new Just(mapping(maybe.value)); // Using `new` for performance.
    }
};

We can also create a utility function which makes defining new data constructors less verbose.

const data = (type, name, ...keys) => {
    const {length} = keys;

    function Data(...vals) {
        if (this instanceof Data)
            for (let i = 0; i < length; i++)
                this[keys[i]] = vals[i];
        else return new Data(...vals);
    }

    Object.defineProperties(Data, {
        name:   { value: name },
        length: { value: length }
    });

    Data.prototype["static-land/canonical"] = type;

    return length > 0 ? Data : new Data;
};

This makes it easy to define new data constructors for algebraic data types.

const Maybe = {};

const Nothing = data(Maybe, "Nothing");

const Just = data(Maybe, "Just", "value");

I would love to hear your thoughts on this, and continue the discussion in #45 here.

Make sure multi-value use-case doesn't hurt one-value case in runGenerator