[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