title: Does each type have a unique catamorphism?
body: <p>Recently I've finally started to feel like I understand catamorphisms. I wrote some about them in <a href="https://stackoverflow.com/a/46555360/625403">a recent answer</a>, but briefly I would say a catamorphism for a type abstracts over the process of recursively traversing a value of that type, with the pattern matches on that type reified into one function for each constructor the type has. While I would welcome any corrections on this point or on the longer version in the answer of mine linked above, I think I have this more or less down and that is not the subject of this question, just some background.</p>
  
  <p>Once I realized that the functions you pass to a catamorphism correspond exactly to the type's constructors, and the arguments of those functions likewise correspond to the types of those constructors' fields, it all suddenly feels quite mechanical and I don't see where there is any wiggle room for alternate implementations.</p>
  
  <p>For example, I just made up this silly type, with no real concept of what its structure "means", and derived a catamorphism for it. I don't see any other way I could define a general-purpose fold over this type:</p>
  
  <pre><code>data X a b f = A Int b
               | B
               | C (f a) (X a b f)
               | D a
  
  xCata :: (Int -&gt; b -&gt; r)
        -&gt; r
        -&gt; (f a -&gt; r -&gt; r)
        -&gt; (a -&gt; r)
        -&gt; X a b f
        -&gt; r
  xCata a b c d v = case v of
    A i x -&gt; a i x
    B -&gt; b
    C f x -&gt; c f (xCata a b c d x)
    D x -&gt; d x
  </code></pre>
  
  <p>My question is, does every type have a unique catamorphism (up to argument reordering)? Or are there counterexamples: types for which no catamorphism can be defined, or types for which two distinct but equally reasonable catamorphisms exist? If there are no counterexamples (i.e., the catamorphism for a type is unique and trivially derivable), is it possible to get GHC to derive some sort of typeclass for me that does this drudgework automatically?</p>