473,322 Members | 1,755 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,322 software developers and data experts.

list of polynomial functions

In the following program I am trying to learn how to use functional
programming aspects of python, but the following program will crash,
claiming that the recursion depth is too great. I am attempting to make
a list of polynomial functions such that poly[0](3) = 1, poly[1](3) =
3, poly[2](3) = 9, etc. Could someone point me in the right direction?
Thanks.

def make_polys(n):
"""Make a list of polynomial functions up to order n.
"""
p = lambda x: 1
polys = [p]

for i in range(n):
polys.append(lambda x: polys[i](x)*x)

return polys

# construct a vector of polynomials
polys = make_polys(5)

# print
for p in polys:
print p(3)

Jun 15 '06 #1
11 3893
In <11**********************@i40g2000cwc.googlegroups .com>, Josiah Manson
wrote:
def make_polys(n):
"""Make a list of polynomial functions up to order n.
"""
p = lambda x: 1
polys = [p]

for i in range(n):
polys.append(lambda x: polys[i](x)*x)


The `i` is the problem. It's not evaluated when the lambda *definition*
is executed but when the lambda function is called. And then `i` is
always == `n`. You have to explicitly bind it as default value in the
lambda definition:

polys.append(lambda x, i=i: polys[i](x)*x)

Then it works.

Ciao,
Marc 'BlackJack' Rintsch
Jun 15 '06 #2
> The `i` is the problem. It's not evaluated when the lambda
*definition* is executed but when the lambda function is
called. And then `i` is always == `n`. You have to
explicitly bind it as default value in the lambda definition:

polys.append(lambda x, i=i: polys[i](x)*x)

Then it works.


Just to sate my curiosity, why can the lambda find "polys", but
not find "i"? If what you're describing is the case, then it
seems to me that the following code should work too:

def make_polys(n):
p = lambda x: 1
polys = [p]
for i in range(n):
p = polys[i]
polys.append(lambda x: (p(x) * x))
return polys

yet it suffers the same problem as the original. Outside the
scope of make_polys, neither polys[] nor i exists.

There's some subtle behavior here that I'm missing.

-tkc


Jun 15 '06 #3
Tim Chase wrote:
The `i` is the problem. It's not evaluated when the lambda
*definition* is executed but when the lambda function is
called. And then `i` is always == `n`. You have to
explicitly bind it as default value in the lambda definition:

polys.append(lambda x, i=i: polys[i](x)*x)

Then it works.
Just to sate my curiosity, why can the lambda find "polys", but
not find "i"? If what you're describing is the case, then it
seems to me that the following code should work too:


it's not that it cannot find it, it's that if you use a closure, i will
have the same value for all lambdas.
There's some subtle behavior here that I'm missing.


lexical closures bind to names, default arguments bind to values.

</F>

Jun 15 '06 #4
Fredrik Lundh wrote:
Tim Chase wrote:
The `i` is the problem. It's not evaluated when the lambda
*definition* is executed but when the lambda function is
called. And then `i` is always == `n`. You have to
explicitly bind it as default value in the lambda definition:

polys.append(lambda x, i=i: polys[i](x)*x)

Then it works.


Just to sate my curiosity, why can the lambda find "polys", but not
find "i"? If what you're describing is the case, then it seems to me
that the following code should work too:


it's not that it cannot find it, it's that if you use a closure, i will
have the same value for all lambdas.
There's some subtle behavior here that I'm missing.


lexical closures bind to names, default arguments bind to values.


Just to be a bit more explicit:
In code like:
def make_polys(n):
"""Make a list of polynomial functions up to order n."""
p = lambda x: 1
polys = [p]
for i in range(n):
polys.append(lambda x: polys[i](x)*x)
i=3

The lambda-defined functions will be called after the for loop is done,
at which time the "i" (from the surrounding environment) will have a
value of 3. Hope this makes it a bit clearer.

--Scott David Daniels
sc***********@acm.org
Jun 15 '06 #5
> The `i` is the problem. It's not evaluated when the lambda *definition*
is executed but when the lambda function is called. And then `i` is
always == `n`. You have to explicitly bind it as default value in the
lambda definition:

