# I'm off to the Oregon Shakespeare Festival for the weekend so no
# time to finish my Untangling series. But I do have time to post this...
# The other day someone asked me if it was possible to implement a
# certain task in one line of Python. My response was "yes, but you
# wouldn't want to." You can think of what follows as the demonstration
# that you really don't want to.
# The problem is, there are lots of Python constructions you can't
# do on one line: assigning variables, defining functions, using
# conditionals, recursion and so on. So it appears there's a limit
# to what you can do. Amazingly, all of these problems can be solved
# with the use of lambdas.
# One place you often want one line lambdas is in the use of the map
# function. So let's stick with that as an example and warm up with
# an easy example. Lets say we want to add 1 to all of the numbers
# from 0 to 19. We can write:
def inc(n):
return n+1
print "1.",map(inc,range(0,20))
# Lambdas enable you to write that as a oneliner:
print "1.",map(lambda x:x+1,range(0,20))
# Now what happens if we want to apply a function that uses a local
# (constant) variable. For example:
def f1(n):
m = 2*n+1
return m+m*m
print "2.",map(f1,range(0,20))
# We can eliminate the assigment by means of a function. m changes from
# being a local to a function argument:
def f2(n):
def g(m):
return m+m*m
return g(2*n+1)
print "2.",map(f2,range(0,20))
# But that seems to make things worse because now we have a function
# definition instead of a variable assigment. But we can eliminate
# that with a lambda:
def f3(n):
return (lambda m:m+m*m)(2*n+1)
print "2.",map(f3,range(0,20))
# And now we can write the whole thing as one big lambda:
print "2.",map(lambda n:(lambda m:m+m*m)(2*n+1),range(0,20))
# But what happens if we want to define a bunch of local functions
# inside our lambda? We can use the same technique. We (1) use
# lambdas to allow us to fake local variable definitions and
# (2) use lambdas to define the functions. So we can replace this:
def f(n):
def g(n):
return 2*n+1
def h(n):
return 3*n2
return g(h(g(h(n))))
print "3.",map(f,range(0,20))
# with this:
print "3.",map(lambda n:(lambda g,h,n:g(h(g(h(n)))))(lambda n:2*n+1,lambda n:3*n2,n),range(0,20))
# We're passing in lambdas as arguments to a lambda so that they
# get bound to g and h.
# But what happens if we want a recursive definition like:
def fact(n):
if n<=1:
return 1
else:
return n*fact(n1)
print "4.",map(fact,range(0,20))
# Because the function is bound to the name fact, we can refer to
# fact by name inside the defintion of fact. How can we do this in
# a oneline lambda? We can start by eliminating the selfreference
# in a fairly standard way. First rewrite fact so it doesn't call
# itself, but calls a function passed in as an argument:
def urfact(f,n):
if n<=1:
return 1
else:
return n*f(f,n1)
# We can then make a factorial function by calling urfact with itself,
# allowing it to carry out the recursion:
def fact1(n):
return urfact(urfact,n)
print "4.",map(fact1,range(0,20))
# We can use urfact directly without fact1:
print "4.",map(lambda n:urfact(urfact,n),range(0,20))
# Now all we need is a oneliner definition of urfact. It's tempting to try:
def urfact1(f,n):
return {True:1,False:n*f(f,n1)}[n<=1]
# But that results in nontermination because it evaluates *both* branches
# of the conditional. In a lazy language like Haskell, the branch not taken
# wouldn't be evaluated. But Python can be made lazy by using...you
# guessed it...lambda. The expression lambda:x is like a lazy version
# of the expression x. It doesn't get evaluated until you apply it as a
# function of no arguments, at which time it takes on the value x. So we
# can rewrite urfact as:
def urfact2(f,n):
return {True:lambda:1,False:lambda:n*f(f,n1)}[n<=1]()
# And we get
print "4.",map(lambda n:urfact2(urfact2,n),range(0,20))
# Note how we use urfact2 twice, so we need the trick above for local
# definitions to get it down to one reference:
print "4.",map(lambda n:(lambda f:f(f,n))(urfact2),range(0,20))
# And now we can replace urfact2 with a lambda
print "4.",map(lambda n:(lambda f:f(f,n))(lambda f,n:{True:lambda:1,False:lambda:n*f(f,n1)}[n<=1]()),range(0,20))
# And that's enough for now. I expect that if we keep going we'll find
# way to rewrite any Python program as a one liner. You could probably
# even write a program to automatically 'compile' a usable subset of
# Python into one liners.
# But you probably don't want to do that.
Friday, September 26, 2008
On writing Python oneliners.
Subscribe to:
Post Comments (Atom)
Blog Archive
Some Links
About Me

Dan Piponi
 Blog: A Neighborhood of InfinityCode: GithubTwitter: sigfpeHome page: www.sigfpe.com
