1
$\begingroup$

I am studying for my exam and I wanted to do some extra excercises, but I have some problems with solving :) Can anyone please help or give me some advice where to start? Thank you!

We can represent every list of lambda expressions $x_0, x_1, ..., x_k$ with lambda expression $[x_0, x_1, ..., x_k]$ , defined as: $[x_0, x_1, ... , x_k] = \lambda c n. c \, x_0 \, (c \, x_1 \, (... (c \, x_k \, n) ...))$

Define lambda expression s, satisfying the equation $s([\underline{n_0}, ..., \underline{n_k}]) = \underline{n_0 + ... + n_k}$ , where $\underline{n}$ is a Church numeral, representing natural number $n$.

Define lambda expression $r$ , satisfying the equation $r([x_0, ..., x_k]) = [x_k, ..., x_0]$ .

Define lambda expression $h$ and $t$ , satisfying the equation $h([x_0, ..., x_k]) = x_0 in t([x_0, x_1, ..., x_k]) = [x_1, ..., x_k]$ .

$\endgroup$
  • $\begingroup$ Actually I don't know where to start, because I am not sure if I understand what I have to do. I don't understand if at the beginning we get the list, or we have to calculate the numbers from expression given. Also, I know how to define sum for example, but I don't know how to get first element from the list. $\endgroup$ – Ivan Obradović Jun 21 '13 at 18:16
1
$\begingroup$

Hint: This way lists are represented as folds. So if you have a lambda term representing a list, you just supply a folding function and a value to start with and the result will be the folded value.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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