fold_catamorphism.scala

/*** Setting up the abstract data type (ADT) / algebra for a linked list ***/
sealed trait List[+A]
case object Nil extends List[Nothing]
case class Cons[+A](head: A, tail: List[A]) extends List[A] 


/*** Defining `fold` which is a catamorphism ***/
// Catamorphism is essentially a reducing traversal of the data 
// using pattern matching?
def fold[A,B](nil: => B)(cons: (A, B) => B)(list: List[A]): B = list match {
  case Cons(a, tail) => cons(a, fold(nil)(cons)(tail))
  case Nil => nil
}


/*** Catamorphism identity ***/
// Catamorphisms has an identity function when passing in the type constructors
def listIdentity[A](list: List[A]): List[A] = {
  val nilTypeConstructor = Nil:List[A]
  val consTypeConstructor = Cons[A](_, _)

  fold(nilTypeConstructor)(consTypeConstructor)(list)
}
  
val list = Cons(1, Cons(2, Cons(3, Nil)))
listIdentity(list) // Cons(1, Cons(2, Cons(3, Nil)))

/*** Catamorphism => identity ***/
// Catamorphisms allows you to implement the visitor pattern

// Example 1: Printing the list
def printList[A](list: List[A]): Unit = {
  def whenNil = print("Nil ")
  def whenCons = (a: A, b: Unit) => print(a + " ")

  fold(whenNil)(whenCons)(list)
}

printList(list) // Nil 3 2 1

// Example 2: Summing Ints
def sumInts(list: List[Int]): Int = {
  def whenNil = 0
  def whenCons = (a: Int, b: Int) => a + b

  fold(whenNil)(whenCons)(list)
}

sumInts(list) // 6

// Example 3: Converting Int to Double
def listIntToDouble(list: List[Int]): List[Double] = {
  def whenNil = Nil:List[Double]
  def whenCons = (head: Int, tail: List[Double]) => Cons(head.toDouble, tail)

  fold(whenNil)(whenCons)(list)  
}

listIntToDouble(list) // Cons(1.0,Cons(2.0,Cons(3.0,Nil)))