473,390 Members | 1,719 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,390 software developers and data experts.

What is the "functional" way of doing this?

Hi,

If I have a number n and want to generate a list based on like the
following:

def f(n):
l=[]
while n>0:
l.append(n%26)
n /=26
return l

I am wondering what is the 'functional' way to do the same.

Thanks,
beginner

Jul 30 '07 #1
11 1132
beginner <zy*******@gmail.comwrites:
def f(n):
l=[]
while n>0:
l.append(n%26)
n /=26
return l

I am wondering what is the 'functional' way to do the same.
If you're trying to learn functional programming, maybe you should use
a functional language like Haskell or Scheme. But anyway you might be
thinking of something like:

def f(n):
def mseq(n):
while n 0:
n,a = divmod(n, 26)
yield a
return list(mseq(n))

The above is not really "functional", but it's a reasonably natural
Python style, at least for me.
Jul 30 '07 #2
On Jul 30, 3:48 pm, beginner <zyzhu2...@gmail.comwrote:
Hi,

If I have a number n and want to generate a list based on like the
following:

def f(n):
l=[]
while n>0:
l.append(n%26)
n /=26
return l

I am wondering what is the 'functional' way to do the same.

Recursion is common in functional programming:

def f(n, l=None):
if l == None:
l = []
if n 0:
return f(n/26, l + [n%26])
else:
return l

print f(1000)

--
Hope this helps,
Steven

Jul 30 '07 #3
On Mon, 30 Jul 2007 22:48:10 +0000, beginner wrote:
Hi,

If I have a number n and want to generate a list based on like the
following:

def f(n):
l=[]
while n>0:
l.append(n%26)
n /=26
return l

I am wondering what is the 'functional' way to do the same.

Seems like a perfectly good function to me :)
I don't know about "functional", but that's crying out to be written as a
generator:

def f(n):
while n 0:
n, x = divmod(n, 26)
yield x

And in use:
>>for x in f(1000):
.... print x
....
12
12
1
>>list(f(1000))
[12, 12, 1]
--
Steven.

Jul 30 '07 #4
James Stroud <js*****@mbi.ucla.eduwrites:
def f(n):
if n>0:
yield n%26
for i in f(n/26):
yield i
Right, this mutates i though. Let's say we have a library function
itertools.iterate() and that we ignore (as we do with functions like
"map") that it uses mutation under the clothes:

def iterate(f, x):
# generate the infinite sequence x, f(x), f(f(x)), ...
while True:
yield x
x = f(x)

Then we could write:

from itertools import imap, takewhile
def snd((a,b)): return b

def f(n):
return takewhile(bool,
imap(snd,
iterate(lambda (a,b): divmod(a,26),
divmod(n,26))))
Jul 31 '07 #5
Considering I am a beginner I did a little test. Funny results too. The
function I proposed (lists1.py) took 11.4529998302 seconds, while the
other one (lists2.py) took 16.1410000324 seconds, thats about 40% more.
They were run in IDLE from their own windows (F5).
Of course my little test may me wrong (just started with this language),
in which case I would appreciate any corrections, or comments.
------------------------------------------------
lists1.py :
def f(n):
if n 0:
return ([n%26] + f(n/26))
else:
return []

import time

start = time.time()
for x in range(1,1000000):
f(2100000000)
end = time.time()

print end - start
-----------------------------------------------
lists2.py :
def f(n):
def mseq(n):
while n 0:
n,a = divmod(n, 26)
yield a
return list(mseq(n))

import time

start = time.time()
for x in range(1,1000000):
f(2100000000)
end = time.time()

print end - start
------------------------------------------------
Jul 31 '07 #6
Kept testing (just in case).
There was this other version of lists2.py (see below). So I created
lists3.py and lists4.py.
The resulting times are
lists1.py : 11.4529998302
lists2.py : 16.1410000324
lists3.py : 3.17199993134
lists4.py : 20.9839999676

