在方案中重新实现具有闭包的列表 [英] Re-implementing lists with closures in scheme

问题描述

这对我来说只是一个好奇的问题：

This is purely a curiosity question for me:

为了有趣，可以很容易地重新定义cons，car和cdr：

So for fun, one can easily redefine cons, car, and cdr like so:

(define cons+
  (lambda (a b)
    (lambda (f)
      (f a b)
  )))

(define car+
  (lambda (f)
    (f (lambda (a b) a))))

(define cdr+
  (lambda (f)
    (f (lambda (a b) b))))

$ b b

这使用闭包创建了一个列表的基本功能。在这种情况下，定义空列表的最好方法是什么？

This creates the basic functionality of a list using closures. In this context, what would be the best way to define an empty list?

推荐答案

没有 >您需要的特殊值作为空列表;你只需要一些东西，然后将其视为空列表。在Common Lisp中，列表是一个cons或符号NIL。你可以采取相同的方法，并使用符号NIL，或者你可以使用一些其他值，只要你一贯地对待。 Lisp系列中链接列表的一部分美丽（有时是丑陋）是它们是深度数据结构 。它们是由一些结构和很多约定构成的。这就是为什么我们可以使用cons单元来实现单链表，树等。

There's no particular special value that you need as the empty list; you just need something and then to treat it as the empty list. In Common Lisp, a list is either a cons or the symbol NIL. You could take the same approach and use the symbol NIL, or you could use some other value, so long as you treat it consistently. Part of the beauty (and sometimes, the ugliness) of linked lists in the Lisp families is that they are intensional data structures. They're built out of a bit of structure and a lot of convention. That's why we can use cons cells to implement singly-linked lists, tree, etc.

现在，它是什么意思，一致地对待它？其中一些将取决于你想要的行为方式。在Common Lisp中，您可以使用空列表调用汽车和 cdr ，然后返回空列表。在Scheme中，你会得到一个错误。在基于闭包的方法中，您可以调用 car + 和 cdr + 的值，而不是

Now, what does it mean to treat it consistently? Some of that will depend on exactly how you want it to behave. In Common Lisp, you can call car and cdr with the empty list, and you'll get back the empty list. In Scheme, you'll get an error. In the closure-based approach, you've got a "leaky" abstraction in the sense that you can call car+ and cdr+ with values that were not produced by cons+, and you might get a value back.

当在Lisp样式（conses和一个空列表）中实现单链表时，通常需要一个界面来检查：

When implementing singly linked lists in the Lisp styles (conses and an empty list), you typically want an interface that will let you check:

(cons? (cons ...)) == true
(empty? empty)     == true

（在这些方面，您可以实现 list？）

(In terms of those, you can implement list?)

(define (list? x)
  (or (cons? x)
      (null? x)))

在您已经完成之后，应该不难实现 cons？功能。但是空？？你在这里真的有很多自由。您可以实现空？，以便实际上有多个对象作为空列表。

After what you've already done, it shouldn't be hard to implement a cons? function. But what about empty?? You actually have a lot of freedom here. You could implement empty? such that there are actually multiple objects that serve as a empty lists. As long as the contract works, it's OK.

我们得到了有序对的工作实现，但它是一个泄漏抽象，有些事情不是 cons 创建的广告素材仍然可以无误地传递到汽车和 cdr 。你满足了公理

At the moment, you've got a working implementation of ordered pairs, but it's a leaky abstraction in that some things that weren't created with cons could still be passed to car and cdr without any error. You've satisfied the axioms

(car (cons x y)) == x
(cdr (cons x y)) == y

但不是影响

（car z）== x      ⇒     z ==（cons x _）

（cdr z）== y     ⇒     z ==（cons _ y）

(car z) == x     ⇒     z == (cons x _)
(cdr z) == y     ⇒     z == (cons _ y)

以使汽车和 cdr 只适用于由 cons 产生的内容，那么您可能会想出如何实现 cons？，您可以使用相同的技术来生成唯一的空列表对象。

If you can find a way to make those implications true, so that car and cdr only work with things produced by cons, then you can probably figure out how to implement cons?, and you can use the same technique to generate a unique empty list object.

这篇关于在方案中重新实现具有闭包的列表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！