Paramorphism

A catamorphism replaces each constructor of a data structure with a function, and that function sees only the results already computed for the substructures. Some functions also need the substructures. A paramorphism passes both^[1].

On lists a paramorphism has the type

where the step function receives the head, the original tail, and the result for the tail. On natural numbers, where the step receives $n$ together with the result for $n$, it is exactly primitive recursion^[1][5].

(* A paramorphism on lists: the step sees the head, the rest of the
   original list, and the result computed for that rest. *)
let rec para f z = function
  | [] -> z
  | x :: xs -> f x xs (para f z xs)
 
(* The same on natural numbers: the step sees n as well as the result for n. *)
let rec para_nat f z n = if n = 0 then z else f (n - 1) (para_nat f z (n - 1))
 
let factorial = para_nat (fun n acc -> (n + 1) * acc) 1
 
(* All suffixes: each step needs the original tail, not just a result. *)
let tails l = para (fun x xs acc -> (x :: xs) :: acc) [ [] ] l
 
(* Insert into a sorted list, keeping the untouched tail as it is. *)
let insert y = para (fun x xs acc -> if y <= x then y :: x :: xs else x :: acc) [ y ]
 
(* Any paramorphism is a fold that rebuilds the list alongside its result. *)
let para_via_fold f z l =
  snd (List.fold_right (fun x (xs, acc) -> (x :: xs, f x xs acc)) l ([], z))
 
let show l = "[" ^ String.concat "; " (List.map string_of_int l) ^ "]"

factorial 10 = 3628800
[1; 2; 3] [2; 3] [3] []
[1; 3; 4; 5; 7; 9]
tail [7; 9] shared: true
via fold: [1; 3; 4; 5; 7; 9]

Factorial uses the number $n$ as well as $n!$. tails cons'es each original tail onto the result. insert stops at the first element not smaller than the new one and returns the original tail unchanged, so the result shares [7; 9] with the input; a fold would have rebuilt it.

Every paramorphism can be written as a fold that returns a pair: the rebuilt substructure and the result. This is para_via_fold above, and it is how Meertens defined paramorphisms^[1]. The pair costs a copy of the structure, and the fold cannot stop early and share the rest. In the other direction, a catamorphism is a paramorphism that ignores the substructure argument.

For a general recursive type, the fixed point $\mu F$ of a functor $F$, the paramorphism takes an algebra on pairs:

The dual scheme, which can stop unfolding and return a whole substructure at once, is the apomorphism. Both belong to the family of recursion schemes catalogued by Meijer, Fokkinga and Paterson and unified by Hinze, Wu and Gibbons as adjoint folds^[2][3]. The Haskell recursion-schemes library provides para for any base functor^[4].

Primitive recursion on the natural numbers goes back to Dedekind and Skolem and was formalized by Kleene^[5]. Lambert Meertens introduced the name paramorphism and its general definition for recursive datatypes in 1992, following the catamorphisms and anamorphisms of Meijer, Fokkinga and Paterson^[1][2].

• CatamorphismA catamorphism is the generalization of fold from lists to any recursive data type: it replaces each constructor of a value with a function and combines the results bottom up. Formally it is the unique homomorphism from the initial algebra of a functor to any other algebra of that functor. Writing a recursive data type as the fixed point of a base functor lets a single cata function fold every such type, with the recursion written once and each computation reduced to an algebra that handles one layer.
• AnamorphismAn anamorphism is the generalization of unfold: it builds a value of a recursive data type from a seed, using a function (a coalgebra) that produces one layer of the structure together with new seeds for its recursive positions. It is the categorical dual of the catamorphism, the unique homomorphism from any coalgebra into the final coalgebra of a functor. Anamorphisms can produce infinite structures such as streams, and they are the way to write corecursive programs that are guaranteed to be productive.
• HylomorphismA function that unfolds a seed into a recursive structure and folds that structure into a result, written so the structure is never built: hylo f g = f . fmap (hylo f g) . g. The call tree of the recursion is the intermediate structure.

1. [1]L. Meertens, “Paramorphisms”, Formal Aspects of Computing 4 (1992).
2. [2]E. Meijer, M. Fokkinga, R. Paterson, “Functional programming with bananas, lenses, envelopes and barbed wire”, FPCA (1991).
3. [3]R. Hinze, N. Wu, J. Gibbons, “Unifying structured recursion schemes”, ICFP (2013).
4. [4]E. Kmett, the recursion-schemes package for Haskell, Data.Functor.Foldable.
5. [5]S. C. Kleene, Introduction to Metamathematics, §43, North-Holland (1952).

last updated 1 October 2026