[Haskell-cafe] Troubles understanding memoization in SOE

[Isaac Dupree]

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