444,100 Members | 2,979 Online Need help? Post your question and get tips & solutions from a community of 444,100 IT Pros & Developers. It's quick & easy.

# What is the "functional" way of doing this?

 P: n/a 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 Replies

 P: n/a beginner 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

 P: n/a On Jul 30, 3:48 pm, beginner 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

 P: n/a 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

 P: n/a James Stroud 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

 P: n/a 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

 P: n/a 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

 P: n/a On Jul 30, 5:48 pm, beginner 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

 P: n/a 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 timeitN = 10**6+1timeit.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 + 1timeit.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

 P: n/a 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. Thefunction I proposed (lists1.py) took 11.4529998302 seconds, while theother 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 timeitN = 10**6+1timeit.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 + 1timeit.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

 P: n/a beginner 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

 P: n/a On 7/31/07, Ricardo Aráoz >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 timeitN = 10**6+1timeit.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 + 1timeit.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. 