6 ms·

This is the missing piece from my mental toolbox. I wish I'd known about it years ago. Co-recursion is a principled way to turn a top-down algorithm into a bot

• gamegoblin 12y ago
  Alternatively, making use of laziness and recursive definitions: fibonacci n = fibs !! n fibs = 1:1:zipWith (+) fibs (tail fibs)
  • Pitarou 12y ago
    Your version is certainly pretty, and it's based on an insight into the nature of the fibonacci series But the value of co-recursion is that you don't need that insight. When you expand out the definitions of `tail`, `!!` and `zipWith`, your code turns out to be the same as mine[1], so I consider that a big win for co-recursion. [1]: At least I think it does.
• Osmium 12y ago
  > 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?
• wyager 12y ago
  Alternatively, fibonacci n = (map fst $ iterate (\(a,b) -> (b,a+b)) (0,1)) !! n
  • Pitarou 12y ago
    I think gamegoblin's was prettier.
    • wyager 12y ago
      Got a really short one! fib a b = a : fib b (a+b) fibn = (!!) (fib 0 1)
• jgg 12y ago
  Corecursion is useful for taking a recursive algorithm and transforming it to a stream-like output pattern. But this is ridiculously inefficient. Well...you might be surprised in the general case. Because of lazy evaluation, Haskell won't necessarily implode on non-TCO recursive functions (example: http://stackoverflow.com/questions/13042353/does-haskell-have-tail-recursive-optimization http://stackoverflow.com/questions/13042353/does-haskell-hav...), and will actually sometimes cause a stack overflow on "optimized" functions. Until now, the only "principled" way I knew of to transform this into something sensible was through memoization, but that's still very wasteful. I think "real" Haskell code usually favors operations of lists over recursive functions. That said, the standard way to transform your recursive structure into something "sensible" is to use a tail-recursive function. In basically any other functional language, you'd go with that approach. To get the same "benefit" in Haskell, you'd have to force strict evaluation inside of a tail-recursive function. This prevents a thunk from causing problems. That said, Haskell doesn't always build up a normal stack on a regular recursive call. Otherwise, you'd just use a list structure. (Someone correct me if I've said something stupid.) ref: http://www.haskell.org/haskellwiki/Tail_recursion http://www.haskell.org/haskellwiki/Tail_recursion
  • Pitarou 12y ago
    My remarks were addressed to people who don't need tail recursion or the benefits & drawbacks of lazy evaluation explained to them, so I think they went a little over your head. I presented a recursive definition, a stream based definition, and a tail-call definition of the fibonacci function. In that toy example, it's easy to get between the three different forms, but in many cases the connection is far less obvious. We need principles that unite the different forms, and allow us to move between them. Co-recursion is one of those principles.
    • jgg 12y ago
      so I think they went a little over your head. I understand lazy evaluation and tail recursion fine. I interpreted your comment as presenting corecursion as the only logical alternative to naive recursive algorithms with or without memoization. You've tacked on the part where you say the latter algorithm is equivalent (due to Haskell's evaluation) - I get that. I'm still not understanding what you mean by only knowing inefficienct, naive recursion in contrast to corecursion. In practice, I have rarely seen corecursion or naive recursion used, but maybe we read different code. In that toy example, it's easy to get between the three different forms, but in many cases the connection is far less obvious. We need principles that unite the different forms, and allow us to move between them. Co-recursion is one of those principles. Uh, okay.
• shoki 12y ago
  Not corecursive, but here's the SICP O(ln(n)) algorithm: fibonacci = fib 1 0 0 1 where fib a b p q n | n == 0 = b | even n = fib a b p' q' (n `div` 2) | otherwise = fib a' b' p q (n - 1) where p' = p*p + q*q q' = 2*p*q + q*q a' = a*q + b*q + a*p b' = b*p + a*q
• LBarret 12y ago
  did you read SICP (this is explained in the first chapters of the book) ? if not you're for a treat.