polys.append(lambda x, i=i: polys[i](x)*x)


Thank you for your help.

Jun 15 '06 #6
> Just to be a bit more explicit:
In code like:
def make_polys(n):
"""Make a list of polynomial functions up to order n."""
p = lambda x: 1
polys = [p]
for i in range(n):
polys.append(lambda x: polys[i](x)*x)
i=3

The lambda-defined functions will be called after the for loop is done,
::boggle::

My understanding is that the lambda-defined functions are not
called until the actual application thereof, with the

mypolys = make_polys(8)
mypolys[5](2) #the lambda call happens here, no?

</F>'s original statement read like a koan...there was more in it
than I was getting out of it. There seem to be several concepts
I've not yet wrapped my head around. My understanding (likely
wrong) was that "lambda" was sort of like defining a function
inline, along the lines of

def f(x):
return x+5

being somewhat equiv to

k = lambda x: x+5

you could then do
f(20) 25 j = f
j(20) 25 k(20) 25 j = k
j(20) 25

There does seem to be some subtle difference, as
f <function f at 0xb7d87e9c> k <function <lambda> at 0xb7d8c0d4>

"k" clearly knows it's a <lambda> just as "f" knows its an "f"
(whether asked for by the aliased name or not).

So at some point, the Python interpreter is compiling this
function/lambda, and expanding matters with or without some sort
of scope. The OP's example seems to pull both "polys" and "i"
from the local scope. However, Python must only be tokenizing
and making references to future-ly available stuff, as, without
"spam", "blah", "tapioca", or "spatula" defined in my
environment, I can do arbitrary things like

q = lambda x: spam[spatula](x) + blah / tapioca

and Python swallows the whole lot as syntactically kosher, even
though none of these items exist. It seems to only evaluate them
at the point that "q" is called.

[lightbulb begins to go on...sorta]

However, in the OP's example, slightly modified, it seems that
polys, even when it doesn't exist in the calling scope, it
doesn't matter.
def mp(n): .... p = lambda x: 1
.... polys = [p]
.... for i in range(n):
.... polys.append(lambda x: polys[i](x)*x)
.... return polys
.... f = mp(5)
polys Traceback (most recent call last):
File "<stdin>", line 1, in ?
NameError: name 'polys' is not defined for p in f: print p(3)

....
1
Traceback (most recent call last):
File "<stdin>", line 1, in ?
File "<stdin>", line 5, in <lambda>
:
:
:

I'm curious why the very first attempt to call p(3) doesn't bomb
out with the NameError that "polys" wasn't defined before it even
got to the point of attempting to call it.
Hope this makes it a bit clearer.


like chocolate. :-/

Thanks for trying though...

-tkc (who is certainly *not* a LISP programmer, as evidenced here...)

Jun 15 '06 #7
I'm curious why the very first attempt to call p(3) doesn't bomb
out with the NameError that "polys" wasn't defined before it even
got to the point of attempting to call it.


In the first call, the 0th lambda function is evaluated, and it was
defined as the constant function 1. The functions after that each refer
to the previous polynomial, so they mess up. The first doesn't so it's
fine.

I'm new to this, as evidenced by my original posting, so I may be
missing something.

I hope I helped,
Josiah

Jun 16 '06 #8
In <ma***************************************@python. org>, Tim Chase
wrote:
My understanding is that the lambda-defined functions are not
called until the actual application thereof, with the

mypolys = make_polys(8)
mypolys[5](2) #the lambda call happens here, no?
Yes, that's right.
</F>'s original statement read like a koan...there was more in it
than I was getting out of it. There seem to be several concepts
I've not yet wrapped my head around. My understanding (likely
wrong) was that "lambda" was sort of like defining a function
inline, along the lines of

def f(x):
return x+5

being somewhat equiv to

k = lambda x: x+5

you could then do

>>> f(20)
25
>>> j = f
>>> j(20)
25
>>> k(20)
25
>>> j = k
>>> j(20)
25

