Recursive Data Structures and Algorithms

// Binary Search Tree
enum BST[+A]:
  case Empty
  case Node(value: A, left: BST[A], right: BST[A])

object BST:
  def insert[A: Ordering](tree: BST[A], value: A): BST[A] =
    val ord = summon[Ordering[A]]
    tree match
      case Empty => Node(value, Empty, Empty)
      case Node(v, l, r) =>
        if ord.lt(value, v) then Node(v, insert(l, value), r)
        else if ord.gt(value, v) then Node(v, l, insert(r, value))
        else tree  // duplicate

  def contains[A: Ordering](tree: BST[A], value: A): Boolean =
    val ord = summon[Ordering[A]]
    tree match
      case Empty => false
      case Node(v, l, r) =>
        if ord.equiv(value, v) then true
        else if ord.lt(value, v) then contains(l, value)
        else contains(r, value)

  def inOrder[A](tree: BST[A]): List[A] = tree match
    case Empty => Nil
    case Node(v, l, r) => inOrder(l) ++ List(v) ++ inOrder(r)

  def depth[A](tree: BST[A]): Int = tree match
    case Empty => 0
    case Node(_, l, r) => 1 + Math.max(depth(l), depth(r))

  def size[A](tree: BST[A]): Int = tree match
    case Empty => 0
    case Node(_, l, r) => 1 + size(l) + size(r)

  def fromList[A: Ordering](items: List[A]): BST[A] =
    items.foldLeft[BST[A]](Empty)(insert)

// Linked List
enum MyList[+A]:
  case Nil
  case Cons(head: A, tail: MyList[A])

object MyList:
  def apply[A](items: A*): MyList[A] =
    items.foldRight[MyList[A]](Nil)(Cons.apply)

  extension [A](list: MyList[A])
    def map[B](f: A => B): MyList[B] = list match
      case Nil => Nil
      case Cons(h, t) => Cons(f(h), t.map(f))

    def filter(p: A => Boolean): MyList[A] = list match
      case Nil => Nil
      case Cons(h, t) =>
        if p(h) then Cons(h, t.filter(p))
        else t.filter(p)

    def foldLeft[B](init: B)(f: (B, A) => B): B = list match
      case Nil => init
      case Cons(h, t) => t.foldLeft(f(init, h))(f)

    def toList: List[A] = list.foldLeft(List.empty[A])((acc, a) => acc :+ a)

    def reverse: MyList[A] =
      list.foldLeft[MyList[A]](Nil)((acc, a) => Cons(a, acc))

@main def run(): Unit =
  import BST.*

  // Build BST
  val tree = fromList(List(5, 3, 7, 1, 4, 6, 8, 2))
  println(s"In-order: ${inOrder(tree)}")
  println(s"Contains 4: ${contains(tree, 4)}")
  println(s"Contains 9: ${contains(tree, 9)}")
  println(s"Depth: ${depth(tree)}")
  println(s"Size: ${size(tree)}")

  // Custom list
  val myList = MyList(1, 2, 3, 4, 5)
  println(s"Original: ${myList.toList}")
  println(s"Mapped: ${myList.map(_ * 2).toList}")
  println(s"Filtered: ${myList.filter(_ > 2).toList}")
  println(s"Sum: ${myList.foldLeft(0)(_ + _)}")
  println(s"Reversed: ${myList.reverse.toList}")