Hum. You are right and I'm probably asking the wrong questions. My original question was when it was possible to eliminate stack frames. For example, in the 'f' function from my first post, we know that none of the variables x and y will be needed after the recursive call to f, so we can just re-use the current stack frame for it, preventing f from using "additional" space for the recursion. However, stack frames are an implementation detail and I thought "constant-space" was an abstraction of my idea. Looks like it was not. On 07/06/2010 04:07 PM, Lennart Augustsson wrote:

Are you limiting your data structures to numbers? In that case, only numbers of limited size, the answer is, of course, yes. You can implement any such function in constant space and time. Just make a lookup table.

Sent from my iPad

On Jul 6, 2010, at 6:37, Steffen Schuldenzucker mailto:sschuldenzucker@uni-bonn.de> wrote:

...

Forwarding this message to the list.

No, I didn't think about the size of integers. For now, let all numbers have some bounded size.

-------- Original Message -------- Subject: Re: [Haskell-cafe] Criteria for determining if a recursive function can be implemented in constant memory Date: Tue, 6 Jul 2010 13:25:57 +1200 From: Richard O'Keefe mailto:ok@cs.otago.ac.nz> To: Steffen Schuldenzucker mailto:sschuldenzucker@uni-bonn.de>

On Jul 6, 2010, at 12:23 AM, Steffen Schuldenzucker wrote:

...

Given the definition of a recursive function f in, say, haskell, determine if f can be implemented in O(1) memory.

How are you supposed to handle integer arithmetic?

If you don't take the size of integers into account, then since a Turing machine can do any computation, it can run a Haskell interpreter, and since a Turing machine's tape can be modelled by a single integer (or more conveniently by two), any Haskell function can be implemented in O(1) Integers.

If you do take the size of integers into account, then pow2 n = loop n 1 where loop 0 a = a loop (m+1) a = loop m (a+a) requires O(n) memory. _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org mailto:Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe