lisp - 如何定义一个以两种不同方式返回一半输入的函数？

Question

我正在阅读符号计算的简要介绍，它问了这个问题。基本上，前面的内容涉及以小函数组成大函数。 (比如 2- 将由两个 1-(lisp 的递减运算符)组成)

因此，其中一个问题是定义返回一半输入的函数 HALF 的两种不同方法是什么。我已经能够想出一个明显的方法(将数字除以 2)，但随后就卡住了。我正在考虑从数字本身中减去一半来得到一半但是前半部分也必须计算......(我不认为作者打算这么快在书中引入递归，所以我很可能错误的)。

所以我的问题是另一种方式是什么？而且只有两种方法吗？

编辑:示例 HALF(5) 给出 2.5

P.S - 这本书涉及 LISP 的教学，我对此一无所知，但显然特别倾向于使用较小的 block 来构建更大的 block ，所以请尝试使用这种方法来回答。

P.P.S - 到目前为止我发现了这个，但它是关于一个完全不同的主题 - How to define that float is half of the number?此处提供本书的 PDF - http://www.cs.cmu.edu/~dst/LispBook/book.pdf (ctrl+f "两种不同的方式")

Answer 1

您似乎在描述 peano arithmetic .在实践中，它的工作方式与使用杯子和水桶对流体进行计算的方式相同。

您通过从源中取出杯子到目标桶中添加，直到源为空。乘法和除法只是高级的加法和减法。要减半，您需要从源中取出两个桶进行更改，直到源为空。当然，这将执行 ceil 或 floor，具体取决于您选择用作答案的桶。

(defun halve (x)
  ;; make an auxillary procedure to do the job
  (labels ((loop (x even acc)
             (if (zerop x)
                 (if even (+ acc 0.5) acc)
                 (loop (- x 1) (not even) (if even (+ acc 1) acc)))))
    ;; use the auxillary procedure
    (loop x nil 0)))

最初我提供了一个 Scheme 版本(因为你刚刚标记了 lisp)

(define (halve x)
  (let loop ((x x) (even #f) (acc 0))
    (if (zero? x)
        (if even (+ acc 0.5) acc)
        (loop (- x 1) (not even) (if even (+ acc 1) acc)))))