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

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top