title: Are haskell data types co-algebras by default?
body: <p>I'm trying to get my head around F-algebras, and <a href="https://www.fpcomplete.com/user/bartosz/understanding-algebras" rel="noreferrer">this article</a> does a pretty good job. I understand the notion of a dual in category theory, but I'm having a hard time understanding how F-coalgebras (the dual of F-algebras) relate to lazy data structures in Haskell. </p>
  
  <p>F-algebras are described with an endofunctor with the function: F a -> a, which makes sense if you think of F a as an expression, and a as the result of evaluating that expression, as the linked article explains it. </p>
  
  <p>Being the dual of F-algebras, the corresponding function for a F-coalgebra would be a -> F a. <a href="http://en.wikipedia.org/wiki/F-coalgebra" rel="noreferrer">Wikipedia</a> says that F-coalgebras can be used to create infinite, lazy data structures. How does the a -> F a functon allow one to create infinite, lazy data structures? Also, with that in mind, since Haskell is at it's core lazy, are most data-types in Haskell F-coalgebras instead of F-algebras? Are F-algebras not lazily evaluated? </p>
  
  <p>If data types (or at least the ones that <em>are</em> capable of infinite data) are based on F-coalgebras in Haskell, what is the a -> F a function for lists, for example? What is the terminal F-coalgebra for lists?</p>
  
  <p>Making an infinite list [1,2,3,4...] might look like this in Haskell:</p>
  
  <pre><code>list = 1 : map (+ 1) list
  </code></pre>
  
  <p>Does this use F-coalgebras somehow? Do infinite data structures require a notion of lazy evaluation and recursion alongside the use of F-coalgebras? Am I missing something here? </p>