[Tutor] Cannot Understand

[Pawel Kraszewski]

Dnia piątek, 10 marca 2006 19:31, Edgar Antonio Rodriguez Velazco napisał:

> f = lambda n: n-1 + abs(n-1) and f(n-1)*n or 1

Oh God! This smells lispish! Haven't seen a jevel like this before, but I LOVE 
it!


-----------------------------------------
First, let's cut that into pieces:

R1     n-1 + abs(n-1) 

 This is a funny way to test if n>1. Indeed, for n>1 it works as 2*n-2 
(especially, it is non-zero), for n<=1 it gives a constant 0

R2     f(n-1)*n

 It is a formula for you-know-what

R3     1

 Well... This is a ONE, you know.

-----------------------------------------
Then, few notes on 'and' and 'or' operators. For correctness of many 
algorithms, programmers introduced 'partial evaluation'. What does it mean?

L1     A and B

When A is FALSE, no matter what the B is, the whole result is FALSE. 
Therefore, we DON'T NEED to evaluate B. When A is TRUE, the result is yet 
unknown and we must evaluate B

L2     A or B

When A is TRUE, no matter what the B is, the whole result is TRUE. Therefore, 
we DON'T NEED to evaluate B. When A is FALSE, the result is yet unknown and 
we must evaluate B

L3     'and' has higher priority than 'or'

-----------------------------------------
Putting things together:

f = lambda n: n-1 + abs(n-1) and f(n-1)*n or 1

which may be rewritten due to law L3 as

     (R1 and R2) or R3

 First check is R1
 
 If R1==false (it means n<=1), then whole brace is automaticaly false due to 
law L1. Moreover, due to the same law, R2 is NOT calculated. We now have the 
value of brace, which is FALSE. We now have "FALSE or R3", so due to law L2 
we now must evaluate R3 to get the final (lambda) result. The total result is 
value of R3, this means 1.

 If R1==true (it means n>1), due to law L1 we must evaluate R2 to get the 
brace result. This is done by recursively calling lambda function with 
argument "n-1". Let's call the returned value a RES. When RES is non-zero (it 
actualy always is, due function it implements) we have non-zero result of the 
whole brace. due to law L2, we don't need to evaluate R3 and calculated 
result RES is the return value of lambda function.


-- 
 Pawel Kraszewski

P.S.

This might be pythonized and de-recursived this way:

 ff = lambda n: reduce(lambda x, y: x*y, xrange(1,n+1))

-----------------------------------------
Spoiler below... Scroll down





































Of course, as a last resort this may be rewritten in "plan english" as:

def f(n):
	if n>1:
		return n*f(n-1)
	else:
		return 1