Catamorphism in 2 minutes

A Catamorphism (κατά "downwards" and μορφή "form, shape") on a type T is a function of type T → U that destruct and object of type T according to the structure of T, calls itself recursively of any components of T that are also of type T and combines this recursive result with the remaining components of T to a U.

And it's just an official name of fold/reduce on higher kinded types. 

For example getting the prod from list of integers is Catamorphism on the list:

	def prod(list: List[Int]): Int = list match {
	case Nil => 1
	case head :: tail => head * prod(tail)
	}

view raw cata.scala hosted with ❤ by GitHub

Catamorphism in programming can be used to fold complex structures (lists, tress, sets)  into their representation via different type. As an example list catamorphism can be described as

	type ListCatamorphism[T, U] = List[T] => U
	def listCatamorphism[T, U](value: U, func: (T, U) => U): ListCatamorphism[T, U] = {
	def cata(list: List[T]): U = {
	list match {
	case Nil => value
	case head :: tail => func(head, cata(tail))
	}
	}
	cata
	}

view raw listCata.scala hosted with ❤ by GitHub

And if we want to fold the list into prod from elements we would use:

def prod: List[Int] => Int = listCatamorphism[Int, Int](1, _ * _)

view raw prod.scala hosted with ❤ by GitHub