472,096 Members | 1,169 Online

# 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 1092 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

'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 discussion thread is closed

Replies have been disabled for this discussion.

### Similar topics

 49 posts views Thread by Ville Vainio | last post: by 30 posts views Thread by Christian Seberino | last post: by 81 posts views Thread by Matt | last post: by 669 posts views Thread by Xah Lee | last post: by 13 posts views Thread by Sarath | last post: by 206 posts views Thread by WaterWalk | last post: by 14 posts views Thread by Franz Steinhäusler | last post: by 4 posts views Thread by BorisBoshond | last post: by 34 posts views Thread by vippstar | last post: by 3 posts views Thread by isladogs | last post: by reply views Thread by beacampos | last post: by 1 post views Thread by beacampos | last post: by reply views Thread by pddon | last post: by reply views Thread by BenitoJuares | last post: by reply views Thread by leo001 | last post: by reply views Thread by antdb | last post: by 2 posts views Thread by Bright1Light | last post: by 7 posts views Thread by bounthong | last post: by