Catamorfismo

Del griego kata- (hacia abajo, contra, o proceso de degradación) + morphē (forma) + el sufijo -ismo (actividad o doctrina).

Un catamorfismo consiste en la compresión de tipo inductivo en un valor de otro tipo.
Podemos representarlo en forma de cuadrado para mostrar el funtor generador de ambos tipos y el catamorfismo \(f\) entre ellos.

1
2
3
4
5
6

          in
 L.A <────────── F.L.A
  │                │
f │                │ F.f
  ↓       ρ        ↓ 
  B  <────────── F.B

\(\rho\) determina de forma única como será el catamorfismo \(f\), así, se denota \(f = (|\rho|)\).
Este cuadrado debe cumplir la propiedad de que ir por cualquiera de sus dos direcciones desde \(F.A\) hasta \(B\) es equivalente. Así, la cata-caracterización es definir exactamente esto:
\(f\circ in = \rho \circ F.f\)
\(\rho\) representa la aplicación de la función recursiva en un único elemento. La recursividad total a la que equivale \(f\) viene de que \(F.f\) viene definido en función del propio \(f\).

El resultado de un catamorfismo "traduce" la estructura constructora del elemento original para crear un nuevo elemento. Por ejemplo:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

  Estructura Original          Catamorfismo (Álgebra)
  del Natural '3'              (+1) ➔ (x :)
                                0   ➔ [ ]

      (+1)                       (x :)
       │                           │
      (+1)       ────────►       (x :)
       │                           │
      (+1)                       (x :)
       │                           │
       0                          [ ]