On Thu, Sep 19, 2013 at 2:31 AM, Brent Yorgey
The distinction is simply this: given a definition
foo = ...
does foo show up in the ..., i.e. on the right-hand-side of its own definition, or not? If foo shows up in its own definition, it is recursive. If not, it is not recursive.
This isn't a satisfactory answer 'simply' (there's that word again!) because it makes a hash out of equational reasoning: fix f = f (fix f) -- recursive fix2 = fix -- no longer recursive! thereby making the very concept itself ontologically suspect. Which of course, it shouldn't be. The stackoverflow question asks about 'representation', which, for the purpose of discussion, posits an actual graph-reduction machine. The current answers give GHC Core in gory detail. If that works for you, great! Otherwise, I recommend the self-guided tutorial on graph reduction in PJ & Lester: http://research.microsoft.com/en-us/um/people/simonpj/papers/pj-lester-book/ -- Kim-Ee