Lambda function which generates a sequence

94 Views Asked by At

Consider this sequence of lambda functions: $\lambda xy. yxy$, $\lambda xyz. zxyz$, $\lambda xyzw. wxyzw$, etc. I would like some lambda function $g$ such that when $g$ is applied to $n$, it returns the $n$th element of this sequence (I'm using Church numerals.)

What I have tried is to construct a function $f$ turns the first element of the sequence into the second, the second into the third, etc. My thoughts being the $g$ could apply this function $n$ times to generate the right element of the sequence. But I have been unsuccessful in my attempts to construct $f$.

As a simpler problem, I tried to find a function that would simply add a variable to a function, but my attempts to do that lead to functions which could add variables to functions with a small number of variables, but they would hit a ceiling where I couldn't add variables anymore.

1

There are 1 best solutions below

0
On BEST ANSWER

First of all, let us look at one of the subterms of the third expression in your list: $\lambda zw . wxyzw$ with free variables $x,y$. Here, the subterm $wxy$ can be abstracted as "do something to $w$". In particular, if we define $f := \lambda w . wxy$, then the expression becomes $\lambda zw . fwzw$. That suggests that we might have more luck if as an intermediate step we concentrate on generating the sequence $\lambda fw.fww$, $\lambda fzw.fwzw$, $\lambda fyzw.fwyzw$, $\lambda fxyzw.fwxyzw$, etc.

Now, the question is: for example, if we have one term $\lambda fyzw.fwyzw$, how can we get to the next term $\lambda fxyzw.fwxyzw$? Well, if $g := \lambda fyzw.fwyzw$, then the next term can be expressed as $\lambda fx.g(\lambda w.fwx)$. Therefore, what we want to iterate will be $\lambda gfx.g(\lambda w.fwx)$.

Thus, the intermediate sequence will be generated as $\lambda n.n(\lambda gfx.g(\lambda w.fwx))(\lambda fw.fww)$. Finally, once we have for example $\lambda fxyzw.fwxyzw$, it is easy to get $\lambda xyzw.wxyzw$ by applying it with $f := \lambda w.w$.

To summarize, the originally desired sequence can be generated by the lambda expression $$\lambda n.n(\lambda gfx.g(\lambda w.fwx))(\lambda fw.fww)(\lambda w.w).$$ (Note that for $n = 0$ you get the term $\lambda x.xx$, then starting at $n = 1$ you get $\lambda xy.yxy$, at $n=2$ you get $\lambda xyz.zxyz$, etc. If instead you want to start with $n=0$ giving $\lambda xy.yxy$, then replace $\lambda fw.fww$ with $\lambda fzw.fwzw$ in the above expression.)