lists3.py is by far the better time, but it does not generate a list but
a generator object, as soon as you make it into a list (lists4.py) times
go up (I don't know why do they go up that much). Apparently the way you
use the conversion to a list, in the function(lists2.py) or in the loop
(lists4.py), makes a big difference. Anyway lists1.py is still the best
of the list generating times, and (in my view) the most elegant and easy
to understand expression of the algorithm.
------------------------------------------------
lists1.py :
def f(n):
if n 0:
return ([n%26] + f(n/26))
else:
return []

import time

start = time.time()
for x in range(1,1000000):
f(2100000000)
end = time.time()

print end - start
-----------------------------------------------
lists2.py :
def f(n):
def mseq(n):
while n 0:
n,a = divmod(n, 26)
yield a
return list(mseq(n))

import time

start = time.time()
for x in range(1,1000000):
f(2100000000)
end = time.time()

print end - start
------------------------------------------------
lists3.py
def f(n):
if n>0:
yield n%26
for i in f(n/26):
yield i
import time

start = time.time()
for x in range(1,1000000):
f(2100000000)
end = time.time()

print end - start
------------------------------------------------
lists4.py
def f(n):
if n>0:
yield n%26
for i in f(n/26):
yield i
import time

start = time.time()
for x in range(1,1000000):
list(f(2100000000))
end = time.time()

print end - start
----------------------------------------------------

Jul 31 '07 #7
On Jul 30, 5:48 pm, beginner <zyzhu2...@gmail.comwrote:
Hi,

If I have a number n and want to generate a list based on like the
following:

def f(n):
l=[]
while n>0:
l.append(n%26)
n /=26
return l

I am wondering what is the 'functional' way to do the same.

Thanks,
beginner
I see. It is interesting (and not surprisingly) that recursion or
yield are required. Thanks for everyone's help.

Jul 31 '07 #8
On Tue, 31 Jul 2007 09:01:42 -0300, Ricardo ArŠoz wrote:
Considering I am a beginner I did a little test. Funny results too. The
function I proposed (lists1.py) took 11.4529998302 seconds, while the
other one (lists2.py) took 16.1410000324 seconds, thats about 40% more.
They were run in IDLE from their own windows (F5).
[snip code]

You may find that using the timeit module is better than rolling your own
timer.
>>def recursive_func(n):
.... if n 0:
.... return [n % 26] + recursive_func(n/26)
.... else:
.... return []
....
>>def generator_func(n):
.... def mseq(n):
.... while n 0:
.... n, a = divmod(n, 26)
.... yield a
.... return list(mseq(n))
....
>>>
import timeit
N = 10**6+1
timeit.Timer("recursive_func(N)",
.... "from __main__ import N, recursive_func").repeat()
[16.48972487449646, 17.000514984130859, 16.520529985427856]
>>>
timeit.Timer("generator_func(N)",
.... "from __main__ import N, generator_func").repeat()
[27.938560009002686, 28.970781087875366, 23.977837085723877]
If you're going to compare speeds, you should also test this one:
>>def procedural_func(n):
.... results = []
.... while n 0:
.... n, a = divmod(n, 26)
.... results.append(a)
.... return results
....
>>>
timeit.Timer("procedural_func(N)",
.... "from __main__ import N, procedural_func").repeat()
[15.577107906341553, 15.60145378112793, 15.345284938812256]
I must admit that I'm surprised at how well the recursive version did, and
how slow the generator-based version was. But I'd be careful about drawing
grand conclusions about the general speed of recursion etc. in Python from
this one single example. I think this is simply because the examples tried
make so few recursive calls. Consider instead an example that makes a few
more calls:
>>N = 26**100 + 1

timeit.Timer("recursive_func(N)",
.... "from __main__ import N, recursive_func").repeat(3, 10000)
[7.0015969276428223, 7.6065640449523926, 6.8495190143585205]
>>timeit.Timer("generator_func(N)",
.... "from __main__ import N, generator_func").repeat(3, 10000)
[3.56563401222229, 3.1132731437683105, 3.8274538516998291]
>>timeit.Timer("procedural_func(N)",
.... "from __main__ import N, procedural_func").repeat(3, 10000)
[3.3509068489074707, 4.0872640609741211, 3.3742849826812744]
--
Steven.

Jul 31 '07 #9
Steven D'Aprano wrote:
On Tue, 31 Jul 2007 09:01:42 -0300, Ricardo ArŠoz wrote:
>Considering I am a beginner I did a little test. Funny results too. The
function I proposed (lists1.py) took 11.4529998302 seconds, while the
other one (lists2.py) took 16.1410000324 seconds, thats about 40% more.
They were run in IDLE from their own windows (F5).

[snip code]

You may find that using the timeit module is better than rolling your own
timer.
>>>def recursive_func(n):
... if n 0:
... return [n % 26] + recursive_func(n/26)
... else:
... return []
...
>>>def generator_func(n):
... def mseq(n):
... while n 0:
... n, a = divmod(n, 26)
... yield a
... return list(mseq(n))
...
>>>import timeit
N = 10**6+1
timeit.Timer("recursive_func(N)",
... "from __main__ import N, recursive_func").repeat()
[16.48972487449646, 17.000514984130859, 16.520529985427856]
>>>timeit.Timer("generator_func(N)",
... "from __main__ import N, generator_func").repeat()
[27.938560009002686, 28.970781087875366, 23.977837085723877]
If you're going to compare speeds, you should also test this one:
>>>def procedural_func(n):
... results = []
... while n 0:
... n, a = divmod(n, 26)
... results.append(a)
... return results
...
>>>timeit.Timer("procedural_func(N)",
... "from __main__ import N, procedural_func").repeat()
[15.577107906341553, 15.60145378112793, 15.345284938812256]
I must admit that I'm surprised at how well the recursive version did, and
how slow the generator-based version was. But I'd be careful about drawing
grand conclusions about the general speed of recursion etc. in Python from
this one single example. I think this is simply because the examples tried
make so few recursive calls. Consider instead an example that makes a few
more calls:
>>>N = 26**100 + 1

timeit.Timer("recursive_func(N)",
... "from __main__ import N, recursive_func").repeat(3, 10000)
[7.0015969276428223, 7.6065640449523926, 6.8495190143585205]
>>>timeit.Timer("generator_func(N)",
... "from __main__ import N, generator_func").repeat(3, 10000)
[3.56563401222229, 3.1132731437683105, 3.8274538516998291]
>>>timeit.Timer("procedural_func(N)",
... "from __main__ import N, procedural_func").repeat(3, 10000)
[3.3509068489074707, 4.0872640609741211, 3.3742849826812744]

Yup! As soon as the size of the list increases the generator function
gets better (50% in my tests). But it's interesting to note that if the
list is within certain limits (I've tested integers (i.e. 2,100,000,000
=7 member list)) and you only vary the times the funct. is called then
the recursive one does better.
Jul 31 '07 #10
beginner <zy*******@gmail.comwrites:
Hi,

