fix_point_bottom_up_and_top_down.scala

  sealed trait Tree
  case class Bin(x: Tree, y: Tree) extends Tree
  case class Lt(in: Int)           extends Tree


  /**
   * Infinite recursion - duplicate all binary values
   */
  def topddown_duplicate_bins(tree: Tree): Tree = tree match {
    case Bin(x, y) =>
      Bin(Bin(topddown_duplicate_bins(tree), topddown_duplicate_bins(tree)), Bin(topddown_duplicate_bins(x), topddown_duplicate_bins(y)))
    case Lt(in)    => Lt(in)
  }

  /**
   * Finite recursions: duplicate all binary values
   */
  def bottomup_duplicate_bins(tree: Tree): Tree = tree match {
    case Bin(Lt(x), Lt(y)) => Bin(Bin(Lt(x), Lt(y)), Bin(Lt(x), Lt(y)))
    case Bin(x, y)         =>
      val result = Bin(bottomup_duplicate_bins(x), bottomup_duplicate_bins(y))
      Bin(result, result)
    case Lt(in)            => Lt(in)
  }

  println(topddown_duplicate_bins(Bin(Bin(Lf(1), Lf(2)), Bin(Lf(3), Lf(4))))) // Infinite recursion
  println(bottomup_duplicate_bins(Bin(Bin(Lf(1), Lf(2)), Bin(Lf(3), Lf(4))))) // Finite recursion
  // res: Bin(Bin(
  //      Bin(Bin(Lt(1),Lt(2)),Bin(Lt(1),Lt(2))),
  //      Bin(Bin(Lt(3),Lt(4)),Bin(Lt(3),Lt(4)))),
  //      Bin(Bin(Bin(Lt(1),Lt(2)),Bin(Lt(1),Lt(2))),
  //      Bin(Bin(Lt(3),Lt(4)),Bin(Lt(3),Lt(4)))))

  /**
    * Approach using Fix
    */
  sealed trait TreeF[A]
  case class LeafF[A](value: Int)   extends TreeF[A]
  case class BinaryF[A](l: A, r: A) extends TreeF[A]


  final case class Fix[F[_]](unfix: F[Fix[F]])

  type Tree = Fix[TreeF]

  /**
    * A single bottom up logic for a functor F, wrapped in Fix.
    */
  def bottomUp[F[_]](f: Fix[F] => Fix[F])(implicit F: Functor[F]): Fix[F] => Fix[F] =
    fix => f(Fix(F.map(fix.unfix)(bottomUp(f))))

  /**
    * A single top down logic for a functor F, wrapped in Fix.
    */
  def topDown[F[_]](f: Fix[F] => Fix[F])(implicit F: Functor[F]): Fix[F] => Fix[F] =
    fix => Fix(F.map(f(fix).unfix)(topDown(f)))


  /**
    * One single duplicate logic
    */
  def duplicate: Tree => Tree = {
    case Fix(BinaryF(first, second)) => Fix(BinaryF(Fix(BinaryF(first, second)), Fix(BinaryF(first, second))))
    case other                       => other
  }

  // Example
  val binary: Tree = Fix(BinaryF(Fix(BinaryF(Fix(LeafF(1)), Fix(LeafF(2)))), Fix(BinaryF(Fix(LeafF(3)), Fix(LeafF(4))))))

  // Finite recursion coz bottomUp has to be finite as shown above
  println(bottomUp(duplicate)(ExprFIsFunctor)(binary))
  // Fix(BinaryF(Fix(BinaryF(Fix(BinaryF(Fix(BinaryF(
  // Fix(LeafF(1)),Fix(LeafF(2)))),
  // Fix(BinaryF(Fix(LeafF(1)),Fix(LeafF(2)))))),
  // Fix(BinaryF(Fix(BinaryF(Fix(LeafF(3)),Fix(LeafF(4)))),
  // Fix(BinaryF(Fix(LeafF(3)),Fix(LeafF(4)))))))),
  // Fix(BinaryF(Fix(BinaryF(Fix(BinaryF(Fix(LeafF(1)),Fix(LeafF(2)))),
  // Fix(BinaryF(Fix(LeafF(1)),Fix(LeafF(2)))))),
  // Fix(BinaryF(Fix(BinaryF(Fix(LeafF(3)),Fix(LeafF(4)))),
  // Fix(BinaryF(Fix(LeafF(3)),Fix(LeafF(4))))))))))

  println(topDown(duplicate)(ExprFIsFunctor)(binary)) 
  // Duplication on previous node which is already duplicated and it happens for ever