Peter Verswyvelen wrote:
Let me see if I understand this correctly. Since I'm an imperative programmer, I'll try a bit of C++ here.
struct Cell : Value { Value* head; Value* tail; };
So in (A) and (B), a Cell c1 is allocated, and c1->head would be a pointer to x, and c1->tail would be a pointer to a newly allocated Cell c2, etc etc, hence O(n) space complexity In (C) however, a Cell xs is allocated, and xs->head is also a pointer to x, but xs->tail is a pointer the cell xs again, creating one circular data structure, hence O(1) space complexity.
Is this more or less correct?
yes.. I don't think you meant to both derive Cell from Value and have a "head" pointer. Otherwise it's an excellent analogy (ignoring how _unevaluated_ thunks are represented, because without those -- with strict list evaluation -- O(n) repeat has to be O(infinity) ).
I'm also trying to figure out how the "fixed point combinator" works, so the fix f = f (fix f), and it's effect on space/time complexity.
or fix f = let x = f x in x which may have different complexity properties? I don't know... Imagine inlining `fix`, if you have a better intuition for explicit (co)recursion than for `fix`. Oh wait, only my definition can be fully inlined, not yours. Isaac