[Haskell-cafe] Criteria for determining if a recursive function can be implemented in constant memory

[Steffen Schuldenzucker]

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
> <sschuldenzucker at uni-bonn.de <mailto:sschuldenzucker at 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 <ok at cs.otago.ac.nz <mailto:ok at cs.otago.ac.nz>>
>> To: 	Steffen Schuldenzucker <sschuldenzucker at uni-bonn.de
>> <mailto:sschuldenzucker at 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 at haskell.org <mailto:Haskell-Cafe at haskell.org>
>> http://www.haskell.org/mailman/listinfo/haskell-cafe