从一对到 lambda 演算/方案中的列表

Question

我正在学习一些关于 lambda 演算的知识（这非常简洁）并且在方案中定义了以下如何完成一对：

; PAIR
; λabf.fab
(define PAIR (lambda (a) (lambda (b) (lambda (f) ((f a) b)))))
(define mypair ((PAIR 1) 2))

; FIRST
; λab.a
(define FIRST (lambda (a) (lambda (b) a)))

; SECOND
; λab.b
(define SECOND (lambda (a) (lambda (b) b)))

(display "First is: ")     (display (mypair FIRST))
(display " | Second is: ") (display (mypair SECOND))

First is: 1 | Second is: 2

如何进一步抽象它以创建列表的数据结构，例如，制作类似 [1 2 3 4 5] 而不仅仅是 [2 3] 的东西？

我自己能做的最好的事情就是对这些进行硬编码，例如，五个：

(define five (
    (PAIR 1) (
      (PAIR 2) (
        (PAIR 3) (
          (PAIR 4) 5)))))

(display (five FIRST)) (display ((five SECOND) FIRST)) (display (((five SECOND) SECOND) FIRST)) (display ((((five SECOND) SECOND) SECOND) FIRST)) (display ((((five SECOND) SECOND) SECOND) SECOND))

是否有更多 'general' 解决方案？

Answer 1

普通 LISP 列表不是 [1 2 3]，而是 (1 . (2 . (3 . ())))。它们是用 (cons 1 (cons 2 (cons 3 '()))) 创建的，因此 lambda 演算中的完全相等列表将是 ((PAIR 1) ((PAIR 2) ((PAIR 3) ...)))

现在标准的 lisp 实现通常会打印 (1 2 3)，但这是打印机完成的一些时髦魔法。它的规则是，如果 cdr 是一个列表，您可以省略点和一组括号。当您使用 lambda 演算对数据建模时，REPL 将始终显示 lambda/closure 个对象，因此您需要实用函数来理解结构并显示相应的可视化。这不是 lambda 演算的一部分，因为只要满足公理就可以了：

(car (cons a b)) ; ==> a
(cdr (cons a b)) ; ==> b

list 是一个 cons 链接参数的辅助函数。你确实可以为对做一些类似的东西，但它不是 lambda 演算的一部分：

(define TRUE (lambda (p) (lambda (q) p)))
(define NIL (lambda (x) TRUE))

(define (ch-list . args)
  (let helper ((lst (reverse args)) (result NIL))
    (if (null? lst)
        result
        (helper (cdr lst)
                ((PAIR (car lst)) result)))))

Answer 2

正如西尔维斯特所说。列表不是数组，它们是条件链，以特殊的 nil 或 () 对象结尾。这意味着要构建这样的东西，您需要 cons 和这个特殊对象。

我在 Racket 中实现了一种玩具语言，称为 'oa'（一个参数），截至几分钟前，您可以找到 here。在其最纯粹的变体中，函数的语法是，例如 (λ x x)：参数周围没有括号，因为为什么会有？还有 define 可以给事物命名，但仅此而已。这是用这种语言实现的 conses：

(define true (λ x (λ y x)))
(define false (λ x (λ y y)))

(define cons (λ h (λ t (λ s ((s h) t)))))
(define car (λ l (l true)))
(define cdr (λ l (l false)))
(define nil (λ l true))
(define null? (λ l (l (λ h (λ t false)))))

方便（但也令人讨厌），oa 使用普通的 Racket reader，因此您可以读取数字，即使它们在语言中没有语义。所以，例如

> (cdr ((cons 1) 1))
1

例如，制作一个元素的三元素列表：

(define three-elt
  (λ e
    ((cons e)
     ((cons e)
      ((cons e)
       nil)))))

> (three-elt 1)
#<λ>
> (car (three-elt 1))
1
> (cdr (cdr (cdr (three-elt 1))))
{nil}: (λ l true)

（有一些特殊的、脆弱的魔法可以让它打印出已经 defined 的事物的名称，就像在最后一个例子中一样。）

给定 zero、zero?、succ 和 pred（后继者和前任者）的定义，以及条件函数 cond，看起来像 (((cond test) if-true) if-false)，然后你可以写一个脏版的 nth:

(define nth
  (λ n (λ c
         (((cond (zero? n))
           (car c))
          ((nth (pred n)) (cdr c))))))

这很脏，因为它免费使用 nth，但您可以使用组合器解决这个问题：我喜欢 U，所以：

(define U
  ;; The U combinator
  (λ f (f f)))

(define nth
  (U (λ t
       (λ n
         (λ c
           (((cond (zero? n))
             (car c))
            (((U t) (pred n)) (cdr c))))))))

使用其中之一：

> ((nth (succ zero)) ((cons true) ((cons false) nil)))
{false}: (λ x (λ y y))
> ((nth zero) ((cons true) ((cons false) nil)))
{true}: (λ x (λ y x))

我认为你不能做的就是这样实现 list，因为即使你添加了特殊的魔法来表达像 list 这样的 nospread 函数，你也已经需要把它的所有参数到列表中。但我可能错了。

oa中的examples/lc.rkt有以上所有功能

从一对到 lambda 演算/方案中的列表

From a pair to a list in lambda calculus / scheme

lambda

scheme

lisp

lambda-calculus

sicp