cata.ts

import { Covariant } from "@effect/typeclass";
import { absurd, dual } from "effect/Function";
import { Kind, TypeLambda } from "effect/HKT";

type Algebra<F extends TypeLambda, R, O, E, A> = (fa: Kind<F, R, O, E, A>) => A;

class Fix<F extends TypeLambda, R, O, E, A> {
  constructor(public unfix: Kind<F, R, O, E, Fix<F, R, O, E, A>>) {}
}

function cata<F extends TypeLambda, R, O, E, A>(
  algebra: Algebra<F, R, O, E, A>,
  query: Fix<F, R, O, E, A>,
  covariant: Covariant.Covariant<F>,
): A {
  return algebra(
    covariant.map(query.unfix, (subquery: Fix<F, R, O, E, A>) =>
      cata(algebra, subquery, covariant),
    ),
  );
}

interface SelectF<A> {
  _tag: "Select";
  fields: string[];
  subquery: A;
}

interface FilterF<A> {
  _tag: "Filter";
  condition: string;
  subquery: A;
}

interface JoinF<A> {
  _tag: "Join";
  condition: string;
  left: A;
  right: A;
}

interface TableF {
  _tag: "Table";
  tableName: string;
}

type QueryF<A> = SelectF<A> | FilterF<A> | JoinF<A> | TableF;

interface QueryFTypeLambda extends TypeLambda {
  readonly type: QueryF<this["Target"]>;
}

const map: Covariant.Covariant<QueryFTypeLambda>["map"] = dual(
  2,
  <A, B>(self: QueryF<A>, f: (a: A) => B): QueryF<B> => {
    switch (self._tag) {
      case "Select":
        return { ...self, subquery: f(self.subquery) };
      case "Filter":
        return { ...self, subquery: f(self.subquery) };
      case "Join":
        return { ...self, left: f(self.left), right: f(self.right) };
      case "Table":
        return self;
      default:
        return absurd(self);
    }
  },
);

const covariant: Covariant.Covariant<QueryFTypeLambda> = {
  imap: Covariant.imap<QueryFTypeLambda>(map),
  map,
};

type Query = Fix<QueryFTypeLambda, never, never, never, string>;

const sqlAlgebra = (queryF: QueryF<string>) => {
  switch (queryF._tag) {
    case "Select":
      return `SELECT ${queryF.fields.join(", ")} FROM ${queryF.subquery}`;
    case "Filter":
      return `${queryF.subquery} WHERE ${queryF.condition}`;
    case "Join":
      return `${queryF.left} JOIN ${queryF.right} ON ${queryF.condition}`;
    case "Table":
      return `${queryF.tableName}`;
  }
};

function select(fields: string[], subquery: Query): Query {
  return new Fix({ _tag: "Select", fields, subquery });
}

function filter(condition: string, subquery: Query): Query {
  return new Fix({ _tag: "Filter", condition, subquery });
}

function join(condition: string, left: Query, right: Query): Query {
  return new Fix({ _tag: "Join", condition, left, right });
}

function table(tableName: string): Query {
  return new Fix({ _tag: "Table", tableName });
}

const query = select(
  ["users.name", "orders.total"],
  filter(
    "orders.total > 100",
    join("users.id = orders.user_id", table("users"), table("orders")),
  ),
);

const sql = cata(sqlAlgebra, query, covariant);

console.log(sql);

$ node src/cata.js
SELECT users.name, orders.total FROM users JOIN orders ON users.id = orders.user_id WHERE orders.total > 100