title: What are paramorphisms?
body: <p>Reading through <a href="http://www.google.com/search?q=functional+programming+with+bananas+lenses+envelopes+and+barbed+wire&amp;ie=utf-8&amp;oe=utf-8&amp;aq=t&amp;rls=org.mozilla:en-US:official&amp;client=firefox-a" rel="noreferrer">this classic paper</a>, I'm stuck on paramorphisms.  Unfortunately the section is quite thin, and the Wikipedia page doesn't say anything.</p>
  
  <p>My Haskell translation is:</p>
  
  <pre><code>para :: (a -&gt; [a] -&gt; b -&gt; b) -&gt; b -&gt; [a] -&gt; b
  para f base = h
    where
      h []       =   base
      h (x:xs)   =   f x xs (h xs)
  </code></pre>
  
  <p>But I don't grok that -- I don't have any intuition for the type signature or the desired result.</p>
  
  <p>What's a paramorphism, and what are some useful examples in action?</p>
  
  <hr>
  
  <p>Yes, I've seen <a href="https://stackoverflow.com/questions/6941904/recursion-schemes-for-dummies">these</a> <a href="https://stackoverflow.com/questions/921972/what-are-zygo-meta-histo-para-futu-dyna-whatever-morphisms">questions</a>, but they don't cover paramorphisms directly and only point to <a href="http://comonad.com/reader/2009/recursion-schemes/" rel="noreferrer">resources</a> that may be helpful as references, but not as learning materials.</p>