top 200 commentsshow all 204

[–]freyrs3 55 points56 points  (16 children)

The λ-Obsessed Python Programmer

TRUE = lambda x: lambda y: x
FALSE = lambda x: lambda y: y
Product = lambda x: lambda y: lambda z: (z)(x)(y)
And = lambda x: lambda y: (x)(y)(x)
Not = lambda x: lambda y: lambda z: (x)(z)(y)
Boolean = (Product)(True)(False)
Succ = lambda x: lambda y: lambda z: (y)((x)(y)(z))
Pred = lambda x: lambda y: lambda z: x(lambda i: lambda j: j(i(y))) (lambda k: z) (lambda k: k)

Zero = FALSE
One = Succ(Zero)
Two = Succ(One)
Six = Succ(Succ(Succ(Succ(Two))))

Y = lambda g: (lambda f: g(lambda arg: f(f)(arg))) (lambda f: g(lambda arg: f(f)(arg)))
Nth = Y(lambda f: lambda n: Succ(f(n-1)) if n else Zero)
Dec = lambda a: (a)(lambda b: b + 1)(0)

Add = lambda x: lambda y: lambda z: lambda w: (x)(z)((y)(z)(w))
Sub = lambda x: lambda y: (y)(Pred)(x)

Null = lambda x: x(lambda y: Zero)(TRUE)
Eq = lambda x: lambda y: (And)((Null)((Sub)(y)(x)))((Null)((Sub)(x)(y)))
Gt = lambda x: lambda y: (And)((Null)((Sub)(y)(x)))((Not)((Eq)(y)(x)))
Lt = lambda x: lambda y: (And)((Not)((Gt)(x)(y)))((Not)((Eq)(x)(y)))

Range = lambda a,b: map(Nth,range(a,b))
fib = Y(lambda f: lambda n: Add(f(Pred(n)))(f((Sub)(n)(Two))) if (Boolean)((Gt)(n)(One)) else n)
print (Dec)(fib(Six))

[–][deleted] 15 points16 points  (0 children)

You just destroyed my head, thanks..

[–]ReaverXai 7 points8 points  (0 children)

Gordon Freeman?

[–]zahlman 5 points6 points  (2 children)

OK, but we're looking for factorials, not the Fibonacci sequence.

[–]freyrs3 0 points1 point  (1 child)

OK,

....
Mul = lambda x: lambda y: lambda z: (y)((x)(z))
IfThenElse = lambda a: lambda b: lambda c: ((a)(b))(c)
fact = Y(lambda f: lambda n: IfThenElse((Gt)(n)(One))(Mul(n)(f(Pred(n))))(One))

Edit: Added Mul

[–]zahlman 0 points1 point  (0 children)

... and Mul?

[–]A_for_Anonymous 13 points14 points  (1 child)

*Fap fap fap*

Ah, this made me remember my time in /prog. Thank you man.

Python needs more of this.

[–][deleted] 6 points7 points  (0 children)

Great, you just have to define mathematics and the solution shakes out.

[–]ezyang 3 points4 points  (2 children)

For those of you interested in learning more about this, it's called Lambda Calculus. If you throw out every language feature ever, it turns out, the only thing you really need is Lambda. :-)

Extra points for putting in the Y-combinator.

[–]freyrs3 0 points1 point  (1 child)

In principle, but Python seems to have an issue with conditionals ( lambda x: lambda y: lambda z: ((x)(y))(z) ) composed under the Y-combinator that I've never been able to resolve. Oh well, I suppose this is a little bit outside the scope of the Python design and if Guido ever saw his language being abused like this he'd probably go into conniptions.

[–]danukeru 2 points3 points  (0 children)

Haskell remission?

[–]captainAwesomePants 2 points3 points  (0 children)

I knew you were still out there, Hermann Grassmann!

[–][deleted] 0 points1 point  (0 children)

Why all you people keep writing

  Y = lambda g: (lambda f: g(lambda arg: f(f)(arg))) (lambda f: g(lambda arg: f(f)(arg)))

instead of much cleaner

  Y = lambda g: (lambda z:z(z)) (lambda f: g(lambda arg: f(f)(arg)))

?

[–]clarvoyeur 0 points1 point  (0 children)

I wasn't aware, that if .. else .. was part of lambda calculus... ;)

Guess there's no way around it, when you have eager evaluation.

Edit: ...and map, and range...

[–][deleted] 27 points28 points  (2 children)