There does seem to be some subtle difference, as

>>> f
<function f at 0xb7d87e9c>
>>> k
<function <lambda> at 0xb7d8c0d4>

"k" clearly knows it's a <lambda> just as "f" knows its an "f"
(whether asked for by the aliased name or not).
That understanding is mostly correct. Just that there's no subtile
difference. `k` doesn't know it's a lambda function, it's just an
ordinary function at this point which happens to have the name '<lambda>'.
That's somewhat unusual but it behaves like any ``def``-ed function.
[lightbulb begins to go on...sorta]

However, in the OP's example, slightly modified, it seems that
polys, even when it doesn't exist in the calling scope, it
doesn't matter.
>>> def mp(n): ... p = lambda x: 1
... polys = [p]
... for i in range(n):
... polys.append(lambda x: polys[i](x)*x)
... return polys
... >>> f = mp(5)
>>> polys Traceback (most recent call last):
File "<stdin>", line 1, in ?
NameError: name 'polys' is not defined >>> for p in f: print p(3)

...
1
Traceback (most recent call last):
File "<stdin>", line 1, in ?
File "<stdin>", line 5, in <lambda>
:
:
:

I'm curious why the very first attempt to call p(3) doesn't bomb
out with the NameError that "polys" wasn't defined before it even
got to the point of attempting to call it.


Well, because `polys` does not exist in the module scope. But it exists
in the local scope of the functions in `f`.

An example:

In [2]:def outer(a):
.2.: b = 42
.2.: def inner(c):
.2.: print a, b, c
.2.: print locals()
.2.:
.2.: return inner
.2.:

In [3]:f = outer(1)

In [4]:f(2)
1 42 2
{'a': 1, 'c': 2, 'b': 42}

If `outer` returns `inner` the inner function still has a reference to the
locals of the enclosing function. So they won't go away if the outer
function returns. `a` and `b` are looked up when `f` is called. That's a
problem if you create more than one function in `outer` and use a name
from outer's locals that changes:

In [7]:def pitfall():
.7.: functions = list()
.7.: for i in range(3):
.7.: functions.append(lambda: i)
.7.: print 'pitfall: i=%d' % i
.7.: return functions
.7.:

In [8]:for function in pitfall():
.8.: print function()
.8.:
pitfall: i=2
2
2
2

At the time the list with the functions is returned `i` is 2. So if you
call any of the functions it looks up this `i`.

Ciao,
Marc 'BlackJack' Rintsch
Jun 16 '06 #9
Josiah Manson wrote:
In the following program I am trying to learn how to use functional
programming aspects of python, but the following program will crash,
claiming that the recursion depth is too great. I am attempting to make
a list of polynomial functions such that poly[0](3) = 1, poly[1](3) =
3, poly[2](3) = 9, etc. Could someone point me in the right direction?
Thanks.

def make_polys(n):
"""Make a list of polynomial functions up to order n.
"""
p = lambda x: 1
polys = [p]

for i in range(n):
polys.append(lambda x: polys[i](x)*x)

return polys

# construct a vector of polynomials
polys = make_polys(5)

# print
for p in polys:
print p(3)


Many wise things have been said in this thread. I would like to proffer
another solution which does not rely on default arguments, just for a
more functional flavor.

def makepolys(n):
if n==0:
return [lambda x: 1]
else:
tailfunc=makepolys(n-1)
return tailfunc + [ lambda x: x * tailfunc[-1](x)]

Another way, which is properly tail recursive is the following:

def makepolys2helper(n,retval):
if n==0:
return retval
else:
return makepolys2helper(n-1,retval+[lambda x: x* retval[-1](x)])

def makepolys2(n):
return makepolys2helper(n,[lambda x: 1])

(Note: this could be collapsed into a single function either with a
default argument, or a nested function, but I thought this was a bit
clearer)

This last approach could, at least theoretically, create an arbitrarily
long list of polys, without overflowing any kind of stack. In practice,
python does not seem to perform tail recursion optimizations, and conks
out after makepolys(997) on my machine.

And yes - I did just sit in on my first functional programming class :)

