fantasy-land compliance

[SimonMeskens]

Typed Static-land compliance

This document outlines a strategy that promises at the very least a guarantee a library will not become incompatible with the Static-land specification and at best allows a path towards full compatibility, without clobbering users with hard to understand terminology, such as monoids, monads and functors.

Rules

A list of Static-land reserved function names, with TypeScript types, is provided at the bottom

1. No type will export a function name out of the reserved list, without also sharing type and behavior
2. If a function shares the type of a Static-land reserved function and has the same behavior, either an alias is made or the method receives the same name

The first rule simply means that if you have, for example, a map method that's not compliant with the Functor.map, you name it transform or select instead. Array.map is compliant with Functor.map, it's actually unusual for name collisions to happen, as Static-land is based on vanilla JavaScript.
The second rule is just to make sure that if there exists, for example, a flatMap compliant with Chain.chain (as in many libraries), compatibility with Static-land is ensured by either having an alias or simply naming it chain in the first place.

Fantasy-land compliance

Each type that exports Static-land compliant functions also has non-enumerable namespaced methods on the type. For example, if a map function exists, the type itself also has a fantasy-land/map property, which is compliant with Fantasy-land (usually the same signature as Static-land, but with this functioning as the type to act on. By making these non-enumerable, you only come across them if you're looking (no pollution of the type). These act as a formal protocol for libraries such as Ramda, so they know how to handle that type.

Static-land reserved functions

For expected behavior, check the Static-land spec. These mostly do exactly what you expect them to do. Static-land never collapses though, so a list of lists is never automatically flattened, for example. Obviously, names of parameters are not important, signature is.

In these, Type is a stand-in for the type in question, generic parameters are noted as A, B, C, etc. A type can always have more generic parameters than specified, but never less.

  equals(a: Type, b: Type): boolean
  lte(a: Type, b: Type): boolean
  concat(a: Type, b: Type): Type
  empty(): Type
  map<A, B>(f: (a: A) => B, ta: Type<A>): Type<B>
  bimap<A, B, C, D>(fa: (a: A) => B, fc: (c: C) => D, ta: Type<A, C>): Type<B, D>
  contramap<A, B>(f: (a: A) => B, tb: Type<B>): Type<A>
  promap<A, B, C, D>(fa: (a: A) => B, fc: (c: C) => D, tbc: Type<B, C>): Type<A, D>
  ap<A, B>(f: Type<(a: A) => B>, ta: Type<A>): Type<B>
  of<A>(a: A): Type<A>
  alt<A>(a: Type<A>, b: Type<A>): Type<A>
  zero<A>(): Type<A>
  chain<A, B>(f: (a: A) => Type<B>, ta: Type<A>): Type<B>
  chainRec // Not easily typable in TypeScript
  reduce<A, B>(f: (a: A, b: B) => A, a: A, tb: Type<B>): A
  extend<A, B>(f: (ta: Type<A>) => B, ta: Type<A>): Type<B>
  extract<A>(ta: Type<A>): A
  traverse // Not easily typable in TypeScript

Progress

General

• Refactor all isEqual functions to equals
• Add namespaced fantasy methods
• Write tests for the laws in Static-land

List

• Look at unifying List with other structures #31
• Add fold primitive to internals
• Add List/of
• Add List/zero
• Add List/alt
• Add List/map #51
• Add List/filter
• Add List/ap
• Add List/reduce
• Add List/chain
• Add List/traverse
• Add List/extend

Original Post: How important is compliance to fantasy-land/static-land for this project? I'd like to use this project together with Ramda and fantasy-land libraries.

I'm willing to help out on this front

[axefrog]

Hey Simon, I'm open to this, though my knowledge of functional primitives is kind of only at a lower beginner-intermediate level, so I'd probably need some coaching here. I honestly don't have much idea of what the different primitives do, or where a lot of them are applicable. I kind of see functional programming as something you can go shallow or deep on. At a shallow level, you can do a lot by following general functional principles - referential transparency, immutability, composition, laziness, higher-orderedness, and so forth. At the deeper level you start using the primitives - functors, monoids, monads, applicatives, etc. That's the part I'm kind of fuzzy on.

[SimonMeskens]

Luckily, the fantasy-land spec has done most of the hard work for you. The idea is that you just need correct implementations of the primitives and other libraries can build useful software on top of them. The abstractions just become a protocol by convention that makes it work (in the same way that protocols like HTTP/TCP/IP/etc are also hard to reason about, but trivial to implement and act like glue to create software layers on top).

In fact, most of the primitives are actually quite useful (for example, Immutable.js' flatMap has exactly the same type signature and behavior as chain in the Chain primitive, they are the same thing. Most collection libraries have flatMap, because it's not an ivory tower abstract concept, it's also a useful function.

My proposal is this: I'm going to write a document that outlines a simple strategy to follow, that makes sure at the very least that this library doesn't become incompatible with fantasy-land libraries such as Ramda and at best provides a path to full compatibility. None of it will involve introducing abstract terms into the library (the word monad will not appear anywhere in the codebase). I'll get back to you when it's done and you can decide if it's something you'd want to introduce. Sound good?

[SimonMeskens]

Proposal: Typed Static-land compliance

This document outlines a strategy that promises at the very least a guarantee a library will not become incompatible with the Static-land specification and at best allows a path towards full compatibility, without clobbering users with hard to understand terminology, such as monoids, monads and functors.

Rules

A list of Static-land reserved function names, with TypeScript types, is provided at the bottom

1. No type will export a function name out of the reserved list, without also sharing type and behavior
2. If a function shares the type of a Static-land reserved function and has the same behavior, either an alias is made or the method receives the same name

The first rule simply means that if you have, for example, a map method that's not compliant with the Functor.map, you name it transform or select instead. Array.map is compliant with Functor.map, it's actually unusual for name collisions to happen, as Static-land is based on vanilla JavaScript.
The second rule is just to make sure that if there exists, for example, a flatMap compliant with Chain.chain (as in many libraries), compatibility with Static-land is ensured by either having an alias or simply naming it chain in the first place.

Fantasy-land compliance

Each type that exports Static-land compliant functions also has non-enumerable namespaced methods on the type. For example, if a map function exists, the type itself also has a fantasy-land/map property, which is compliant with Fantasy-land (usually the same signature as Static-land, but with this functioning as the type to act on. By making these non-enumerable, you only come across them if you're looking (no pollution of the type). These act as a formal protocol for libraries such as Ramda, so they know how to handle that type.

Static-land reserved functions

For expected behavior, check the Static-land spec. These mostly do exactly what you expect them to do. Static-land never collapses though, so a list of lists is never automatically flattened, for example. Obviously, names of parameters are not important, signature is.

In these, Type is a stand-in for the type in question, generic parameters are noted as A, B, C, etc. A type can always have more generic parameters than specified, but never less.

  equals(a: Type, b: Type): boolean
  lte(a: Type, b: Type): boolean
  concat(a: Type, b: Type): Type
  empty(): Type
  map<A, B>(f: (a: A) => B, ta: Type<A>): Type<B>
  bimap<A, B, C, D>(fa: (a: A) => B, fc: (c: C) => D, ta: Type<A, C>): Type<B, D>
  contramap<A, B>(f: (a: A) => B, tb: Type<B>): Type<A>
  promap<A, B, C, D>(fa: (a: A) => B, fc: (c: C) => D, tbc: Type<B, C>): Type<A, D>
  ap<A, B>(f: Type<(a: A) => B>, ta: Type<A>): Type<B>
  of<A>(a: A): Type<A>
  alt<A>(a: Type<A>, b: Type<A>): Type<A>
  zero<A>(): Type<A>
  chain<A, B>(f: (a: A) => Type<B>, ta: Type<A>): Type<B>
  chainRec // Not easily typable in TypeScript
  reduce<A, B>(f: (a: A, b: B) => A, a: A, tb: Type<B>): A
  extend<A, B>(f: (ta: Type<A>) => B, ta: Type<A>): Type<B>
  extract<A>(ta: Type<A>): A
  traverse // Not easily typable in TypeScript

[SimonMeskens]

I did some quick checking and so far, it seems like the library already correctly uses of, map, concat, equals and empty.

Prime candidates for inclusion are chain (for lists this is a flatMap), ap (for list, a variant of flatMap that's kinda like zipWith), alt (for list, this is just an alias for concat) and zero (for list, just an alias of empty).

[axefrog]

I'm going to go ahead and give a preliminary nod to this. I can't see any downside. For what it's worth, I'm a heavy use of Most.js, which also has FantasyLand compliance, so have used chain, ap and others a lot.

Before you go ahead though, you should be aware that the README documentation for Collectable is a bit out of date, primarily with respect to mutation. See here for an overview, and see the link in that comment as well. It's important to understand how the mutation API works before proceeding; it's quite a bit more powerful than what Immutable.js provides, and underpins the implementation of every persistent structure and substructure in this library.

I'll also disclaim my lack of up-to-date documentation in that this kind of library is a lot of work for just one person and you're one of the very few people that has demonstrated any genuine interest in the project, so I have't had a lot of help. The library is 100% alive though, and has long-term relevance for me, so I have a vested interest in its survival and success. Also, one of the reasons for the low number of commits at the moment is that I'm dogfooding this in a real project, so most of work is there. The point is I'm actively using it though.

I'll also come back to you after I have a chance to properly read through your comments and look at FantasyLand a bit more closely.

[SimonMeskens]

The only real downside is that some of the operations tend to be the same for certain collections. For example, alt/concat and empty/zero are the same for lists. This means you get some duplication (why do we need both alt and concat if they do the same thing? etc).

In any case, I just put around 50 hours into Immutable.js, only to bang my head against my desk over and over. This library, on the other hand, seems wonderful and exactly what I need.

I'll make a PR with additions to List, so we can review what's working and what isn't. I won't focus on performance straight away, as that'll require me to gain some knowledge first.

I'll leave the issue open until the PR lands

[axefrog]

Cool, I'm glad it fits your needs. I'm quite open to evolving/improving the existing API where solid cases can be made. I still think of the library as pre-release, and there are numerous things that need to be done when time permits (there are some inconsistent APIs between collections, the deep operations API is lacking, documentation is lacking, some things need more unit tests, etc.). As such, breaking changes don't bother me at this point. The take on SemVer that I outline in the Contributors document will mitigate any issues with breakage.

May I ask what issues you personally had with Immutable.js?

[axefrog]

I'll make a PR with additions to List, so we can review what's working and what isn't. I won't focus on performance straight away, as that'll require me to gain some knowledge first.

Note: #31 and #19 - List's implementation is really complicated because my original strategy was half learning how to implement this kind of thing, and half implementing my own specialised kind of internal zipper for fast ongoing traversal and modification of the list. #19 describes the changes I'd make now if I had a chance. Don't feel bad if you can't figure out what my code is doing, though feel free to ask me anything if you do end up wanting to tackle that.

[SimonMeskens]

May I ask what issues you personally had with Immutable.js?

The same issue I had with Flow, I feel like Facebook doesn't embrace open-source. There's a laundry list of long-standing bugs that aren't being fixed and there's a number of important fixes from months back that haven't been released yet. Recently, the typings for TypeScript broke (the compiler crashes if you even try to use them) and the only reaction by the team has been: "we'll accept a PR".

So I'm looking for a true open-source product with a contribution strategy and a release strategy, but I still want persistent data structures. The fact that Collectable also adheres closer to FRP techniques is a huge bonus too.

[axefrog]

Ah yeah, actually the reason I created this library was because I too was using Immutable.js and I was frustrated that it lacked certain features and functionality I wanted, and that it was entirely class-based, which meant if I were to use one thing, it'd drag the entire library into my application bundle. Development seemed pretty stagnant too, as you said. There was nothing else out there that matched what I needed, so I ended up diving in and learning how to write my own immutable data structures. My biggest wants were a list structure that supported fast dissection and concatenation operations, and ordered collections that I could actually control the sorting characteristics of. RedBlackTree has turned out to be the collection I use the most, by far, despite there being SortedMap and SortedSet structures. Turns out that a lot of the time you already know the type of key you're going to use, and the problem domain doesn't include key collisions, so RBT ends up being a perfect fit.

[shinzui]

I stumbled upon collectable while looking for a fantasy-land compatible immutable DS library to replace Immutable.js. I'm currently forced to use invoker(0, 'toJS') more often than I like, and lose the immutability. I really hope the 1.0 release will be fantasy-land compliant.

[SimonMeskens]

hey @shinzui

I have a few more PRs ready for Fantasy-land support, but my job got kinda hectic in August and onwards. I'll try to push the stuff I have and share the parts that still need to be done (I have them in a gist somewhere).

[axefrog]

@SimonMeskens I've spent some time in the last couple of months getting a better handle on FL and SL in the process of my own work. I'm by no means a beacon of knowledge on the subject, but I've got a better appreciation for the two now, and will apply that knowledge to any future changes to the library.

When I finally get a chance (or more likely when I need to for my own work), I'm going to embark on a process of cleaning up and filling out the API for each collection (internal refactoring of List, et al, notwithstanding). When I do this, I'll be looking for input on aspects of the current API that could use improvement. Such feedback is welcome before then as well, but the point is that I think Collectable is still relatively unknown, and I have no idea if anyone other than me is using it all for anything beyond personal experimentation. You seem to be doing something with it, so you'll probably be the first person I ask :)

[SimonMeskens]

@axefrog Feel free to always tag me for questions. I'm currently using Collectable for a video game that I stream the creation of occasionally, so I'm also giving the library some exposure (not much, I have like 10 viewers). Basically, Collectable has become my default collection library right now, for personal projects.

I also plan on donating more code at some point when life slows down again (August to March is really busy for me, then I get a long slow summer).

In the interim since the last time we spoke, I've also gotten involved a bit more with FL and SL projects and it does seem like TypeScript still has a major problem typing some of the more useful parts of functional programming, including libraries that could consume FL or SL enabled libraries, so it's all still very early to worry about these things anyway.

[axefrog]

Cool.

it does seem like TypeScript still has a major problem typing some of the more useful parts of functional programming

I've had the same experience, often spending more time fighting the type system than getting work done. I've come to the conclusion that for heavily-functional codebases, TS is not currently a great fit. I'm removing it from the core of my own project and restricting it to simpler libraries such as Collectable, for now at least.

[SimonMeskens]

I'm not sure if Fantasy Land is the end-all be-all for TypeScript btw. The issue is that Fantasy Land is not curried and TypeScript doesn't like that very much. It does much better at typing curried functions (curried in the sense that you provide arguments one by one, not that it does fully curried partial application).

I feel like part of the issue is trying to shoehorn Haskell into TypeScript. We should figure out new solutions and new abstractions based on what's possible, not try to adapt the really tricky parts of Haskell into TypeScript. TS can do things Haskell can't and vice versa, it's just not a good fit. It will never be a good fit either, because it's essentially using a different inference strategy. There will always be tricky parts of Haskell left that won't make it into TypeScript (typeclasses and traits?)

That said, I do still think it's a good idea to get most of FL/SL into Collectable, as every collection should really have most of the operations, like map/chain/of, because they make sense.

[SimonMeskens]

Also, here's my TODO list, I'm not sure which of these I might not have PRed yet, I'll check when I have time:

General

• Refactor all isEqual functions to equals
• Add namespaced fantasy methods
• Write tests for the laws in Static-land

List

• Look at unifying List with other structures #31
• Add fold primitive to internals
• Add List/of
• Add List/zero
• Add List/alt
• Add List/map #51
• Add List/filter
• Add List/ap
• Add List/reduce
• Add List/chain
• Add List/traverse
• Add List/extend

[SimonMeskens]

I'm not sure how important adding traverse is btw, it seems rather limited in use, so I think List is mostly ready (I might need to PR a few parts still, I'll check the commit tree locally).

One good thing about the local implementation in a collection library is that we don't need to work at the higher abstraction level. We can do most things without Higher Kinded Types and the like and leave the worry to libraries like Ramda to handle that for us. One big issue is that there doesn't seem to be a really good TypeScript-first functional library due to the issues mentioned above.

[SimonMeskens]

I added the useful parts of the conversation to the OP, let me know if anything is unclear

[axefrog]

I feel like part of the issue is trying to shoehorn Haskell into TypeScript. We should figure out new solutions and new abstractions based on what's possible, not try to adapt the really tricky parts of Haskell into TypeScript.

Agreed. I think there is a hole in the market for a TS-like product that is architected around a desire for functional approaches, rather than focusing on the OO crowd, but unfortunately nothing like that exists for JS at the moment.

I'm not sure how important adding traverse is btw, it seems rather limited in use, so I think List is mostly ready (I might need to PR a few parts still, I'll check the commit tree locally).

Methods like traverse are perhaps more appropriate for the deep operations API in the main package. I don't have any strong feelings about it though.

[SimonMeskens]

I don't have any strong feelings about it though

Neither do I. I think the strategy for those kinds of things is easy, if there's no strong reason to have it, don't implement until there's a consuming library that makes use of it.

Agreed. I think there is a hole in the market for a TS-like product that is architected around a desire for functional approaches, rather than focusing on the OO crowd, but unfortunately nothing like that exists for JS at the moment.

I do plan on working on a TS-library that does abstractions the typescript way, but I'm not sure how hard it will be. I have a few novel ideas, but I'd need to start hacking away. I assume part of the solution would be to use a different model of computation, instead of a heavily lambda-calculus based approach. I have some books on my shelf that might be helpful, but they're so math-heavy it takes me a couple of hours per page.

[axefrog]

I do plan on working on a TS-library that does abstractions the typescript way, but I'm not sure how hard it will be.

Funny you say that - my full time project is a decentralised system that is entirely built around continuous-time signals, demand-based computation, and streams. I've had it in my head a for a little while now that this would be the perfect platform for building a TS-like compiler (i.e. just go ahead and write JS code) that does not require type annotations in 99% of cases, and is able to use graph-based modelling and set theory to provide strong, deep inference everywhere, without having a million things chunking up memory simultaneously. I'm also super interested in having such a compiler that centres around graph nodes rather than source code files, which would open up all kinds of possibilities for dealing with imports, namespaces, contextually-relevant code, etc.

[axefrog]

By the way, jump into https://gitter.im/FRPTools/Lobby if you want to discuss things without de-railing the thread.

[axefrog]

@SimonMeskens FYI, I have a number of updates and bug fixes in my local copy of the repo, but the repo is undergoing some (slow, unfinished) restructuring at the moment, which means I haven't been able to push the changes to Github yet. I should probably make a dev branch I guess. Anyway, the latest changes and bug fixes are actually published to NPM, so you might want to update your dependencies. Fixes include webpack-breaking circular deps, infinite looping in HashSet, bug fixes and some new ordinal lookup methods in SortedMap, and some other bug fixes (I think in RedBlackTree and List).

[SimonMeskens]

Thanks, I'll have a look next time I'm doing dev

[grossbart]

I really like libraries that support Fantasy Land, so I‘m happy this is being worked on :) Also, thank you for making the library!

For reference, there is a nice FL list implementation available here: https://github.com/funkia/list/blob/master/README.md

Also, to understand the usefulness of FL this really helps: https://github.com/MostlyAdequate/mostly-adequate-guide

As for how to implement some of the more complicated things in TypeScript, Canti has a great library here: https://github.com/gcanti/fp-ts You could implement the API using its type classes, I think, but that would of course introduce a dependency.