4 ms·

> But this is ridiculously inefficient. I'm sorry, but I don't understand this. How is that inefficient?

• Aqwis 12y ago
  It makes two recursive calls at each step.
• alepper 12y ago
  Try sketching the call graph of e.g. fibonacci 5.
• gamegoblin 12y ago
  Here is the call stack for 1, 3, and 5 fib 1 1 fib 3 fib 2 fib 1 1 fib 0 1 2 fib 1 1 3 fib 5 fib 4 fib 3 fib 2 fib 1 1 fib 0 1 2 fib 1 1 3 fib 2 fib 1 1 fib 0 1 2 5 fib 3 fib 2 fib 1 1 fib 0 1 2 fib 1 1 3 8 The number of calls grows exponentially. Roughly 1.618^n, to be specific.
  • nodejsguy 12y ago
    If this was reddit, you would get gold for that reply
    • gamegoblin 12y ago
      In the time it took me to do it by hand I am 100% positive I could have written a Python program to do it probably 3 times. Yyyyep just tested it: def fibs(n, tabs=0): if n < 2: print "\t"*tabs + "1" return 1 print "\t"*tabs+"fibs %d"%n a = fibs(n-1, tabs+1) b = fibs(n-2, tabs+1) print "\t"*tabs+str(a+b) return a+b Took exactly 71 seconds to write. I probably spent 3 minutes on it by hand getting all the spaces right.
  • dustingetz 12y ago
    Haskell is lazy and pure, why can't it auto memoize for us so we can code it like we would in math?
    • albertzeyer 12y ago
      A while ago, I asked exactly that question: http://stackoverflow.com/questions/5749039/automatic-memoizing-in-functional-programming-languages http://stackoverflow.com/questions/5749039/automatic-memoizi... I think the answer is basically that there is no good heuristic about what to store, how much and how long.
      • cabalamat 12y ago
        > I think the answer is basically that there is no good heuristic about what to store, how much and how long. In Python you can just put a @memoize decorator before a function you want memoized; would it be possible to have something similar in Haskell?
        • albertzeyer 12y ago
          Yes, see here: http://www.haskell.org/haskellwiki/Memoization http://www.haskell.org/haskellwiki/Memoization Note that in Python, you also have the issue that you still need to specify some cleverness about how long something is stored and what is stored. Many example memoize implementations just store everything (e.g.: https://wiki.python.org/moin/PythonDecoratorLibrary#Memoize https://wiki.python.org/moin/PythonDecoratorLibrary#Memoize) but of course that is not a solution in practice.
          • gizmo686 12y ago
            I don't think the methods mentioned in the haskell wiki are quite equivelent to the python decorator, as they require you to modify the data structure itself to support memoization. It should be possible to use UnsafePerformIO to create a generic function memoize function (at least for inputs that implelemt Eq or Ord), but that is almost definantly overkill and asking for space leaks.