24 comments:
this is bending my mind just reading it; nicely done
You *can* do conditionals in 1 line in Python:
if n<=1:
return 1
else:
return n*f(f,n1)
becomes
return 1 if n <= 1 else n*f(f,n1)
Have fun debugging! I'll stick with "normal" code thank you.
In the case of assigning lambdas to local variables you can also do:
print "3.",map(lambda n:(lambda n,g=(lambda n:2*n+1),h=(lambda n:3*n2):g(h(g(h(n)))))(n),range(0,20))
Also important to note is that people who would judge a programming language by the class of programs that can be written in one line in that language don't really deserve and answer to their question.
I won't be the only one to notice this, but you are basically transforming an iterative program into a functional one. Your final Python looks a lot like Lisp, except that a Lisp program wouldn't need to be on one line.
I won't be the only one to notice this, but you are basically transforming an iterative program into a functional one. Your final Python looks a lot like Lisp, except that a Lisp program wouldn't need to be on one line.
Great post!!
I didn't even know about that lambda thing! Very interesting, very interesting...
Don't you know about Python ternary operator ? It was introduced in Python 2.5...
(a if cond else b)
print "4.",map(lambda n:(lambda f:f(f,n))(lambda f,n:{True:lambda:1,False:lambda:n*f(f,n1)}[n<=1]()),range(0,20))
=
print "4.",map(lambda n:(lambda f:f(f,n))(lambda f,n:(1 if n<=1 else n*f(f,n1))),range(0,20))
hey, that's a pretty slick explanation of the Y combinator! honestly, i've never seen it developed so plainly.
Some of these can be written more cleanly using some of the newer features of Python. You don't need map anymore, you can use list comprehensions, so things like
print "1.",map(inc,range(0,20))
Can be
print "1.", [inc(x) for x in xrange(0, 20)]
(And xrange instead of range because it does not construct a list inplace, but just a constantmemory iterator). And you have a ternary operator now in 2.5, so
def urfact2(f,n):
return {True:lambda:1,False:lambda:n*f(f,n1)}[n<=1]()
Can be something like
urfact2 = lambda f, n: 1 if n <= 1 else n * f(x1)
Which evaluates lazily so you don't need the extra () to avoid blowing the stack or even an [] access to the inline dictionary.
But yes, interesting introduction to this type of functional gymnastics that Python does well.
Yes, but can you write the python script that compiles all other python scripts into one line of code in one line of code?
Clever, and very useful to think about from a pure CS standpoint, but from a getitdone engineering standpoint all this work wouldn't be necessary if python allowed braces to represent indent/outdent.
Reminds me of http://www.nishiohirokazu.org/blog/2006/09/how_to_write_oneliner_in_pytho.html
thanks for sharing
azrolboyz
print "4.",map(lambda n:(lambda f:f(f,n))(lambda f,n:{True:lambda:1,False:lambda:n*f(f,n1)}[n<=1]()),range(0,20))
You should try to write Perl one liners...
I expect that if we keep going we'll find way to rewrite any Python program as a one liner
More than expect, I think you know :)
In fact, it is possible to encode any Lambda Calculus term as a Python oneliner like this. Since we know Lambda Calculus is Turing complete  we thus know we can write any program (not just Python programs) as a Python oneliner.
But yes... you probably wouldn't want to do that :)
Stuart,
As you might guess, I'm not really a Python programmer, I just do it part time in my day job :)
I didn't know about the one line conditional syntax. But it was a good excuse to demonstrate how to achieve laziness with lambdas.
Hmm, you could write a one liner that compiles python apps into one liners.
But I guess you would write the app to make one liners first, then run it on it's self?
Speaking of meta, pypy is rad.
for sake of code readiness, I'd prefer more lines of code, or at least short one liner, rather than combined too many things in a quite long line.
thx for sharing
>> In fact, it is possible to encode any Lambda Calculus term as a Python oneliner like this. Since we know Lambda Calculus is Turing complete  we thus know we can write any program (not just Python programs) as a Python oneliner.
We can compute any computable function as a Python one liner.
To do interactive computation you need a bit more than lambda calculus.
self = (lambda f: (lambda *a,**k: f(f,*a,**k)))
fact1 = (lambda n: (lambda f,n: f(f,n)) (lambda f,n: n*f(f,n1) if n else 1, n))
fact2 = self(lambda f,n: n*f(f,n1) if n else 1)
Nice One......
A prime number sieve in nothing but lambdas:
import sys
(lambda y:lambda z:z(z(y(lambda p:lambda n:(lambda s:lambda z:z(lambda x:lambda
y:y)(lambda d:p(s)(y(s))(d)))(lambda x:lambda a:lambda s:lambda p:p(a)(lambda y
:s(n(x))(y))))(lambda c:lambda a:lambda s:z(lambda y:s(c)(y)))))(y(lambda p:
lambda b:lambda t:t(sys.stdout.write(b('.')('P'))or p))))(lambda f:(lambda q:q(
q))(lambda x:f(lambda y:x(x)(y))))(lambda s:lambda p:p(lambda x:lambda y:x)(s))
Post a Comment