[Haskell-cafe] Troubles understanding memoization in SOE
isaacdupree at charter.net
Wed Sep 26 16:41:20 EDT 2007
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.
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.
More information about the Haskell-Cafe