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

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.

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.

Then the author introduced the iterative Fibonacci algorithm, and formally proved that the iterative and recursive algorithms were equivalent. But the author failed to explain where that iterative algorithm came from: there was no general purpose tool like memoization that could be used to derive the iterative form from the recursive form. I still remember the intellectual disappointment.

Now, with co-recursion and a couple of other techniques, that gap is finally bridged. Using co-recursion, I can derive the stream algorithm directly from the recursive definition. And then I can apply deforestation techniques and tail-call optimization to derive the iterative algorithm from the stream algorithm. That's a pretty powerful intellectual toolset, don't you think?

I think I've read that book too.

For the benefit of anyone following along at home: The unproven-but-accepted Church-Turing thesis states that any algorithm that can be done on a Turing machine (i.e., a Turing-complete language) can be represented as a recursive function and a function in the lambda calculus, and vice-versa.

And then I can apply deforestation techniques and tail-call optimization to derive the iterative algorithm from the stream algorithm.

How do you use deforestation and tail-call optimization to derive an iterative function from a stream in the general case?

You're also pulling a false comparison: you've jumped from a 'general' algorithm to "what a corecursive function is evaluated as under Haskell's semantics".

Corecursion builds a data structure. A TCO function, for example, won't produce that kind of output. The corecursive function could only be directly equivalent to the linear time, constant memory TCO function in a lazily-evaluated runtime (if that's true - tail recursive functions in Haskell can actually blow up the stack due to lazy evaluation).

How do you cut an iron bar in half with a pair of scissors?

Deforestation is a tool; not a universal truth.

You're also pulling a false comparison ... The corecursive function could only be directly equivalent to the linear time, constant memory TCO function in a lazily-evaluated runtime

But I'm using a lazily evaluated runtime. My code is Haskell. And in any case, I used deforestation in the last step to remove the lazily evaluated data structure.

If I understand you correctly, you're telling me that high-level mathematical formalisms work better in Haskell. Yes, they do.

  fibonacci n = fibs !! n
  fibs = 1:1:zipWith (+) fibs (tail fibs)

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.

    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

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

    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

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.

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?

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) but of course that is not a solution in practice.

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.

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

     fibonacci n = (map fst $ iterate (\(a,b) -> (b,a+b)) (0,1)) !! n

     fib a b = a : fib b (a+b)
     fibn = (!!) (fib 0 1)