I am wondering if there is some proof that all recursive algorithms can be rewritten to use some known set of higher-order functions instead of recursion. I'm talking about functions like fold, map, filter, etc.

If recursion can always be replaced, I'm also interested in knowing whether there is some mechanical translation, or if it's something that can't be automated.

Apologies if this question is ill-formed. I'm no PLT expert.

  • $\begingroup$ Are you looking for Kleene normal form? $\endgroup$ – François G. Dorais Dec 9 '16 at 1:41
  • 1
    $\begingroup$ You could always use the Y combinator which is sufficient to simulate all recursion... $\endgroup$ – cody Dec 9 '16 at 3:00
  • 1
    $\begingroup$ Does it matter that fold, map, filter, etc. are themselves defined by (structural) recursion? And would you consider it cheating if I suggested that all you need is fix : (t -> t) -> t which computes fixed points? $\endgroup$ – Andrej Bauer Dec 9 '16 at 7:10
  • $\begingroup$ Can we migrate this to cs.computerscience.com? $\endgroup$ – Andrej Bauer Dec 9 '16 at 7:15
  • $\begingroup$ I am not sure about Kleene normal form, but the others were correct to guess that I was lacking basic knowledge about fixed-point combinators. Incidentally, I don't care whether or not the higher order functions are defined by structural recursion. But I'm going to go away and read more before thinking about this. Thanks guys. $\endgroup$ – nepp Dec 9 '16 at 16:42

You may replace recursion with computation of fixed points, so all you need is a fixed-point operator

fix : (a -> a) -> a

which satisfies

fix f = f (fix f)

Then, given a recursive definition of f : a -> b,

f = Φ(f)

we may define f as

f = fix (λg.Φ(g))

Here fix has type ((a -> b) -> (a -> b)) -> (a -> b).

You may consider this to be cheating, but the question is not really research-level precisely because the connection between recursion and fixed points is a basic piece of knowledge. I am guessing that maybe you did not know about the connection.

  • $\begingroup$ Thank you! I studied this about 8 years ago, and since I haven't looked at he subject since I had indeed forgotten the connection. Maybe I'll return when I've figured out what I'm really trying to ask, but this answer is definitely the starting point I was looking for. $\endgroup$ – nepp Dec 9 '16 at 16:35

Not the answer you're looking for? Browse other questions tagged or ask your own question.