What is the "functional" way of doing this?

B

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
 
P

Paul Rubin

beginner said:
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.
Click to expand...

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

attn.steven.kuo

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.
Click to expand...


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

Steven D'Aprano

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.
Click to expand...


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:.... print x
....
12
12
1[12, 12, 1]
 
P

Paul Rubin

[email protected] said:
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)
Click to expand...

Right, this is functional style, but quite painful in Python (no tail
recursion, and look at all that list copying).
 
A

attn.steven.kuo

[email protected] said:
Recursion is common in functional programming:
Click to expand...
def f(n, l=None):
if l == None:
l = []
if n > 0:
return f(n/26, l + [n%26])
else:
return l
Click to expand...
print f(1000)
Click to expand...

Right, this is functional style, but quite painful in Python (no tail
recursion, and look at all that list copying).
Click to expand...



Yes, I agree that performance would greatly suffer. This
is really idomatic Lisp re-written as Python and was the first
thing that popped into my head when the OP mentioned 'functonal'.

Your generator/iterator solution should run must faster.
 
?

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

[email protected] said:
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)
Click to expand...
Right, this is functional style, but quite painful in Python (no tail
recursion, and look at all that list copying).
Click to expand...
Click to expand...

It might actually be :

def f(n):
if n > 0:
return ([n%26] + f(n/26))
else:
return []

Wouldn't that be ok?
 
J

James Stroud

beginner said:
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
Click to expand...

Does it get any more functional than lambda?

py> f = lambda n, r=None: f(n/26, (r if r else [])) + [n%26] if n/26
else [n%26]
py> f(300000)
[17, 1, 20, 12]
py> f(30000)
[1, 18, 9, 22]
py> f(3000)
[4, 11, 10]
py> f(1000)
[1, 12, 12]


--
James Stroud
UCLA-DOE Institute for Genomics and Proteomics
Box 951570
Los Angeles, CA 90095

http://www.jamesstroud.com/
 
J

James Stroud

James said:
py> f = lambda n, r=None: f(n/26, (r if r else [])) + [n%26] if n/26
else [n%26]
py> f(300000)
[17, 1, 20, 12]
py> f(30000)
[1, 18, 9, 22]
py> f(3000)
[4, 11, 10]
py> f(1000)
[1, 12, 12]
Click to expand...

Oops, those are backwards. Should be:

f = lambda n, r=None: [n%26] + f(n/26, (r if r else [])) if n/26 else [n%26]

--
James Stroud
UCLA-DOE Institute for Genomics and Proteomics
Box 951570
Los Angeles, CA 90095

http://www.jamesstroud.com/
 
J

James Stroud

Ricardo said:
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)

Right, this is functional style, but quite painful in Python (no tail
recursion, and look at all that list copying).
Click to expand...
Click to expand...

It might actually be :

def f(n):
if n > 0:
return ([n%26] + f(n/26))
else:
return []

Wouldn't that be ok?
Click to expand...

You are still copying lists. This wouldn't:

def f(n):
if n>0:
yield n%26
for i in f(n/26):
yield i


James

--
James Stroud
UCLA-DOE Institute for Genomics and Proteomics
Box 951570
Los Angeles, CA 90095

http://www.jamesstroud.com/
 
P

Paul Rubin

James Stroud said:
def f(n):
if n>0:
yield n%26
for i in f(n/26):
yield i
Click to expand...

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

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
Click to expand...

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

Steven D'Aprano

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).
Click to expand...

[snip code]

You may find that using the timeit module is better than rolling your own
timer.
.... if n > 0:
.... return [n % 26] + recursive_func(n/26)
.... else:
.... return []
........ def mseq(n):
.... while n > 0:
.... n, a = divmod(n, 26)
.... yield a
.... return list(mseq(n))
........ "from __main__ import N, recursive_func").repeat()
[16.48972487449646, 17.000514984130859, 16.520529985427856].... "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:
.... results = []
.... while n > 0:
.... n, a = divmod(n, 26)
.... results.append(a)
.... return results
........ "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:
.... "from __main__ import N, recursive_func").repeat(3, 10000)
[7.0015969276428223, 7.6065640449523926, 6.8495190143585205].... "from __main__ import N, generator_func").repeat(3, 10000)
[3.56563401222229, 3.1132731437683105, 3.8274538516998291].... "from __main__ import N, procedural_func").repeat(3, 10000)
[3.3509068489074707, 4.0872640609741211, 3.3742849826812744]
 
?

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

Steven said:
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).
Click to expand...

[snip code]

You may find that using the timeit module is better than rolling your own
timer.
... if n > 0:
... return [n % 26] + recursive_func(n/26)
... else:
... return []
...... def mseq(n):
... while n > 0:
... n, a = divmod(n, 26)
... yield a
... return list(mseq(n))
...... "from __main__ import N, recursive_func").repeat()
[16.48972487449646, 17.000514984130859, 16.520529985427856]... "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:
... results = []
... while n > 0:
... n, a = divmod(n, 26)
... results.append(a)
... return results
...... "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:
... "from __main__ import N, recursive_func").repeat(3, 10000)
[7.0015969276428223, 7.6065640449523926, 6.8495190143585205]... "from __main__ import N, generator_func").repeat(3, 10000)
[3.56563401222229, 3.1132731437683105, 3.8274538516998291]... "from __main__ import N, procedural_func").repeat(3, 10000)
[3.3509068489074707, 4.0872640609741211, 3.3742849826812744]
Click to expand...

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

Alexander Schmolck

beginner said:
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.
Click to expand...

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
 
C

Chris Mellon

Steven said:
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).
Click to expand...

[snip code]

You may find that using the timeit module is better than rolling your own
timer.
def recursive_func(n):
Click to expand...
... if n > 0:
... return [n % 26] + recursive_func(n/26)
... else:
... return []
...
def generator_func(n):
Click to expand...
... 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)",
Click to expand...
... "from __main__ import N, recursive_func").repeat()
[16.48972487449646, 17.000514984130859, 16.520529985427856]
timeit.Timer("generator_func(N)",
Click to expand...
... "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):
Click to expand...
... results = []
... while n > 0:
... n, a = divmod(n, 26)
... results.append(a)
... return results
...
timeit.Timer("procedural_func(N)",
Click to expand...
... "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)",
Click to expand...
... "from __main__ import N, recursive_func").repeat(3, 10000)
[7.0015969276428223, 7.6065640449523926, 6.8495190143585205]
timeit.Timer("generator_func(N)",
Click to expand...
... "from __main__ import N, generator_func").repeat(3, 10000)
[3.56563401222229, 3.1132731437683105, 3.8274538516998291]
timeit.Timer("procedural_func(N)",
Click to expand...
... "from __main__ import N, procedural_func").repeat(3, 10000)
[3.3509068489074707, 4.0872640609741211, 3.3742849826812744]
Click to expand...

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.
Click to expand...

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

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Similar Threads

What "might" I be doing wrong with this snippet? 6
What is the best way of going about recreating the setTimeout() function? 0
What is the counterpart of this C pointer programme in C#? 2
Functional schmunctional... 10
Is there a way to pass this state from component to the fetch? 1
Scanf is being prioritized over printf ? 1
Why is Python telling me variable is local not global? 3
Xah's Edu Corner: Unix Pipe As Functional Language 0

Members online

No members online now.
Total: 27 (members: 0, guests: 27)
Robots: 101

Forum statistics

Threads
473,754
Messages
2,569,522
Members
44,995
Latest member
PinupduzSap

Latest Threads

Top