[ninetyninenine]

It’s hard to characterize what fp is. A lot of people think fp is a bunch of techniques like map, reduce, immutability or high level functions or monads.

None of those things are exclusive to fp. They are just tricks developed by fp.

Here’s how to get a high level characterization of what fp actually is:

You know how in math and physics they have formulas? Formulas for motion, for area, etc.

Functional programming is about finding the formula for a particular program.

Typically when you code you write an algorithm for your program. In functional programming you are writing a formula. Think about what that means.

The formula has side effect benefits that make it easier to manage complexity and correctness. That’s why people like it. These side effects (pun) are not evident until you programmed with fp a certain amount.

Obviously though people naturally reason about things in the form of procedures rather then formulas so fp tends to be harder then regular programming.

[dxbydt]

> Functional programming is about finding the formula for a particular program.

Can be disproved trivially. Anyone can code up a program that generates the nth prime for some n, by iteratively accumulating n primes starting from 2 using trial division. otoh, an actual formula that produces the nth prime would be an earth shaking event.

[ninetyninenine]

Iteration doesn't exist in functional programming. If you ever used iteration in FP you're doing it wrong.

So I ask you... how does a functional program do the algorithm you ask for above?

Recursion and the ternary operator. All iterative programs can be written in recursion and vice versa.

Another way of thinking about this is rather then formula, think expression. Functional programming is about coding up an expression that can fit on one line.

Anything that breaks the program into multiple lines means you're turning your functional expression into a list of procedures.

[ykonstant]

There exist many formulas that encode the program you mentioned or other sieving methods, so it is unclear what you mean by "actual formula". See https://en.wikipedia.org/wiki/Formula_for_primes

[dxbydt]

I prefer to make a distinction between recurrence, identity, and formula. Otherwise the whole discussion is moot. For example, to compute the nth fibonacci, we have Binet’s formula. We don’t need to bootstrap - we just take the golden ratio and its conjugate, exponentiate, take the difference and scale by root 5. That’s a genuine formula. otoh If one says the nth fibonacci is just the sum of the previous two fibonaccis, that’s technically not a formula - you would need to bootstrap to get those previous ones, so that a recurrence - still very useful, but not a formula in the sense you can’t turn the crank and be done. In that specific sense, I agree with Wilf and Dudley that the procedures outlined by Mills, Wright, Wilson etc are essentially worthless as formulas. They are nice identities and recurrences, but not a genuine formula in that you can’t get the nth prime by turning the crank - you have to bootstrap with so many extraneous params it makes the whole exercise futile.

[ninetyninenine]

Definition of formula does not preclude recurrence relations.

Evaluation of a formula will always require some form of "turning the crank" whether it involves recurrence or not.

The evaluation of the formula lives in sort of a separate universe then the formula itself. For example the integral or the limit of something represents something as a formula, but sometimes algorithmic evaluation of such things are not possible. A formula can exist EVEN when a algorithm or "turning the crank" evaluation doesn't exist. It's a seperate thing and does not influence the definition of "formula".

[KolenCh]

You are talking past each other on what formula means. In FP, a recursive function is a valid “formula”. P.S. I’m not arguing for that characterization.

[ninetyninenine]

Hint: it's a recursive formula. There's a isomorphism