Lambda calculus lists construction explanation
-
04-11-2019 - |
Question
I have the following notes that introduce how lambda calculus handles lists. They go as follows:
A list is something we can match on and deconstruct if it is not empty:
list match{ case Nil => M case Cons(x,y) => N(x,y) }
A list value is given by how it interacts with two terms M and N
(1) For starters I don't understand at all what is the role of M and N here. Then it continues:
We define it (a list) as a function that will take such M and N as arguments
$Nil = \lambda mn.m$
$Cons(P,Q) = \lambda mn. n (P,Q)$
(2) Assuming I know how pairs and if constructs work in lambda calculus how can I come up with this expressions myself? I suppose that once this is clear I will be able to understand this sentence:
Cons is like a pair but takes m as argument, too, to fit along with nil
Can you clarify points (1) and (2)?
Edit:
This are some further comments made in my notes that may make easier to understand what the intention of the writer is:
$Nil \ M \ N \implies M$ $Cons(P,Q) \ M \ (\lambda p. p._1) \implies \cdots \implies (P,Q)._1$
No correct solution