Peter Verswyvelen wrote:
Paul L wrote:
We recently wrote a paper about the leak problem. The draft is at http://www.cs.yale.edu/~hl293/download/leak.pdf. Comments are welcome! I'm trying to understand the following in this paper:
(A) repeat x = x : repeat x or, in lambdas: (B) repeat = λx → x : repeat x This requires O(n) space. But we can achieve O(1) space by writing instead: (C) repeat = λx → let xs = x : xs in xs
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. Also I believe (A) and (B) are the same as repeat = fix (\ f -> (\ x -> x : f x ) ) While (C) is repeat = \x -> fix (\ me -> x : me ) or repeat x = fix (\me -> x : me )
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. Any good tutorials on that one? Or is this the one http://haskell.org/haskellwiki/Recursive_function_theory. Looks a bit scary at first sight ;-)
Thanks again, Peter
A good way to think about 'fix' is that it lets us write a definition that talks about the thing that we are defining. This is very common in Haskell, since every recursive definition or mutually recursive set of definitions talks about itself. (Every Haskell let is a bit like Scheme's letrec). This is also common in C++ and Java when an object "talks about" itself while it is being constructed. Warning: It is easy for a programming mistake to create a dependency loop (or "black hole") when using 'fix' improperly. This is similar to a C++/Java object calling itself during construction when it is in only a partially constructed state and causing an error. Now take the definition from GHC's base package, currently in http://darcs.haskell.org/packages/base/Data/Function.hs
-- | @'fix' f@ is the least fixed point of the function @f@, -- i.e. the least defined @x@ such that @f x = x@. fix :: (a -> a) -> a fix f = let x = f x in x
Consider the type of fix, namely (a->a)->a. Note that is not the same as a->a->a which is actually a->(a->a). For (A) and (B) the type 'a' is the type of 'f' which is a function. If repeat :: q -> [q] then 'a' is 'q->[q]' and the fix is of type ( (q->[q]) -> (q->[q]) ) -> (q->[q]) For (C) the type 'a' is the type of 'me' which is a list, and the fix is of type ( [q] -> [q] ) -> [q] Expand (C) step by step: -- Rename x to be q to avoid name collisions repeat = \q -> fix (\me -> q : me ) -- Now substitute the definition of fix using f = (\me -> q : me) repeat = \q -> let x = (\me -> q : me) x in x -- Apply the function with me replaced by x repeat = \q -> let x = q : x in x Optionally convert to pointful notation repeat q = let x = q : x in x And these are your definition (C) Expand (A) or (B) step by step: Rename x to q to avoid name collision later repeat = fix (\ f -> (\ q -> q : f q ) ) Expand definition of fix replacing f with (\ f -> (\ q -> q : f q ) ) repeat = let x = (\ f -> (\ q -> q : f q ) ) x in x Apply the function replacing f with x repeat = let x = (\ q -> q : x q ) ) in x Simplify by noting that 'x' and 'repeat' name the same thing repeat = (\q -> q : repeat q) Optionally convert to pointful notation repeat q = q : repeat q -- Chris