If I have a number n and want to generate a list based on like the
following:

def f(n):
l=[]
while n>0:
l.append(n%26)
n /=26
return l

I am wondering what is the 'functional' way to do the same.
This is very 'functional' (and also quite concise):

f = compose(list,partial(unfold, divmod(_,26)))

The definitions of compose, unfold, and _ are left as excercises (of
increasing difficulty) for the reader.

'as
Aug 1 '07 #11
On 7/31/07, Ricardo ArŠoz <ri******@gmail.comwrote:
Steven D'Aprano wrote:
On Tue, 31 Jul 2007 09:01:42 -0300, Ricardo ArŠoz wrote:
Considering I am a beginner I did a little test. Funny results too. The
function I proposed (lists1.py) took 11.4529998302 seconds, while the
other one (lists2.py) took 16.1410000324 seconds, thats about 40% more..
They were run in IDLE from their own windows (F5).
[snip code]

You may find that using the timeit module is better than rolling your own
timer.
>>def recursive_func(n):
... if n 0:
... return [n % 26] + recursive_func(n/26)
... else:
... return []
...
>>def generator_func(n):
... def mseq(n):
... while n 0:
... n, a = divmod(n, 26)
... yield a
... return list(mseq(n))
...
>>import timeit
N = 10**6+1
timeit.Timer("recursive_func(N)",
... "from __main__ import N, recursive_func").repeat()
[16.48972487449646, 17.000514984130859, 16.520529985427856]
>>timeit.Timer("generator_func(N)",
... "from __main__ import N, generator_func").repeat()
[27.938560009002686, 28.970781087875366, 23.977837085723877]
If you're going to compare speeds, you should also test this one:
>>def procedural_func(n):
... results = []
... while n 0:
... n, a = divmod(n, 26)
... results.append(a)
... return results
...
>>timeit.Timer("procedural_func(N)",
... "from __main__ import N, procedural_func").repeat()
[15.577107906341553, 15.60145378112793, 15.345284938812256]
I must admit that I'm surprised at how well the recursive version did, and
how slow the generator-based version was. But I'd be careful about drawing
grand conclusions about the general speed of recursion etc. in Python from
this one single example. I think this is simply because the examples tried
make so few recursive calls. Consider instead an example that makes a few
more calls:
>>N = 26**100 + 1

