# Reproducing Nest-function with recursive nesting does not work

In general, when I am learning a new programming language, it helps me to understand how builtin functions works. I am trying to reproduce the builtin Nest[f,exp,n] without any fancy Mathmatica functions.

This is what I want:

nesting[f_,k_] := Nest[f,#,k]&
=> nesting[f,3][Pi] = f[f[f[Pi]]]


I thought about implementing a recursive function:

nesting[f_,k_] := nesting[f,k-1]
nesting[f,1] := f[#]&


But unfortunately, this does not work. Trying to evaluate the function at some point does add this function evaluation to the outermost, not the innermost function.

=> nesting[f,3][Pi] = f[f[f[#1]&]]][Pi]


It seems that the ampersand (&) from the definition of a pure function has to be outside the whole nested function. That means I want to have following structure:

nesting[f,3] = f[f[f[#1]]]&


For that I tried changing my function definition to

nesting[f_,k_] := nesting[f,k-1]&
nesting[f_,1] := f[#]


This yiedls a (atleast for me) unexpected and definitely unwanted behaviour:

nesting[f,3] = nesting[f,3-1]&
nesting[f,3][Pi] = nesting[f,2-1]&


Why does the second parameter (k) change depending on if I evaluate the function or just want to get the pure function from $3-1$ to $2-1$? And how can I fix my function in general?

• First, you should note that there's an underscore missing in your code. nesting[f,1] := f[#]& Should have an underscore under the first f since it's a function argument. Without it the function only works with literally the symbol "f" Jul 12 '18 at 14:01
• Thanks, I will edit that. It was actually a copy error, in Mathematica I implemented it with the underscore. Jul 12 '18 at 14:24

Here's a few examples to play with:

Clear@nest;
nest[f_, 1] := f;
nest[f_, k_] := f @* nest[f, k - 1];


First thing to note is that f and f[#]& are basically the same here. "f" is represents the function named "f". "f[#]&" represents "the function that you get if you apply f to some argument". Those are basically the same.

Here's a more confusing solution, which I think follows a bit more directly from what you're trying to do:

Clear@nest;
nest[f_, 1] := f[#]&;
nest[f_, k_] := f[nest[f, k - 1][#]] &;


It's weird and gross. I'd find this very confusing. Maybe the best way to write this is to include all the arguments:

Clear@nest;
nest[f_, 1][arg_] := f[arg];
nest[f_, k_][arg_] := nest[f, k - 1][f[arg]];


Unfortunately, it does not really solve my problem completely.

Let us begin with your first solution

Clear@nest;
nest[f_, 1] := f;
nest[f_, k_] := f @* nest[f, k - 1];


That does work, but does not produce the wanted

nest[f_,3] = f[f[f[#]]]&


and also used the builtin Function "Composition".

Clear@nest;
nest[f_, 1] := f[#]&;
nest[f_, k_] := f[nest[f, k - 1][#]] &;


does not really work for me. The function will not be evaluated at some recursion point.

nest[f,k] = f[nest[f, 3 - 1][#1]] &


It seems to be the same problem as I was having before. Is there a problem on my part? It seems that the function does not have a pattern that it can match to because of the double double brackets and remains unevaluated?

Clear@nest;
nest[f_, 1][arg_] := f[arg];
nest[f_, k_][arg_] := nest[f, k - 1][f[arg]];


would work in principle but does not produce the wanted result

nest[f,3][Pi] = f[f[f[Pi]]]
nest[f,3] = nest[f,3]


Why will nest[f,3] not result in a pure function but remain unevaluated? Is there a way to archieve

To be clear:

I am trying to produce a pure function that expects one parameter, such that

nest[f,k] = f[f[f[.......f[f[f[#]]]......]]]&


that means, I want Mathmatica to return a pure function even when I am not evaluating at a certain point.

Clear@nest;
nest[f_, 1][arg_] := f[arg];
nest[f_, k_][arg_] := nest[f, k - 1][f[arg]];
nest[f_, k_] := nest[f, k][#] &


This will result in

nest[f,3] = nest[f,3][#1]&


I am feeling that we are just there, how can I force Mathematica to evaluate the last

nest[f,3][#1]


to

f[f[f[#1]]]


?

EDIT:

As an example, when using the builtin "Nest"

Clear@nest;
nest[f_, k_] := Evaluate[Nest[f, #, k]] &


I am getting

nest[f,3] = f[f[f[#1]]]&


This is the desired behaviour.

EDIT2:

Hey, I was able to solve the problem using nasty recursive pure functions:

nest[f_,k_]:=Evaluate[If[#1==1, f[#2], f[#0[#1-1, #2]]] &[k, #]]&

This leads to the expected behaviour:

nest[f,3]=f[f[f[#1]]]&

• What are your go-to programming languages? This usually helps me understand where you're coming from. I gave you functions that were functionally equivalent to what you want. You're more interested in something different. Procedural code generation. Are you sure you really want to do this? I feel like you're inflicting brutal suffering on yourself unnecessarily. Jul 12 '18 at 19:51
• "Function" has attribute HoldAll. So you want to do the evaluating outside of it.  Clear@nest; nest[f_, 1] := f[#] &; nest[f_, k_] := With[{inner = Apply[f[#] &, nest[f, k - 1]]}, Function@inner]  Jul 12 '18 at 19:52
• If you're coming from another functional programming language, there's a big caveat you should be aware of about "Functions" in Mathematica. They're more or less just patterns that behave like functions in different ways. Mathematica isn't a functional programming language. It's a loose implementation of one on top of a term rewriting system Jul 12 '18 at 19:58
• Thank you for your informative answers! As I have stated in my post, I got it to work, but certainly not as elegant as you. Jul 12 '18 at 21:39
• I am coming from an Python/C++ standpoint and I still have some trouble understanding Mathematicas "Pseuo" functional programming syntax. Jul 12 '18 at 21:41