--------------207CE5A72BAA0F320CA902DD
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
I am just beginning to delve into the graph-rewriting operational
semantics of Clean, and I would like to have some explanations about the
following :
How is it that :
module fib
import StdEnv
fibonaci = [ 1,2:zipWith (+) fibonaci ( tl fibonaci ) ]
where
zipWith o xl yl = zipWitho xl yl
where
zipWitho [x:xl] [y:yl] = [o x y:zipWitho xl yl ]
zipWitho [] [] = []
Start = fibonaci
seems to be running in exponential space and time, while :
module fib
import StdEnv
fibonaci = [ 1,2:rest fibonaci ]
where
rest f = zipWith (+) f ( tail f )
zipWith o xl yl = zipWitho xl yl
where
zipWitho [x:xl] [y:yl] = [o x y:zipWitho xl yl ]
zipWitho [] [] = []
Start = fibonaci
seems to be running in linear time and space ?
This is of some concern to me because the first program is running in
linear time under the Haskell interpreter Hugs98 without any problem.
Does that mean that some more knowledge of the operational semantics of
Clean is needed than it is for Haskell interpreters/compilers ?
Thanks
--------------207CE5A72BAA0F320CA902DD
Content-Type: text/html; charset=us-ascii
Content-Transfer-Encoding: 7bit
I am just beginning to delve into the graph-rewriting operational semantics
of Clean, and I would like to have some explanations about the following
:
import StdEnv
fibonaci = [ 1,2:zipWith (+) fibonaci ( tl fibonaci ) ]
where
zipWith o xl yl = zipWitho xl yl
where
zipWitho [x:xl]
[y:yl] = [o x y:zipWitho xl yl ]
zipWitho []
[] = []
Start = fibonaci
import StdEnv
fibonaci = [ 1,2:rest fibonaci ]
where
rest f = zipWith (+) f ( tail f )
zipWith o xl yl = zipWitho xl yl
where
zipWitho [x:xl]
[y:yl] = [o x y:zipWitho xl yl ]
zipWitho []
[] = []
Start = fibonaci
Thanks