title: Why do I need a list fold to actually deconstruct a tree with this tree catamorphism?
body: <p>A catamorphism can either deconstruct a value</p>
  <pre><code>[1,2,3].reduce((acc, x) =&gt; acc + x, 0); // 6
  </code></pre>
  <p>or maintain the structure and act like the identity of the underlying type:</p>
  <pre><code>[1,2,3].reduce((acc, x) =&gt; acc.concat([x]), []); // [1,2,3]
  </code></pre>
  <p>With lists (or arrays in JS) the catamorphism and the fold (of a foldable container) coincide.</p>
  <p>However, with trees they do not:</p>
  <p><div class="snippet" data-lang="js" data-hide="false" data-console="true" data-babel="false">
  <div class="snippet-code">
  <pre class="snippet-code-js lang-js prettyprint-override"><code>const treeCata = f =&gt; ([x, xs]) =&gt;
    f(x) (arrMap(treeCata(f)) (xs));
  
  const arrMap = f =&gt; xs =&gt;
    xs.map((x, i) =&gt; f(x, i));
  
  const arrFold = f =&gt; acc =&gt; xs =&gt;
    xs.reduce((acc, x) =&gt; f(acc) (x), acc);
  
  const log = x =&gt; (console.log(x), x);
  
  const Node = (x, xs) =&gt; ([x, xs]);
  const Node_ = x =&gt; xs =&gt; ([x, xs]);
  
  const tree = Node(1, [
    Node(2, [
      Node(3, []),
      Node(4, [])
    ]),
    Node(5, [])
  ]);
  
  const foo = treeCata(Node_) (tree);
  
  const bar = treeCata(x =&gt; xs =&gt; x + arrFold(y =&gt; z =&gt; y + z) (0) (xs)) (tree);
  
  log(foo);
  log(bar);</code></pre>
  </div>
  </div>
  </p>
  <p>The role as identity works as expected. The deconstruction, however, is a bit more involved. As a matter of fact I need a list fold to conduct it. I can actually see that there is one layer of deconstruction, because otherwise a list fold wouldn't be enough for a non-linear tree. But still having to use another fold seems odd.</p>
  <p>I can only guess that this behavior is related to the terse definition of the used catamorphism. It only takes a single case into account the product <code>Tree a = Node a [Tree a]</code>. Maybe it would be more promising if I'd fully embrace the algebraic structure of the type and distingiush <code>Node</code>/<code>Array</code> constructor and the empty array case.</p>
  <p>But does this mean <code>treeCata</code> is not a proper catamorphism? What is it lacking?</p>