Lists defined using foldRight

flist.scala

/* A functional type of list
   that is exactly the type of foldRight */
type FList[+A] = [R] => (_nil: R, _cons: (A,R) => R) => R

// The empty list defined as its foldRight
def nil[A]: FList[A] =
  [R] => (_nil: R, _cons: (A,R) => R) => _nil

// The cons constructor defined also as its foldRight
def cons[A](head: A, tail: FList[A]): FList[A] =
  [R] => (_nil: R, _cons: (A,R) => R) =>
    val foldedTail: R = tail[R](_nil, _cons)
    _cons(head, foldedTail)

extension [A](self: FList[A])
  /* Structural equality between these lists
     It is equalivalent to defining equality using foldRight */
  def ===(other: FList[A]): Boolean =
    type Predicate = FList[A] => Boolean

    // Tests if a list is empty
    val eqNil: Predicate =
      (l: FList[A]) => l(true, (_,_) => false)

    // Test is a list is a cons made of this head and "tail"
    val eqCons: (A, Predicate) => Predicate =
      (head: A, tailEqualityPredicate: Predicate) =>
        (l: FList[A]) =>
          /* Scala pair type could be used but it is even nicer to show that
             equality on these lists can be defined with no (case) classes at all,
             just functions! */
          type FPair[+A,+B] = [R] => (A => B => R) => R

          def pair[A,B](a:A, b:B): FPair[A,B] =
            [R] => (f:A => B => R) => f(a)(b)

          def fst[A,B](p: FPair[A, B]): A =
            p[A]((a:A) => _ => a)

          def snd[A,B](p: FPair[A, B]): B =
            p[B](_ => (b:B) => b)

          /* To use the tailEqualityPredicate we need the tail of the list,
             So I reconstruct it "using foldRight" */
          val consCase =
            (hd: A, p: FPair[Boolean, FList[A]]) =>
              val tl = snd(p)
              val b = hd == head && tailEqualityPredicate(tl)
              val t = cons[A](hd, tl)
              pair(b,t)

          fst:
            l(pair(false, nil), consCase)

    // Magic!
    self(eqNil, eqCons)(other)

  // Of course this type of list is equalivalent to the usual one (FList -> List side)
  def toList: List[A] =
    self[List[A]](Nil, _ :: _)

extension [A](self: List[A])
  // Of course this type of list is equalivalent to the usual one (FList <- List side)
  def toFList: FList[A] =
    self match
      case Nil => nil[A]
      case hd :: tl => cons[A](hd, tl.toFList)

def test[A](l1: List[A], l2: List[A]): Unit =
  if ! (l1.toFList === l2.toFList)
  then throw new Exception(s"${l1} != ${l2}")

@main def hello: Unit =
  val r = new java.util.Random
  for
    i <- 1 to 1000
  do
    val l = List.fill(r.nextInt(1000))(r.nextInt())
    test(l,l)
  println("OK")