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.
fold
,map
,filter
, etc. are themselves defined by (structural) recursion? And would you consider it cheating if I suggested that all you need isfix : (t -> t) -> t
which computes fixed points? $\endgroup$