-matt

Jun 20 '06 #10
In article <11**********************@i40g2000cwc.googlegroups .com>,
Matteo wrote:
This last approach could, at least theoretically, create an arbitrarily
long list of polys, without overflowing any kind of stack. In practice,
python does not seem to perform tail recursion optimizations, and conks
out after makepolys(997) on my machine.


You can find out the conking-out limit and change it, within reason.
import sys
help (sys.getrecursionlimit) [...] help (sys.setrecursionlimit)

[...]

Here is a recipe for tail recursion optimization at ASPN:

http://aspn.activestate.com/ASPN/Coo.../Recipe/496691

Python doesn't do any kind of tail recursion optimization by default
because Guido has decided it shouldn't (at least so far). I'm sure it has
been discussed in detail in Python development forums & lists, but I
don't know those details.

This Google search is a start, but it gives too many hits for me to shift
through now:

http://www.google.fi/search?q=site%3...tail+recursion

Pka
Jun 20 '06 #11

"Pekka Karjalainen" <pk******@paju.oulu.fi> wrote in message
news:slrne9f84g.227.pk******@paju.oulu.fi...
Python doesn't do any kind of tail recursion optimization by default
because Guido has decided it shouldn't (at least so far). I'm sure it has
been discussed in detail in Python development forums & lists, but I
don't know those details.


Giving Python's late name resolution, the transformation would be a change
in semantics. Something might be proposed for 3.0.

Terry Jan Reedy

Jun 20 '06 #12

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

17
by: Just | last post by:
While googling for a non-linear equation solver, I found Math::Polynomial::Solve in CPAN. It seems a great little module, except it's not Python... I'm especially looking for its poly_root()...
9
by: strotee76 | last post by:
What do I need to do to setTerm() for it to work properly? If you notice any other glaring issues, then please let me know. With this header file: ======================= #ifndef Polynomial_h...
1
by: Rubén Campos | last post by:
I've trying to implement polynomials of arbitrary order as a C++ template, as shown here: template <unsigned long int N> class Polynomial { public: Polynomial (); ~Polynomial ();
2
by: pradeep rajpoot | last post by:
struct node *insert(struct node *p); void *add (struct node *a,struct node *b); #include<stdio.h> #include<conio.h> #include<alloc.h> struct node { int cof,ex,ey,ez; struct node *link;
2
by: prem425 | last post by:
Write a C++ program to implement the linked list structure representation of a polynomial of several variables. You would prompt for input: two such polynomials – with same number of variables....
7
by: yodadbl07 | last post by:
hey im trying to write a class of polynomials using a linked list. But I am getting an error at run time with my Polynomial* getNext() function. The error says access violation reading location. Im...
5
by: blackx | last post by:
I am creating a Polynomial class using linked list. My problem is that my code has gotten some run-time errors (not compile or build errors) when I was running the program. Specifically, I am...
15
by: hsachdevah | last post by:
Hello, I am trying to create a dictionary item with its key as list type and value as custom object type. It gives me a error "An item with the same key has already been added." Here is my code:...
0
by: ryjfgjl | last post by:
ExcelToDatabase: batch import excel into database automatically...
0
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
1
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: Vimpel783 | last post by:
Hello! Guys, I found this code on the Internet, but I need to modify it a little. It works well, the problem is this: Data is sent from only one cell, in this case B5, but it is necessary that data...
1
by: Defcon1945 | last post by:
I'm trying to learn Python using Pycharm but import shutil doesn't work
1
by: Shællîpôpï 09 | last post by:
If u are using a keypad phone, how do u turn on JavaScript, to access features like WhatsApp, Facebook, Instagram....
0
by: af34tf | last post by:
Hi Guys, I have a domain whose name is BytesLimited.com, and I want to sell it. Does anyone know about platforms that allow me to list my domain in auction for free. Thank you
0
by: Faith0G | last post by:
I am starting a new it consulting business and it's been a while since I setup a new website. Is wordpress still the best web based software for hosting a 5 page website? The webpages will be...
0
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 3 Apr 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome former...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.