building and traversing a tree using fp-ts

node.test.ts

import {
  Lineage,
  Node,
  getSubtreeByLineage,
  treeFromLineageArray,
  walkTreeDepthFirst,
} from "../node";

describe("Node", () => {
  const LINEAGE_ARRAY_FIXTURE: ReadonlyArray<Lineage> = [
    ["a"],
    ["b", "b1"],
    ["b", "b2"],
    ["c", "c1", "c1a"],
    ["c", "c1", "c1b"],
  ];
  const TREE_FIXTURE: Node = {
    a: null,
    b: { b1: null, b2: null },
    c: { c1: { c1a: null, c1b: null } },
  };
  const DFS_FIXTURE = [
    ["a", getSubtreeByLineage(TREE_FIXTURE, "a")],
    ["b1", getSubtreeByLineage(TREE_FIXTURE, "b", "b1")],
    ["b2", getSubtreeByLineage(TREE_FIXTURE, "b", "b2")],
    ["b", getSubtreeByLineage(TREE_FIXTURE, "b")],
    ["c1a", getSubtreeByLineage(TREE_FIXTURE, "c", "c1", "c1a")],
    ["c1b", getSubtreeByLineage(TREE_FIXTURE, "c", "c1", "c1b")],
    ["c1", getSubtreeByLineage(TREE_FIXTURE, "c", "c1")],
    ["c", getSubtreeByLineage(TREE_FIXTURE, "c")],
  ];

  describe("treeFromLineageArray", () => {
    it("should build complex tree", () => {
      expect(treeFromLineageArray(LINEAGE_ARRAY_FIXTURE)).toEqual(TREE_FIXTURE);
    });

    it("should return empty", () => {
      const input: ReadonlyArray<Lineage> = [];
      const expected: Node = {};
      expect(treeFromLineageArray(input)).toEqual(expected);
    });
  });

  describe("getSubtreeByLineage", () => {
    it("should get undefined", () => {
      expect(getSubtreeByLineage(TREE_FIXTURE, "z")).toBeUndefined();
    });

    it("should get null", () => {
      expect(getSubtreeByLineage(TREE_FIXTURE, "a")).toBeNull();
    });

    it("should get b's tree", () => {
      expect(getSubtreeByLineage(TREE_FIXTURE, "b")).toEqual(TREE_FIXTURE["b"]);
    });
  });

  describe("depth first ", () => {
    it("should walk depth first", () => {
      expect(walkTreeDepthFirst(TREE_FIXTURE)).toEqual(DFS_FIXTURE);
    });

    it("should walk nowhere", () => {
      expect(walkTreeDepthFirst({})).toEqual([]);
    });
  });
});

node.ts

import {
  either,
  function as func,
  option,
  ord,
  readonlyArray,
  readonlyNonEmptyArray,
  record,
  string,
} from "fp-ts";

export type Defined<T> = T extends undefined ? never : T;
export type Node = {
  [K in string]?: Node | null;
};
export type NodeEntry = Defined<Node[keyof Node]>;
export type Lineage = readonlyNonEmptyArray.ReadonlyNonEmptyArray<string>;

export const enhanceTreeWithLineage = (
  tree: Node,
  [first, ...remainder]: Lineage,
): Node => {
  return {
    ...tree,
    [first]: func.pipe(
      remainder,
      readonlyNonEmptyArray.fromArray,
      option.map((nonEmptyRemainder) =>
        enhanceTreeWithLineage(
          func.pipe(
            option.fromNullable(tree[first]),
            option.getOrElse(() => ({})),
          ),
          nonEmptyRemainder,
        ),
      ),
      option.getOrElse<NodeEntry>(func.constNull),
    ),
  };
};

export const treeFromLineageArray = (
  lineages: ReadonlyArray<readonlyNonEmptyArray.ReadonlyNonEmptyArray<string>>,
): Node =>
  func.pipe(
    lineages,
    readonlyArray.reduce({}, (tree, lineage) =>
      enhanceTreeWithLineage(tree, lineage),
    ),
  );

export const walkTreeDepthFirst = (
  tree: Node,
): ReadonlyArray<[string, NodeEntry]> =>
  func.pipe(
    tree,
    record.toEntries,
    readonlyArray.filter(
      (entry): entry is [string, NodeEntry] => entry[1] !== undefined,
    ),
    readonlyArray.sort(
      func.pipe(
        string.Ord,
        ord.contramap<string, [string, NodeEntry]>(([key]) => key),
      ),
    ),
    readonlyArray.map(([key, subtree]) =>
      func.pipe(
        subtree,
        option.fromNullable,
        option.map((nonNullSubtree) => walkTreeDepthFirst(nonNullSubtree)),
        option.map((results) =>
          func.pipe(results, readonlyArray.append(func.tuple(key, subtree))),
        ),
        option.getOrElse<ReadonlyArray<[string, NodeEntry]>>(() =>
          readonlyArray.of(func.tuple(key, subtree)),
        ),
      ),
    ),
    readonlyArray.flatten,
  );

export const getSubtreeByLineage = (
  tree: Node,
  ...lineage: Lineage
): Node | null | undefined => {
  return func.pipe(
    lineage,
    readonlyNonEmptyArray.reduce(
      either.right<undefined, NodeEntry>(tree),
      (subtree, path) =>
        func.pipe(
          subtree,
          either.chain(
            func.flow(
              option.fromNullable,
              either.fromOption(func.constUndefined),
              either.map((value) => value[path]),
              either.filterOrElse(
                (value): value is NodeEntry => value !== undefined,
                func.constUndefined,
              ),
            ),
          ),
        ),
    ),
    either.fold(func.identity, func.identity),
  );
};