What is the "functional" way of doing this?

[beginner]

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

[Paul Rubin]

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.

[attn.steven.kuo]

On Jul 30, 3:48 pm, beginner <[e-mail]:

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

[Steven D'Aprano]

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.

[Paul Rubin]

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))))

[=?ISO-8859-1?Q?Ricardo_Ar=E1oz?=]

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

[=?ISO-8859-1?Q?Ricardo_Ar=E1oz?=]

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

[beginner]

On Jul 30, 5:48 pm, beginner <[e-mail]:

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.

[Steven D'Aprano]

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.

[=?ISO-8859-1?Q?Ricardo_Ar=E1oz?=]

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.

[Alexander Schmolck]

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

[Chris Mellon]

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).