4 ms·

I lost interest in FP when my FP solution for the Fibonacci series was exactly how not to do it.

toast0 5y ago
You can write the closed form in FP just as well as any other language. Most FP languages will let you write a recursive form that won't blow the stack. In C, you'd need to used closed form or a loop if you value your stack.
- AnimalMuppet 5y ago
  How do you write the FP version that won't blow your stack? You can't just use TCO, can you? (Because of the two calls.) And if you're using memoization, you could do that in C. And, even a naive implementation wouldn't blow your stack, it would just melt your CPU into a puddle of slag. Or am I missing something here?
  - toast0 5y ago
    TCO works if you write it properly: fib(0) -> 0; fib(1) -> 1; fib(N) when is_integer(N), N >= 2 -> fib(N, 2, fib(0) + fib(1), fib(1)). fib(N, N, Current, _Last) -> Current; fib(N, I, Current, Last) -> fib(N, I + 1, Current + Last, Current). But if you write the same thing in C, it'll still blow your stack (of course, you can transform it into a loop), and you'll need to use bigints somehow, these numbers get big fast. It does use a lot of cpu though; takes not quite 10 seconds to run fib(1000000) on my Pentium G2020. Closed form is certainly faster, although I didn't benchmark it :D
    - toast0 5y ago
      Too late to edit, but if you do fib(N) when ... -> fib(N - 2, fib(0) + fib(1), fib(1)). Then you can check for N = 0 to return Current, and do N - 1 in the iteration. One less value to pass in each recursion should make it faster, and it's less to think about.
Twisol 5y ago
For completeness, what was your solution? I promise not to judge it if you don't want me to :) but it seems like it would be a valuable discussion for others who might be on the fence. My solution (from another conversation on this very page) is: fib 0 a b = b fib n a b = fib (n - 1) b (a + b) It might (or might not) look simple, but this solution arises from an understanding of computation as reduction, which is very much not how imperative languages go about things. So it's really not shameful or even problematic to have arrived at a different solution first.
- GnarfGnarf 5y ago
  I don't recall, it was probably the naïve one.
gsam 5y ago
Implementing it with a hylomorphism is actually quite clean, however, understanding the plumbing to get there is not. The principles are generally quite simple, however, there's no non-mathematical wordings to describe it.

You can write the closed form in FP just as well as any other language. Most FP languages will let you write a recursive form that won't blow the stack. In C, you'd need to used closed form or a loop if you value your stack.

AnimalMuppet 5y ago
How do you write the FP version that won't blow your stack? You can't just use TCO, can you? (Because of the two calls.) And if you're using memoization, you could do that in C. And, even a naive implementation wouldn't blow your stack, it would just melt your CPU into a puddle of slag. Or am I missing something here?
- toast0 5y ago
  TCO works if you write it properly: fib(0) -> 0; fib(1) -> 1; fib(N) when is_integer(N), N >= 2 -> fib(N, 2, fib(0) + fib(1), fib(1)). fib(N, N, Current, _Last) -> Current; fib(N, I, Current, Last) -> fib(N, I + 1, Current + Last, Current). But if you write the same thing in C, it'll still blow your stack (of course, you can transform it into a loop), and you'll need to use bigints somehow, these numbers get big fast. It does use a lot of cpu though; takes not quite 10 seconds to run fib(1000000) on my Pentium G2020. Closed form is certainly faster, although I didn't benchmark it :D
  - toast0 5y ago
    Too late to edit, but if you do fib(N) when ... -> fib(N - 2, fib(0) + fib(1), fib(1)). Then you can check for N = 0 to return Current, and do N - 1 in the iteration. One less value to pass in each recursion should make it faster, and it's less to think about.

Twisol 5y ago

For completeness, what was your solution? I promise not to judge it if you don't want me to :) but it seems like it would be a valuable discussion for others who might be on the fence. My solution (from another conversation on this very page) is: fib 0 a b = b fib n a b = fib (n - 1) b (a + b) It might (or might not) look simple, but this solution arises from an understanding of computation as reduction, which is very much not how imperative languages go about things. So it's really not shameful or even problematic to have arrived at a different solution first.

GnarfGnarf 5y ago
I don't recall, it was probably the naïve one.

gsam 5y ago

Implementing it with a hylomorphism is actually quite clean, however, understanding the plumbing to get there is not. The principles are generally quite simple, however, there's no non-mathematical wordings to describe it.