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
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