timeit.Timer("recursive_func(N)",
... "from __main__ import N, recursive_func").repeat(3, 10000)
[7.0015969276428223, 7.6065640449523926, 6.8495190143585205]
>>timeit.Timer("generator_func(N)",
... "from __main__ import N, generator_func").repeat(3, 10000)
[3.56563401222229, 3.1132731437683105, 3.8274538516998291]
>>timeit.Timer("procedural_func(N)",
... "from __main__ import N, procedural_func").repeat(3, 10000)
[3.3509068489074707, 4.0872640609741211, 3.3742849826812744]

Yup! As soon as the size of the list increases the generator function
gets better (50% in my tests). But it's interesting to note that if the
list is within certain limits (I've tested integers (i.e. 2,100,000,000
=7 member list)) and you only vary the times the funct. is called then
the recursive one does better.

Not especially surprising. Suspending and resuming a generator is
naturally more expensive than a single function call. The advantages
of generators are time/space tradeoffs, greater expressiveness, and
state preservation (not used here).
Aug 1 '07 #12

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

Similar topics

49
by: Ville Vainio | last post by:
I don't know if you have seen this before, but here goes: http://text.userlinux.com/white_paper.html There is a jab at Python, though, mentioning that Ruby is more "refined". -- Ville...
30
by: Christian Seberino | last post by:
How does Ruby compare to Python?? How good is DESIGN of Ruby compared to Python? Python's design is godly. I'm wondering if Ruby's is godly too. I've heard it has solid OOP design but then...
81
by: Matt | last post by:
I have 2 questions: 1. strlen returns an unsigned (size_t) quantity. Why is an unsigned value more approprate than a signed value? Why is unsighned value less appropriate? 2. Would there...
669
by: Xah Lee | last post by:
in March, i posted a essay ‚ÄúWhat is Expressiveness in a Computer Language‚ÄĚ, archived at: http://xahlee.org/perl-python/what_is_expresiveness.html I was informed then that there is a academic...
13
by: Sarath | last post by:
What's the advantage of using for_each than the normal iteration using for loop? Is there any 'tweak' to use stream objects as 'Function' parameter of for_each loop. Seems copy function can do...
206
by: WaterWalk | last post by:
I've just read an article "Building Robust System" by Gerald Jay Sussman. The article is here: http://swiss.csail.mit.edu/classes/symbolic/spring07/readings/robust-systems.pdf In it there is a...
14
by: Franz Steinhšusler | last post by:
Hello NG, wWhat are the best programs in your opinion, written entirly in pyhton, divided into categories like: a) Games b) Utilities/System c) Office d) Web/Newsreader/Mail/Browser ....
4
by: BorisBoshond | last post by:
Hi all, Hope someone is able and willing to help me with following problem. I received a xsd file from another company, our company i supposed to return xml based on that xsd. Problem is that I...
34
by: vippstar | last post by:
On Nov 17, 1:43 pm, Ertugrul SŲylemez <e...@ertes.dewrote: Well your blog entry starts with which is untrue and a bad way to start an article. Reading further, in your code...
0
by: taylorcarr | last post by:
A Canon printer is a smart device known for being advanced, efficient, and reliable. It is designed for home, office, and hybrid workspace use and can also be used for a variety of purposes. However,...
0
by: ryjfgjl | last post by:
If we have dozens or hundreds of excel to import into the database, if we use the excel import function provided by database editors such as navicat, it will be extremely tedious and time-consuming...
0
by: emmanuelkatto | last post by:
Hi All, I am Emmanuel katto from Uganda. I want to ask what challenges you've faced while migrating a website to cloud. Please let me know. Thanks! Emmanuel
0
BarryA
by: BarryA | last post by:
What are the essential steps and strategies outlined in the Data Structures and Algorithms (DSA) roadmap for aspiring data scientists? How can individuals effectively utilize this roadmap to progress...
1
by: nemocccc | last post by:
hello, everyone, I want to develop a software for my android phone for daily needs, any suggestions?
1
by: Sonnysonu | last post by:
This is the data of csv file 1 2 3 1 2 3 1 2 3 1 2 3 2 3 2 3 3 the lengths should be different i have to store the data by column-wise with in the specific length. suppose the i have to...
0
marktang
by: marktang | last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However,...
0
by: Hystou | last post by:
Most computers default to English, but sometimes we require a different language, especially when relocating. Forgot to request a specific language before your computer shipped? No problem! You can...
0
jinu1996
by: jinu1996 | last post by:
In today's digital age, having a compelling online presence is paramount for businesses aiming to thrive in a competitive landscape. At the heart of this digital strategy lies an intricately woven...

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.