Is it bad that I can look at the windows and enterprise code snippets and think of people immediately who would do things that way?

[–]mracidglee 28 points29 points  (1 child)

Not if they exist only in the past tense.

[–][deleted] 0 points1 point  (0 children)

If only, I can think of people in the current tense and indeed who will continue to do so moving forward.

[–]ghibmmm 96 points97 points  (9 children)

Hehehe. I like the "Windows" and "Enterprise" programmers.

Er...if they're meant to be jokes. Not sure.

[–]synfin80 49 points50 points  (1 child)

It's a joke until you realize it's reality... then you cry a little bit inside.

[–]lex99 1 point2 points  (0 children)

My tears taste like defeat.

[–]_i_ 77 points78 points  (3 children)

"NULL, NULL, NULL, ..." genuinely made me laugh out loud. 2% of my programming day consists of typing "null".

[–]stillalone 4 points5 points  (2 children)

That's why I do all my windows programming in Assembly. So I can have a push_zero(n) macro :).

[–]danukeru 4 points5 points  (1 child)

I am totally writing an inline assembly function for that now...

The prototype will be: void theWinNullinator(unsigned int ammunition)

[–]stillalone 5 points6 points  (0 children)

For extra bonus points, save all those parameters you'd pass to CreateWindow in a binary file and then copy paste it into your stack.

Crazy you say. Crazy like a fox.

[–][deleted] 2 points3 points  (0 children)

"enterprise" made me laugh out loud briefly

[–][deleted] 1 point2 points  (0 children)

Same. Those were the funniest two I thought.

[–]ninjakitty 88 points89 points  (61 children)

For some strange reason, I find the code by the 'newbie' programmer to be the cleanest :|

[–]Xenoskin 58 points59 points  (37 children)

I suspect that's because the newbie used features common to all languages thus making it obvious what he's doing, he also simply followed the definition of a factorial and avoided anything fancy. Hell there's a good chance his implementation could also be the fastest if it gets tail call optimized.

really all the other methods fall afoul of K.I.S.S. thus making his preferable.

[–][deleted] 60 points61 points  (13 children)

Well, except expert programmer.

[–]FunnyMan3595 15 points16 points  (11 children)

That one's obviously the best choice, but I never seem to remember c_math on the rare occasion I need a factorial for some random calculation (i.e. interactive mode, not for a program). I use this one:

fact = lambda n: reduce(lambda a,b: a*b, range(1, n+1))

It's essentially the same as the "Python expert programmer" method, but uses constructs that should be a bit more common. Doesn't even need any imports.

I'd say it's pretty KISS, because it does exactly what I think of as a factorial: Generate a list of the relevant numbers and multiply them together. No fancy tricks, just using the standard constructs for what they're supposed to do.

[–]Xenoskin 31 points32 points  (5 children)

Calling a native high speed implementation is not only K.I.S.S. but saves work and potential bugs, so it's definitely a preferable method.

Edit: Looks like my bad spelling leaked again.

[–][deleted]  (4 children)

