no-day/fp-ts-graph

Immutable functional graph data structure for fp-ts

no-day

After midnight of every day. Technically it's the next day, but doesn't the next day really start when you wake up in the morning?

Docs

Early prototype

This repo contains a very early prototype of the no-day graph editor.

Run the UI on the current repo

git clone https://github.com/no-day/no-day
cd no-day
yarn install
yarn no-day

The UI is served on port 9000.

Run the UI on another local repo

Currently we don't provide an installer, but you can:

ln -fs $PWD/node_modules/.bin/no-day ~/bin/no-day

And from another monorepo then run:no-day at the root.

fp-ts-graph's Issues

Define absolute paths in tsconfig.json

• Make sure that works from the examples/test folder, too.

package.json `types` and `main` do not point to files

Excerpt from the published package.json

{
  "types": "dist/index.d.ts",
  "main": "dist/index.js",
}

Both of these files do not exist, see the tree of the bundle provided by npm

$ tree ../node_modules/@no-day/fp-ts-graph/            
../node_modules/@no-day/fp-ts-graph/
├── dist
│   └── src
│       ├── index.d.ts
│       └── index.js

The solution I know is to update the package.json like so

{
  "types": "dist/src/index.d.ts",
  "main": "dist/src/index.js",
}

Going to work on a PR

Refactor & completion of CRUD operations

I'd like to make the CRUD operations for edges and nodes more explicit.

Types

Here's a draft for the operations with their planned return types:

Node

• C: insertNode : Either<ErrNodeExists, Graph<...>>
• R: lookupNode : Either<ErrNodeNotExists, Node>
• U: updateNode, modifyNode : Either<ErrNodeNotExists, Graph<...>>
• D: deleteNode : Either<ErrNodeNotExists, Graph<...>>
• (CU: upsertNode : Graph<...>, "the only one that can never fail")

Edge

• C: insertEdge : Either<ErrNodeNotExists | ErrEdgeExists, Graph<...>>
• R: lookupEdge : Either<ErrEdgeNotExists, Graph<...>>
• U: updateEdge, modifyEdge : Either<ErrEdgeNotExists, Graph<...>>
• D: deleteEdge : Either<ErrEdgeNotExists, Graph<...>>
• (CU: upsertEdge : Either<ErrNodeNotExists, Graph<...>>)

Thoughts

• Another option would be to keep operations that can only fail by one cause (almost all of them) in Option instead of Either. That's quite common, but to me it looks more consistent to keep all of them in Either.
• First I was in favor of using the "at" like in fp-ts/Map: insertAt would be insertAtNode, but looking at the above bullets, it seems to me more confusing than helping.

`deploy-docs` should not run on pull requests

https://github.com/no-day/fp-ts-graph/blob/main/.github/workflows/build.yml#L27

however, docs generation should run on regular CI checks

Add `fromEntries`as a simpler way to create a graph

• Should be analogous to toEntries, resulting in an Option<Graph>
• All graph creations in examples/tests should be changed to this more readable and comparable way

Add `tsconfig-build.json`

add tsconfig-build.json that builds only src

Improve performance of graph operations

Due to underlying data structures (Map) it takes O(n) to lookup a node in the graph. fp-ts iterates the map one by one and uses Eq to match the node. This is extremely limiting when having large graphs (thousands+ of nodes) and performing complex traverse operations.

Suggested improvements:

1. Provide io-ts codec which encodes / decodes arbitrary data type to string
2. Replace all occurances of Map with Record and use encoded strings as keys (lookup complexity between O(1) and O(log(n)))

import { Codec } from 'io-ts/Codec';

export interface Graph<Id, Edge, Node> {
  readonly _brand: unique symbol;
  readonly nodes: Record<string, NodeContext<Node>>;
  readonly edges: Record<string, Edge>;
}

type NodeContext<Node> = {
  data: Node;
  outgoing: Set<string>;
  incoming: Set<string>;
};

Usually only first function argument changes from E: Eq<Id> to C: Codec<string, string, Id>. The remaining arguments should remain the same same . The only problem I see is with potential collision when building what's been Direction<T> = { from: T, to: T } and now is string out of two strings (using derived Codec<string, string, string>. We can use some non-standard sequence of UTF characters which is highly unlikely to collide and write an explicit warning in the documentation.

Let me know your thoughts.

publish as `fp-ts-graph` instead of `@no-day/fp-ts-graph`

`prettier-plugin-jsdoc` to devDependencies