[Haskell-cafe] Criteria for determining if a recursive function can
be implemented in constant memory
Steffen Schuldenzucker
sschuldenzucker at uni-bonn.de
Mon Jul 5 08:23:20 EDT 2010
Dear Cafe,
since a little discussion with my tutor I am wondering how the following
problem can be solved and if it is decidable:
Given the definition of a recursive function f in, say, haskell,
determine if f can be implemented in O(1) memory.
First I thought the solution would be "check if f is tail-recursive".
However, consider the following definition:
> -- for the sake of uniformity
> if' c t e = if c then t else e
>
> f :: (Num a) => a -> a -> a
> f x y = if' (x <= 0) y $
> if' (x >= 2) (f (x-2) (y+1)) (f (x-1) y)
(I don't really care what this function computes as long as it
terminates, which is obvious)
Although ghc will probably not perform this optimization, f can be
realized in O(1) mem:
// trying to duplicate f's structure as closely as possible
double f( double x, double y )
{
START:
if ( x <= 0 )
return y;
else
{
if ( x >= 2 )
{
x = x - 2;
y = y + 1;
goto START;
}
else
{
x = x - 1;
y = y;
goto START;
}
}
}
It is crucial that (the second) if' does not use both of its last two
arguments, but only one. If we replace the second if' by, say
> g :: (Num a) => c -> a -> a -> a
> g c t e = if' c (t + e) (t - e)
, then we have to compute *both* (f (x-2) (y+1)) and (f (x-1) y), and x
and y have to be kept in memory during the call to (f (x-2) (y+1)),
therefore f cannot be implemented in constant memory. (read: I haven't
found a way which does not radically alter f's structure).
So, does someone know how to solve this or can prove that it can't be
solved?
Best regards,
Steffen
More information about the Haskell-Cafe
mailing list