Làm thế nào để viết một danh sách trống bằng cách sử dụng S, K và tôi combinators?

Question

Tôi biết rằng:

(cons [p] [q]) is ((s ((s i) (k [p]))) (k [q])) 
(car [lst]) is ([lst] k) 
(cdr [lst]) is ([lst] (k i)) 

Tôi muốn viết một danh sách như thế này

(cons [a] (cons [b] (cons [c] [nil]))) 

, đó sẽ là một cái gì đó như thế này:

((s ((s i) (k [a]))) (k ((s ((s i) (k [b]))) (k ((s ((s i) (k [c]))) (k [nil])))))) 

Nhưng tôi không biết cách biên dịch 'nil' thành S, K và I combinators. Có ai biết không?

Cảm ơn trước, Edwin Jose Palathinkal

Answer 1

Điều duy nhất bạn cần từ một đại diện nil là để có thể xác định nó - viết một số null? vị trả về "true" cho nil và "false" cho tất cả các cặp khác. Điều này có nghĩa là câu trả lời phụ thuộc vào sự thể hiện của bạn về đúng/sai. Với lựa chọn chung của λxy.x và λxy.y, mã hóa tiện lợi cho nil là λf.[true]. Dịch này sang SKI là rất dễ dàng (và tôi sẽ không làm điều đó ở đây, vì nó trông giống như bài tập về nhà ...).

(Ngoài ra, việc thực hiện một vị null? cho đại diện này cho nil là một bài tập tốt.)