Lambda calculus: fold & Y

[Horse]

Homework Statement

I have two lambda expressions. Triblelist should trible every element in a list eg 1234 to 111222333444. N_th_list should do it n times. The problem is to give some value of n to n_th_list to receive triblelist. How can you do it? Help is really appreciated!

Homework Equations

triblelist = \list. ((fold F) nil ) list,
where F = \a b . cell a (cell a (cell a b))

n_th_list = \n list. ((fold (F n)) nil ) list,
where F = Y (\i .\n a b. n b (\p. cell a (i p a b)))

The Attempt at a Solution

It may be that my equations are wrong. I am not sure of n_th_list. The Y combinator confuses me. I have a bad habit of expanding everything, the calculations really get messy. How should I proceed?

 

[mighty2000]

my first step would be to fully understand the problem and the given equations. From the forum post, it seems that the goal is to find a value of n that will make n_th_list behave the same as triblelist.

To start, let's examine the given equations for triblelist and n_th_list.

For triblelist, we have the equation: triblelist = \list. ((fold F) nil ) list, where F = \a b . cell a (cell a (cell a b))

This means that triblelist is a lambda expression that takes in a list as its argument and then applies the function F to that list using the fold operation. The function F is defined as \a b . cell a (cell a (cell a b)), which takes in two arguments and creates a cell with the first argument and then another cell with the first argument again, and then a final cell with the second argument. This results in a list with each element being tripled.

For n_th_list, we have the equation: n_th_list = \n list. ((fold (F n)) nil ) list, where F = Y (\i .\n a b. n b (\p. cell a (i p a b)))

This is a bit more complex, as it involves the Y combinator. However, we can break it down step by step. The first part, \n list., simply defines the lambda expression with two arguments, n and list. The second part, ((fold (F n)) nil ) list, is the same as in triblelist, where we are applying the fold operation to the list using the function F. However, in this case, F is defined as Y (\i .\n a b. n b (\p. cell a (i p a b))). Let's break this down further.

The Y combinator is a fixed-point combinator, which means it allows us to define recursive functions in lambda calculus. In this case, it is being used to define a recursive function i, which takes in three arguments: n, a, and b. The function F is then defined as \n a b. n b (\p. cell a (i p a b)), which takes in the same three arguments and applies the function i to them.

To summarize, n_th_list is a recursive function that takes in a list and an integer n and applies