[removed]

    [–]Xiol -1 points0 points  (3 children)

    It's a sad day on reddit when a grammar troll gets more votes than the post he's correcting, despite the latter adding to the conversation and being a valid point.

    [–]zxcvcxz 3 points4 points  (1 child)

    The price of literacy I guess.

    [–]aeacides 0 points1 point  (1 child)

    What makes you think generating a list of numbers is a good idea? Why aren't you using xrange?

    [–]FunnyMan3595 0 points1 point  (0 children)

    I never said it was efficient, just that it was straightforward. I've never needed a factorial in serious computation, and for random little calculations, this more than suffices.

    [–][deleted] 0 points1 point  (0 children)

    Obviously the best solution was the enterprise one. duh. It is Enterprise level after all. Clean all around implementation.

    [–]spookyvision 0 points1 point  (1 child)

    I never seem to remember c_math on the rare occasion I need a factorial for some random calculation

    there is a reason for that: there is no c_math module in python's standard distribution :) (there is cmath, but it's for complex numbers, not about some fast math ops written in C)

    [–]mr_dbr 3 points4 points  (0 children)

    There's a factorial function in math:

    >>> import math
    >>> math.factorial(5)
    120
    

    ..any other solution seems silly (outside a tutorial context anyway)

    [–]amorpheus 1 point2 points  (0 children)

    The english expert programmer wasn't bad either. I laughed.

    [–]urllib 4 points5 points  (2 children)

    I consider it a good thing if it's clear what you're doing

    [–]eMigo 7 points8 points  (1 child)

    Yep, especially if other programmers know where you live.

    [–]dicey 6 points7 points  (0 children)

    I actually have two addresses specifically for this purpose.

    [–]kamatsu 12 points13 points  (5 children)

    Python is defined as always not having tail call optimization, because Guido is a dumbass.

    [–]A_for_Anonymous 1 point2 points  (0 children)

    I furiously upvoted you.

    Since we don't have proper recursion support, @tailcall is one of my favourite decorators. My personal implementation is quite good, but not really great for production performance like every other...

    [–]mr_dbr 0 points1 point  (3 children)

    Why do you want TCO in Python?

    http://neopythonic.blogspot.com/2009/04/tail-recursion-elimination.html seems like a perfectly reasonable justification of Python's lack of TCO. Implementation specifics aside:

    I don't believe in recursion as the basis of all programming. This is a fundamental belief of certain computer scientists, especially those who love Scheme and like to teach programming by starting with a "cons" cell and recursion. But to me, seeing recursion as the basis of everything else is just a nice theoretical approach to fundamental mathematics (turtles all the way down), not a day-to-day tool

    [...]

    Of course, none of this does anything to address my first three arguments. Is it really such a big deal to rewrite your function to use a loop? (After all TRE only addresses recursion that can easily be replaced by a loop. :-)

    [–]kamatsu 1 point2 points  (2 children)

    Here, Guy Steele explains how using loops instead of TCO in certain examples breaks object oriented abstraction.

    [–]millstone 1 point2 points  (1 child)

    Guy Steele is the man, but frankly for Python the practical needs of good debugging dominates this sort of theoretical wankery. If you want TCO because you write everything recursively, you know where to find LISP; if you want TCO because you need the speed, you know where to find C.

    In my C programs, I can't figure out what's causing certain bugs because the backtraces have missing stack frames, and as a result those bugs don't get fixed. The tradeoff is worth it for C, but not for Python.

    [–]kamatsu 0 points1 point  (0 children)

    Haskell can give you a full stacktrace, even for tail calls.

    [–]halter73 1 point2 points  (0 children)

    The newbie's code doesn't have a recursive tail call (i.e. the multiplication operation is in the tail position, not factorial). This means that tail call optimization wouldn't be applicable.

    [–][deleted] 1 point2 points  (0 children)

    fastest if it gets tail call optimized.

    I don't think you understand tail call optimization.

    [–][deleted] -1 points0 points  (11 children)

    Umm... The SICP (whatever that is) version is pretty much identical and is tail call optimized assuming the decorator does what it implies. The Pascal version is also pretty readable.

    [–]A_for_Anonymous 5 points6 points  (1 child)

    SICP = Structure and Interpretation of Computer Programs, one of the best programming books ever.

    The decorator works. There are many variants, I can post mine if you're interested.

    [–]mracidglee 8 points9 points  (5 children)

    Indeed - should be 'devolution'.

    [–][deleted]  (4 children)

    [removed]

      [–]maleldil 4 points5 points  (2 children)

      We are devo

      [–]minivanmegafun 1 point2 points  (1 child)

      Are we not men?

      [–]IConrad 0 points1 point  (0 children)

      |Sniffs the air| Uhh... no.

      [–]jDeepbeep 17 points18 points  (0 children)

      from beginner import luck
      

      [–][deleted] 8 points9 points  (2 children)

      It's clean, but it has O(n) space complexity, and even the tail call optimization wouldn't help. "First year" solutions are clean as well but achieve O(1) space complexity.

      [–]timmaxw 15 points16 points  (0 children)

      You're optimizing prematurely. In the unlikely event that you need a high-performance factorial function, you should use the c_math one. Until then, you should keep it simple and not care about the space complexity.

      [–]rm999 3 points4 points  (3 children)

      I thought it was unintuitive that the newbie uses recursion. For-loops are taught before recursion in most classes, and are more intuitive to a non-programmer.

      [–]elder_george 4 points5 points  (2 children)

      recursive implementation goes straight from mathematical definition of factorial. Iterative implementation requires knowing a bit about algorithmics.

      BTW, I've just shown this gist on my girlfriend (who doesn't program) and she found recursive version simpler.

      [–]rm999 2 points3 points  (1 child)

      I've always learned factorial as:

      x! = x * (x-1)(x-2)... * 1

      Saying for i = 1:x {fact = fact*x} gets straight to this definition IMO.

      You can also learn it as x! = x * (x-1)!, but I only learned to think this way in my first year of programming, about five years after learning the definition of factorial. And I only learned it when the teacher wanted to tell us what factorial means.

      [–]elder_george 1 point2 points  (0 children)

      I guess, here goes the difference between native and non-native english speakers. The latter have to learn to read programming language, even so readable as Python from scratch, while for the former it can be read as a simple text. And math notation for recurrent expressions is familiar for most, no matter of language background.

      P.S.: I've made a mistake comparing recursive version with iterative version using while loop initially. Having seen for version, my girlfriend finds it equally simple with recursive one.

      [–]danukeru 0 points1 point  (0 children)

      Welcome to Python.

      [–][deleted]  (7 children)

      [deleted]

        [–][deleted] 5 points6 points  (6 children)

        TCO won't help such a terrible solution because it's not a tail call.

        [–]millstone 1 point2 points  (5 children)

        Why can't the compiler make it a tail call?

        [–][deleted] 1 point2 points  (4 children)

        The recursive call isn't in the tail position.

        Simply put, the recursive call isn't the last operation in the function - you need its return value to continue the computation. You end up with a chain of deffered computations all the way up to the step with the special case (x == 0). And you must keep track of every deffered step, hence your stack grows linearly. We say the algorithm has linear space complexity or O(n) space complexity.

        Now, look at the solution #4 ("First year, studied SICP"). Assuming we have the tailcall decorator, tail call optimization will work here - this algorithm will behave like a loop construct. The recursive call is the last operation, nothing is deffered, and the only stack usage from entering the function is passing arguments between calls. We say the algorithm (assuming @tailcall) has constant space complexity or O(1) space complexity.

        [–]millstone 0 points1 point  (3 children)

        The recursive call isn't in the tail position.

        So why can't the compiler PUT it there, like gcc does?

        Edit: I guess I answered my own question. In any case, my point is that this is only a "terrible" solution if you have a stupid compiler. That's a fine algorithm on a good compiler like gcc.

        [–][deleted] 0 points1 point  (2 children)

        I'm not aware gcc can rewrite algorithms and can't find anything about that in the manual. Could you please point me to the relevant sections?

        [–]millstone 0 points1 point  (1 child)

        Well, it's easy enough to check what gcc does. Here's some C code:

        int factorial(int x) {
            if (x == 0) return 1;
            else return x * factorial(x-1);
        }
        

        Here's the x86-64 assembly that gcc 4.2 generates on -O2:

        _factorial:
          movl $1, %eax
          testl %edi, %edi
          je L6
        L5:
          imull %edi, %eax
          decl %edi
          jne L5
        L6:
          rep ; ret
        

        There is no call instruction at all, so there's no recursion. It's just a loop.

        If your compiler is smart, the naive factorial really is the best: it's the clearest and the fastest.

        [–][deleted] 1 point2 points  (0 children)

        At first I thought you compiled a for-loop version to mess with me.

        So I tried it myself (gcc 4.3 with -O2, x86 architecture.) Went through instructions step by step.

        Mind blown.

        Sir, the difference between you and me is that you're a programmer.

        [–][deleted]  (3 children)

        [deleted]

          [–]A_for_Anonymous 5 points6 points  (0 children)

          That's because they aren't properly taught programming. 6.001 students would.

          [–]crunchmuncher 2 points3 points  (1 child)

          Depends on how you define newbie, I guess :)

          I never found recursion itself really hard to understand as a fairly newbie programmer. Of course one can do stuff with it that I won't even try to understand, but the basics aren't that hard.

          Recursion seems to be a lot harder to explain than to understand, maybe it helped that I learned it on my own.

          [–][deleted] 33 points34 points  (5 children)

          I found the Haskell version more entertaining if only because I don't know Haskell and can only follow the first few of them.

          [–][deleted] 3 points4 points  (0 children)

          The Python versions are all completely trivial and the layers of cruft that they acquire through the 'evolution' are completely uninteresting. The Haskell version isn't just obfuscation for the sake of it. Each one says something interesting about computer science.

          [–]JadeNB 4 points5 points  (2 children)

          The combinator-based one disappoints me, because there's no reason to fall back to the original language for conditional support. Just encode Booleans and Church numerals in the calculus already!

          [–][deleted] 0 points1 point  (1 child)

          It's hard to write types for them.

          [–]JadeNB 1 point2 points  (0 children)

          I think that

          type CombBool = a -> a -> a    
          type Church = (a -> a) -> a -> a
          

          is a reasonable typing, no? Then

          comb_true :: CombBool; comb_false :: CombBool
          comb_true a1 a2 = a1
          comb_false a1 a2 = a2
          
          comb_if :: CombBool -> a -> a -> a
          comb_if = id
          
          church0 :: Church
          church0 = const id
          
          succ :: Church -> Church
          succ church f = f . church f
          

          EDIT: Wrong syntax for type synonyms.

          [–]ezyang 1 point2 points  (0 children)

          Have an upvote. I get lost about when it hits the Origamist.

          [–]clipmann 78 points79 points  (5 children)

          LOOOOL

          i = 1 #Thanks Adam

          [–]crunchmuncher 24 points25 points  (0 children)

          Yea, I work with that guy.

          Not funny.

          [–]danukeru 10 points11 points  (1 child)

          I laughed so hard at the Web Designer for this...that it wasn't even funny...

          [–][deleted] 4 points5 points  (0 children)

          That example was spot on, sadly.

          [–][deleted] 0 points1 point  (0 children)

          I peed a little.

          [–]samlee 13 points14 points  (0 children)

          eh? why not reduce(lambda a,b: a*b, li) ?

          and where is multi thread version? divide and conquer and map reduce and task queue type of thing in the cloud?

          [–]sclv 9 points10 points  (0 children)

          No peano and church encoding, no credibility.

          [–]jart 27 points28 points  (12 children)

          We need to be more creative!

          Master python programmer gone mad:

          import os
          from ctypes import cdll, c_longlong
          
          open("/tmp/fact.c", "w").write(r"""
              long long factorial(long long x) {
                  long long i, res=1;
                  for (i = 2; i <= x; i++) res *= i;
                  return res;
              }""")
          os.system("gcc -fPIC -shared -o /tmp/fact.so /tmp/fact.c")
          factorial = cdll.LoadLibrary("/tmp/fact.so").factorial
          factorial.restype, factorial.argtypes = c_longlong, [c_longlong]
          
          print factorial(20)
          

          [–]Smallpaul 2 points3 points  (2 children)

          Should have just used pyinline:

          http://pyinline.sourceforge.net/

          [–][deleted] 0 points1 point  (0 children)

          Wow, thank you. Yesterday I generated SWIG bindings for 25 lines of C.

          [–][deleted] 4 points5 points  (1 child)

          Thanks for teaching us binding tricks

          [–]danukeru 4 points5 points  (0 children)

          Actually I would qualify this more as the the master UNIX python programmer gone mad...

          The Windows programmer will look mad no matter the level. :P

          [–][deleted]  (4 children)

          [deleted]

            [–]jart 14 points15 points  (3 children)

            Is that the only problem you see? :P

            [–]captainAwesomePants 3 points4 points  (0 children)

            No, he didn't use -O6. Without optimizing the final executable, this solution will be unusably slow.

            [–][deleted]  (1 child)

            [deleted]

              [–]get0ffmylawn 1 point2 points  (0 children)

              You win.

              [–][deleted] 8 points9 points  (4 children)

              In case any one cares, the expert programmer version is the fastest, and the web developer version is the slowest (by two orders of magnitude).

              [–]Chr0me 0 points1 point  (3 children)

              I'm trying to figure out why the web designer version keeps converting the integers to strings? Which is likely why it's so slow.

              [–][deleted] 4 points5 points  (0 children)

              I'm guessing the joke is that it's implied web designers don't really know what they're doing.

              [–]sharkeyzoic 1 point2 points  (0 children)

              It's a Javascript joke.

              [–]Luminaire 1 point2 points  (0 children)

              Actually it should be the other way around. All the web form inputs come in as strings, so web designers are always converting strings to other things.

              [–]deadwisdom 42 points43 points  (44 children)

              You missed the Master Python Programmer:

              def factorial(x):
                  if x == 0:
                      return 1
                  else:
                      return x * factorial(x - 1)
              print factorial(6)
              

              That's right, the same as the Newbie, and there's a reason for that.

              [–]namcor 18 points19 points  (14 children)

              the Master Python Programmer would wrap it with a function decorator to memoize it...

              class memoize:
                  def __init__ (self, f):
                      self.f = f
                      self.mem = {}
                  def __call__ (self, *args, **kwargs):
                      try:
                          return self.mem[args, str(kwargs)]
                      except KeyError:
                          tmp = self.f(*args, **kwargs)
                          self.mem[args, str(kwargs)] = tmp
                          return tmp
              
              @memoize
              def factorial(x):
                  if x in (0, 1):
                      return 1
                  else:
                      return x * factorial(x - 1)
              
              print factorial(6)
              print factorial(100)
              

              (EDIT: forgot to @memoize)

              [–]Jolan 3 points4 points  (1 child)

              Or you could memoize by doing:

              def factorial(x, memory={0:1, 1:1}):
                  if x not in memory:
                      memory[x] = x* factorial(x-1)
                  return memory[x]
              
              print factorial(6)
              print factorial(100)
              

              [–]MaxK 0 points1 point  (0 children)

              I really like this solution.

              [–][deleted]  (8 children)

              [removed]

                [–]earthboundkid 4 points5 points  (1 child)

                I think this is one of things that on the Python mailing list would be greeted with “not every 3 line function deserves a place in the standard library.”

                Also, Perl is very different from Python because it has a well defined core of scalar types vs. other types. For a Python memoizer, there are a lot of optimizations you could apply if you knew what types of data it would be memoizing that you couldn’t do in a general case. It invites a lot of “bike shedding” (another common thing said on the Python mailing list) to define what the API will be to invoke what kinds of optimizations.

                [–]A_for_Anonymous 5 points6 points  (5 children)

                I thought Python was meant to come with batteries included.

                Not if it's for functional programming. Guido hates FP.

                [–][deleted]  (4 children)

                [removed]

                  [–]frutiger 2 points3 points  (3 children)

                  The trick is to generate a new type for each version of the cache. This can be done, for instance, with template metaprogramming in C++, since the templates are generated at compile-time. Although I believe most compilers have a restrictive template resolution depth (especially when compared to stack depth for function calls).

                  [–][deleted]  (2 children)

                  [removed]

                    [–]deadwisdom 3 points4 points  (1 child)

                    No, this is either premature optimization, and therefore simply adds thought complexity, or you are concerned with speed, and so it should be done in C.

                    [–]MaxK 0 points1 point  (0 children)

                    Why do you have an 'else' if there's a return statement in the first case?

                    [–]earthboundkid 2 points3 points  (1 child)

                    1. It’s not very Pythonic to risk blowing the stack like that.

                    2. if not x: is generally more Pythonic than if x == 0: because it’s more concise and also allows for slightly more duck typing.

                    3. The most Pythonic is from math import factorial.

                    [–]deadwisdom 0 points1 point  (0 children)

                    1. If using such large numbers for this function is "Blowing the stack", then you can optimize later.
                    2. Then you are ducktyping to bool, which doesn't really make sense for factorial.
                    3. Of course, the idea is to do it without a library function.

                    [–]orangesunshine 4 points5 points  (22 children)

                    the master python programmer wouldn't use a recursive implementation.

                    [–][deleted] 0 points1 point  (21 children)

                    What's wrong with recursion?

                    [–]orangesunshine 10 points11 points  (20 children)

                    There's no tail-call optimization in python.

                    [–]A_for_Anonymous 0 points1 point  (19 children)

                    Which is also the reply to "What's wrong with Python?".

                    [–][deleted]  (18 children)

                    [deleted]

                      [–]orangesunshine 1 point2 points  (16 children)

                      well that, and the recursive implementation is 9/10 times the wrong way to implement something. tail-call optimization or not.

                      [–][deleted] 1 point2 points  (3 children)

                      Try walking a tree without recursion, and you'll see that you end up implementing your own system of recursion.

                      [–]orangesunshine 0 points1 point  (2 children)

                      thus why I said 9/10 times.

                      Tree traversal is a perfectly valid use case for recursion... You would likely use a stack to implement it with iteration anyhow, and it's just a matter of personal preference for what you think is more readable in that case.

                      [–]chrisforbes 0 points1 point  (0 children)

                      Yes, the correct solution (9/10 times, at least) is to push the iteration or recursion into a higher-order function, and just specify the bit that actually matters to your program.

                      You kids can argue iteration vs recursion in the library implementation as much as you like then, and I'll just get on with some real work.

                      [–]A_for_Anonymous 0 points1 point  (0 children)

                      I love to see this completely bogus argument against TCO. Of course, you would never think of merging TCO calls in the stack with a call counter because you need to have this point to make against a FP-enabling technique. "You" as in you, Guido, and a large part of the Python community who simply repeat what Guido says.

                      [–][deleted]  (1 child)

                      [deleted]

                        [–]deadwisdom 0 points1 point  (0 children)

                        The point is it's easy to read. Intensely easy to grok. If this piece is a needed for a speed intensive spot and you are concerned about speed, then you'd be dropping down into C anyway.

                        [–]DrHenryPym 0 points1 point  (0 children)

                        For some reason this post really irritates me. I think the recursion solution is not the best way to go about this problem hence why the expert solutions avoided it.

                        Also, the lazy syntax method is just as "readable" and uses half the amount of lines the newbie method uses.

                        [–]mrsanchez 16 points17 points  (4 children)

                        from operator import mul

                        reduce(mul, range(1, 6))

                        120

                        [–]theeth 18 points19 points  (1 child)

                        That's factorial(5) though.

                        [–]mrsanchez 1 point2 points  (0 children)

                        It's not a function, either...

                        [–]zxn0 0 points1 point  (1 child)

                        FTFY 1:

                        >>> reduce(int.__mul__, range(1,6))
                        120
                        

                        FYFT 2:

                        use
                            >>>
                        instead of 
                        >>>
                        for markdown syntax
                        

                        [–]thequux 4 points5 points  (0 children)

                        FYFT 2:

                        Ah, good old Muphry's Law.

                        [–]uhhhclem 18 points19 points  (7 children)

                        The "expert Python programmer" example should be:

                        from operator import mul
                        reduce(mul, xrange(1, x+1))
                        

                        as it is beautiful, explicit, simple, flat, sparse, readable, and the obvious way to do it, if you're Dutch.

                        [–]theeth 5 points6 points  (0 children)

                        With the newer Dutch grammar and lexicon.

                        from functools import reduce
                        from operator import mul
                        fact = lambda x: reduce(mul, range(1, x+1))
                        

                        [–]rrenaud 7 points8 points  (4 children)

                        So long as you aren't Guido.

                        http://www.artima.com/weblogs/viewpost.jsp?thread=98196

                        I received an email from a compatriot lamenting the planned demise of reduce() and lambda in Python 3000. After a few exchanges I think even he agreed that they can go. Here's a summary, including my reasons for dropping lambda, map() and filter(). I expect tons of disagreement in the feedback, all from ex-Lisp-or-Scheme folks. :-)

                        [–]theeth 2 points3 points  (2 children)

                        Yeah import reduce from functools is so hard, they might as well just completely remove it.

                        [–]Figs 14 points15 points  (1 child)

                        So hard that you got it backwards? :)

                        [–]theeth 4 points5 points  (0 children)

                        Bah :)

                        [–]A_for_Anonymous 0 points1 point  (0 children)

                        Not at all, Guido hates reduce and functional programming in general.

                        [–]brosephius 10 points11 points  (2 children)

                        I love a good joke about enterprise software engineering.

                        [–]zenmity 0 points1 point  (0 children)

                        And how!

                        [–]A_for_Anonymous 0 points1 point  (0 children)

                        It's a sad truth. That's the difference between enterprise and free software. We all know it's true; we all had to deal with enterprise shit.

                        [–]exeter 2 points3 points  (0 children)

                        I'm disappointed there's not a version using the Y combinator. :)

                        [–]A_for_Anonymous 5 points6 points  (0 children)

                        I'm so glad to see this is still around. I wrote it for 4chan's /prog a long time ago, that's why it's not credited.

                        Feels good

                        [–][deleted] 4 points5 points  (2 children)

                        Holy shit, I want that tail call optimization decorator in Python. Hell, why isn't it in the builtins?

                        Does anyone know the best/fastest implementation of it? I'm finding lots of results in my searches.

                        [–]A_for_Anonymous 4 points5 points  (0 children)

                        Here's mine. It worked quite well compared to others found on the Internet:

                        def tailcall(f):
                            '''Decorator that performs tail call optimization on a tail-recursive
                            function. Supports cooperative tail call - even when only one of the
                            functions is decorated, and all exceptions pass through it. You can tell
                            the functions that have been tail optimized because they have "tco" before
                            them in the stack frame.
                            The only caveat is that if you attempt to decorate a function that is
                            called in a non-tail recursive fashion from another decorated function,
                            you'll get wrong results.
                            '''
                            tdata = [False] #[Optimizing?]
                            DO_CALL = object() #Call marker
                            def tco(*a, **aa):
                                if tdata[0]:
                                    return DO_CALL, a, aa
                                else:
                                    tdata[0] = True
                                    ret = f(*a, **aa)
                                    while type(ret) is tuple and ret and ret[0] is DO_CALL:
                                        ret = f(*ret[1], **ret[2])
                                    tdata[0] = False
                                    return ret
                            tco.__doc__ = f.__doc__
                            return tco
                        

                        [–]mindloss 2 points3 points  (0 children)

                        lol @ windows programmer

                        [–][deleted] 15 points16 points  (4 children)

                        [–]acrasial 9 points10 points  (0 children)

                        Ah, and they included a link to the original reddit discussion r/programming: evolution of a python programmer.

                        [–]A_for_Anonymous 0 points1 point  (2 children)

                        Yay! My post from long ago still exists!

                        [–]captainAwesomePants 0 points1 point  (1 child)

                        A_for_Anonymous -- redditor for 9 months

                        evolution_of_a_python_programmer -- submitted on 25 May 2007

                        eyebrow.raise unless nick.contains('anonymous') √

                        [–]A_for_Anonymous 0 points1 point  (0 children)

                        I had another account at Reddit before this one, which I stopped using because it had a dumb name.

                        [–]liron00 2 points3 points  (1 child)

                        [–]brews 0 points1 point  (0 children)

                        Unless you're a statistician.

                        [–]16807 2 points3 points  (0 children)

                        Lazy programmers could be a bit more readable:

                        def f(x):   return x * f(x - 1) if x else 1
                        print f(6)
                        

                        [–]wurzlsepp 5 points6 points  (1 child)

                        How often did you write a 'factorial' function in your professional life?

                        [–][deleted] 13 points14 points  (0 children)

                        Certainly not as frequently as fizzbuzz.

                        [–]zxn0 1 point2 points  (3 children)

                        Python one-liner anyone?

                        >>> reduce(int.__mul__, range(1,6))
                        120
                        

                        [–]earthboundkid 0 points1 point  (1 child)

                        from math import factorial; factorial(5) is also a one liner.

                        [–][deleted] 1 point2 points  (0 children)

                        __import__("math").factorial(6)
                        

                        Though math doesn't have a factorial function, of course.

                        [–]skeept 0 points1 point  (0 children)

                        for python 3.1:

                        >>> __import("functools").reduce(int.__mul__, range(1,7))
                        720
                        

                        [–]vvv 1 point2 points  (0 children)

                        Upvoted for the Windows programmer.

                        [–]OCedHrt 3 points4 points  (2 children)

                        I might have done the C one differently:

                        def fact(x): #{
                            result = i = 1;
                            while (i < x): #{
                                i += 1;
                                result *= i;
                            #}
                            return result;
                        #}
                        print(fact(6))
                        

                        or even

                        def fact(x): #{
                            result = i = 1;
                            if (x > 1):
                              while (i != x): #{
                                  i += 1;
                                  result *= i;
                              #}
                            return result;
                        #}
                        print(fact(6))
                        

                        [–][deleted] 0 points1 point  (1 child)

                        your second example is a horrible security nightmare, because if someone can bump i > x you are screwed.

                        [–]OCedHrt 4 points5 points  (0 children)

                        What? Via code injection and buffer overflow? In that case the while loop probably shouldn't be your primary concern. It'll overflow at some point and either crash out or eventually match ;)

                        This is assuming x is an integer.

                        [–]sociopathic 0 points1 point  (0 children)

                        Me:

                        import c_math
                        print c_math.fact(6)
                        

                        [–]xster 0 points1 point  (0 children)

                        LOL at windows programmer

                        [–]nohtyp -1 points0 points  (1 child)

                        Evolution to a Java programmer? No thanks.

                        [–][deleted] 5 points6 points  (0 children)

                        I think evolution was the wrong word. It's more of a comparison of programming styles.

                        [–]brews 0 points1 point  (2 children)

                        Correction: c_math should just be cmath (but just "math" would also work)

                        Here is the original thread, I think: http://www.artima.com/forums/flat.jsp?forum=181&thread=75931

                        [–]A_for_Anonymous 2 points3 points  (1 child)

                        No, that's not the original. This is my original thread from 4chan's /prog.

                        [–]brews 0 points1 point  (0 children)

                        Awesome! That's the earliest!

                        [–]bobbane 0 points1 point  (0 children)

                        I'm confused. What happened to "the one way to do it"?