muref.scala

// https://hackage.haskell.org/package/data-reify

import java.util.IdentityHashMap

trait MuRef[T]:
  type F[_]

  def recurse[U](t: T)(f: T => U): F[U]

trait NuRef[T]:
  type F[_]

  def recons[U](fu: F[U])(f: U => F[U]): T

opaque type Unique = Int

object Unique:
  inline def apply(u: Int): Unique = u

final case class Graph[F[_], V](root: V, edges: Map[V, F[V]]):
  def to[T](using nu: NuRef[T], ev: F[V] =:= nu.F[V]): T =
    nu.recons(ev(edges(root)))(v => ev(edges(v)))

object Graph:
  def from[T](t: T)(using mu: MuRef[T]): Graph[mu.F, Unique] =
    var unique = 0
    def nextUnique(): Unique =
      val u = unique
      unique += 1
      Unique(u)

    val idMap: IdentityHashMap[T, Unique] = IdentityHashMap()
    val edges = Map.newBuilder[Unique, mu.F[Unique]]

    def convert(t: T): Unique =
      if idMap.containsKey(t) then idMap.get(t)
      else
        val u = nextUnique()
        idMap.put(t, u)
        val fu = mu.recurse(t)(convert(_))
        edges.addOne(u -> fu)
        u

    val u = convert(t)
    Graph(u, edges.result())

enum InfList[A]:
  case Cons(head: A, tail: () => InfList[A])

  def toLazyList: LazyList[A] =
    this match
      case Cons(head, tail) =>
        LazyList.cons(head, tail().toLazyList)

enum InfListF[A, U]:
  case Cons(head: A, tail: U)

given [A]: MuRef[InfList[A]] with
  type F[U] = InfListF[A, U]

  def recurse[U](t: InfList[A])(f: InfList[A] => U): InfListF[A, U] =
    t match
      case InfList.Cons(head, tail) =>
        InfListF.Cons(head, f(tail()))
  
given [A]: NuRef[InfList[A]] with
  type F[U] = InfListF[A, U]

  def recons[U](fu: InfListF[A, U])(f: U => InfListF[A, U]): InfList[A] =
    fu match
      case InfListF.Cons(head, tail) =>
        InfList.Cons(head, () => recons(f(tail))(f))

@main
def main(): Unit =
  val list =
    var ref: InfList[Int] = null
    ref = InfList.Cons(100, () => InfList.Cons(200, () => ref))
    ref
  val graph = Graph.from(list)
  println(graph)
  //=> Graph(0,Map(1 -> Cons(200,0), 0 -> Cons(100,1)))
  println(graph.to[InfList[Int]].toLazyList.take(10).toList)
  //=> List(100, 200, 100, 200, 100, 200, 100, 200, 100, 200)