遍历列表时反转列表与非尾递归
Reversing list vs non tail recursion when traversing lists
我想知道你，经验丰富的 lispers / 函数式程序员通常是如何决定使用什么的。比较：
(define (my-map1 f lst)
(reverse
(let loop ([lst lst] [acc '()])
(if (empty? lst)
acc
(loop (cdr lst) (cons (f (car lst)) acc))))))
和
(define (my-map2 f lst)
(if (empty? lst)
'()
(cons (f (car lst)) (my-map2 f (cdr lst)))))
问题可以这样描述：每当我们要遍历一个列表时，我们是否应该将结果收集到累加器中，它保留了尾递归，但最后需要列表反转？或者我们应该使用未优化的递归，但这样我们就不必反转任何东西？
在我看来，第一个解决方案总是更好。实际上，那里还有额外的复杂性 (O(n))。但是，它使用的内存要少得多，更不用说调用函数不会立即完成了。
但我见过使用第二种方法的不同示例。要么我遗漏了什么，要么这些例子只是教育性的。是否存在未优化的递归更好的情况？
带累加器的尾递归
- 遍历列表两次
- 构造两个列表
- 常量堆栈space
- 可能因 malloc 错误而崩溃
朴素递归
- 遍历列表两次（一次建立堆栈，一次拆除堆栈）。
- 构建一个列表
- 线性堆栈space
- 可能因堆栈溢出（在 racket 中不太可能）或 malloc 错误而崩溃
It seems to me the first solution is always better
分配通常比额外的堆栈帧更耗时，所以我认为后者会更快（不过您必须对其进行基准测试才能确定）。
Are there situations where unoptimized recursion is better?
是的，如果你正在创建一个惰性求值结构，在haskell中，你需要cons-cell作为求值边界，你不能对尾递归调用进行惰性求值。
基准测试是唯一可以确定的方法，racket 具有深堆栈框架，因此您应该能够摆脱这两个版本。
stdlib版本是，这说明如果你愿意牺牲可读性，通常可以挤出一些性能。
给定相同功能的两个实现，使用相同的 O 表示法，95% 的情况下我会选择更简单的版本。
有很多方法可以使递归保留迭代过程。
我一般直接做continuation passing style。这是我的“自然”方式。
一个考虑函数的类型。有时您需要将您的函数与其周围的函数连接起来，并且根据它们的类型，您可以选择另一种方法来进行递归。
你应该从解决“小阴谋家”开始，为它打下坚实的基础。在“小打字机”中，您可以发现另一种基于其他计算哲学的递归方式，用于 agda、coq 等语言。
在方案中，有时您可以编写实际上 haskell 的代码（您可以编写由 haskell 编译器生成的单子代码作为中间语言）。在那种情况下，递归的方式也不同于“通常”的方式等
如果可能，我会使用高阶函数，例如 map，它在底层构建一个列表。在 Common Lisp 中，我也经常使用 loop，它有一个 collect 关键字用于以正向方式构建列表（我也使用 series 库，它也透明地实现了它）。
我有时会使用非尾递归的递归函数，因为它们能更好地表达我想要的内容，而且列表的大小会相对较小；特别是写宏的时候，操作的代码一般不会很大
对于我没有收集到列表中的更复杂的问题，我通常接受为每个解决方案调用的回调函数。这确保了工作在数据的生成方式和数据使用方式之间更清楚地分开。
对我来说，这种方法是所有方法中最灵活的，因为没有对应该如何处理或收集数据做出任何假设。但这也意味着回调函数很可能会执行副作用或非本地 returns（请参见下面的示例）。只要副作用的范围很小（函数局部），我认为这不是一个特别的问题。
例如，如果我想要一个函数生成 0 到 N-1 之间的所有自然数，我写：
(defun range (n f)
(dotimes (i n)
(funcall f i)))
此处的实现迭代 N 下从 0 开始的所有值，并使用值 I 调用 F。
如果我想将它们收集在一个列表中，我会写：
(defun range-list (N)
(let ((list nil))
(range N (lambda (v) (push v list)))
(nreverse list)))
但是，我也可以通过使用队列来避免整个 push/nreverse 习惯用法。 Lisp 中的队列可以实现为一对 (first . last)，它跟踪底层链表集合的第一个和最后一个 cons 单元。这允许在恒定时间内将元素追加到末尾，因为不需要遍历列表（请参阅 在 Lisp 中实现队列，P. Norvig，1991）。
(defun queue ()
(let ((list (list nil)))
(cons list list)))
(defun qpush (queue element)
(setf (cdr queue)
(setf (cddr queue)
(list element))))
(defun qlist (queue)
(cdar queue))
因此，该函数的替代版本为：
(defun range-list (n)
(let ((q (queue)))
(range N (lambda (v) (qpush q v)))
(qlist q)))
当您不想构建所有元素时，generator/callback 方法也很有用；它有点像惰性评估模型（例如 Haskell），您只使用需要的项目。
假设您想使用 range 查找 vector 中的第一个空位置，您可以这样做：
(defun empty-index (vector)
(block nil
(range (length vector)
(lambda (d)
(when (null (aref vector d))
(return d))))))
这里，词法名称 nil 的 block 允许匿名函数调用 return 以 return 值退出块。
在其他语言中，相同的行为经常被颠倒过来：我们使用带有游标和 next 操作的迭代器对象。我倾向于认为直接编写迭代并调用回调函数更简单，但这也是另一种有趣的方法。
假二分法
您还有其他选择。在这里，我们可以通过一次遍历在列表上保留尾递归和 map。这里使用的技术称为 continuation-passing style -
(define (map f lst (return identity))
(if (null? lst)
(return null)
(map f
(cdr lst)
(lambda (r) (return (cons (f (car lst)) r))))))
(define (square x)
(* x x))
(map square '(1 2 3 4))
'(1 4 9 16)
此问题带有 racket 标记，它内置了对 delimited continuations 的支持。我们可以使用一次遍历完成 map，但这次不使用递归。享受 -
(require racket/control)
(define (yield x)
(shift return (cons x (return (void)))))
(define (map f lst)
(reset (begin
(for ((x lst))
(yield (f x)))
null)))
(define (square x)
(* x x))
(map square '(1 2 3 4))
'(1 4 9 16)
我的意图是 post 将向您展示将您的思想归类为特定结构的危害。 Scheme/Racket 的美妙之处在于，我已经了解到，任何您梦寐以求的 实现都可供您使用。
我强烈推荐 Matthew Butterick 的 Beautiful Racket。这本简单易懂且免费提供的电子书打破了您脑海中的玻璃天花板，并向您展示了如何以面向语言的方式思考您的解决方案。
我想知道你，经验丰富的 lispers / 函数式程序员通常是如何决定使用什么的。比较：
(define (my-map1 f lst)
(reverse
(let loop ([lst lst] [acc '()])
(if (empty? lst)
acc
(loop (cdr lst) (cons (f (car lst)) acc))))))
和
(define (my-map2 f lst)
(if (empty? lst)
'()
(cons (f (car lst)) (my-map2 f (cdr lst)))))
问题可以这样描述：每当我们要遍历一个列表时，我们是否应该将结果收集到累加器中，它保留了尾递归，但最后需要列表反转？或者我们应该使用未优化的递归，但这样我们就不必反转任何东西？
在我看来，第一个解决方案总是更好。实际上，那里还有额外的复杂性 (O(n))。但是，它使用的内存要少得多，更不用说调用函数不会立即完成了。
但我见过使用第二种方法的不同示例。要么我遗漏了什么，要么这些例子只是教育性的。是否存在未优化的递归更好的情况？
带累加器的尾递归
- 遍历列表两次
- 构造两个列表
- 常量堆栈space
- 可能因 malloc 错误而崩溃
朴素递归
- 遍历列表两次（一次建立堆栈，一次拆除堆栈）。
- 构建一个列表
- 线性堆栈space
- 可能因堆栈溢出（在 racket 中不太可能）或 malloc 错误而崩溃
It seems to me the first solution is always better
分配通常比额外的堆栈帧更耗时，所以我认为后者会更快（不过您必须对其进行基准测试才能确定）。
Are there situations where unoptimized recursion is better?
是的，如果你正在创建一个惰性求值结构，在haskell中，你需要cons-cell作为求值边界，你不能对尾递归调用进行惰性求值。
基准测试是唯一可以确定的方法，racket 具有深堆栈框架，因此您应该能够摆脱这两个版本。
stdlib版本是
给定相同功能的两个实现，使用相同的 O 表示法，95% 的情况下我会选择更简单的版本。
有很多方法可以使递归保留迭代过程。
我一般直接做continuation passing style。这是我的“自然”方式。
一个考虑函数的类型。有时您需要将您的函数与其周围的函数连接起来，并且根据它们的类型，您可以选择另一种方法来进行递归。
你应该从解决“小阴谋家”开始，为它打下坚实的基础。在“小打字机”中，您可以发现另一种基于其他计算哲学的递归方式，用于 agda、coq 等语言。
在方案中，有时您可以编写实际上 haskell 的代码（您可以编写由 haskell 编译器生成的单子代码作为中间语言）。在那种情况下，递归的方式也不同于“通常”的方式等
如果可能，我会使用高阶函数，例如 map，它在底层构建一个列表。在 Common Lisp 中，我也经常使用 loop，它有一个 collect 关键字用于以正向方式构建列表（我也使用 series 库，它也透明地实现了它）。
我有时会使用非尾递归的递归函数，因为它们能更好地表达我想要的内容，而且列表的大小会相对较小；特别是写宏的时候，操作的代码一般不会很大
对于我没有收集到列表中的更复杂的问题，我通常接受为每个解决方案调用的回调函数。这确保了工作在数据的生成方式和数据使用方式之间更清楚地分开。
对我来说，这种方法是所有方法中最灵活的，因为没有对应该如何处理或收集数据做出任何假设。但这也意味着回调函数很可能会执行副作用或非本地 returns（请参见下面的示例）。只要副作用的范围很小（函数局部），我认为这不是一个特别的问题。
例如，如果我想要一个函数生成 0 到 N-1 之间的所有自然数，我写：
(defun range (n f)
(dotimes (i n)
(funcall f i)))
此处的实现迭代 N 下从 0 开始的所有值，并使用值 I 调用 F。
如果我想将它们收集在一个列表中，我会写：
(defun range-list (N)
(let ((list nil))
(range N (lambda (v) (push v list)))
(nreverse list)))
但是，我也可以通过使用队列来避免整个 push/nreverse 习惯用法。 Lisp 中的队列可以实现为一对 (first . last)，它跟踪底层链表集合的第一个和最后一个 cons 单元。这允许在恒定时间内将元素追加到末尾，因为不需要遍历列表（请参阅 在 Lisp 中实现队列，P. Norvig，1991）。
(defun queue ()
(let ((list (list nil)))
(cons list list)))
(defun qpush (queue element)
(setf (cdr queue)
(setf (cddr queue)
(list element))))
(defun qlist (queue)
(cdar queue))
因此，该函数的替代版本为：
(defun range-list (n)
(let ((q (queue)))
(range N (lambda (v) (qpush q v)))
(qlist q)))
当您不想构建所有元素时，generator/callback 方法也很有用；它有点像惰性评估模型（例如 Haskell），您只使用需要的项目。
假设您想使用 range 查找 vector 中的第一个空位置，您可以这样做：
(defun empty-index (vector)
(block nil
(range (length vector)
(lambda (d)
(when (null (aref vector d))
(return d))))))
这里，词法名称 nil 的 block 允许匿名函数调用 return 以 return 值退出块。
在其他语言中，相同的行为经常被颠倒过来：我们使用带有游标和 next 操作的迭代器对象。我倾向于认为直接编写迭代并调用回调函数更简单，但这也是另一种有趣的方法。
假二分法
您还有其他选择。在这里，我们可以通过一次遍历在列表上保留尾递归和 map。这里使用的技术称为 continuation-passing style -
(define (map f lst (return identity))
(if (null? lst)
(return null)
(map f
(cdr lst)
(lambda (r) (return (cons (f (car lst)) r))))))
(define (square x)
(* x x))
(map square '(1 2 3 4))
'(1 4 9 16)
此问题带有 racket 标记，它内置了对 delimited continuations 的支持。我们可以使用一次遍历完成 map，但这次不使用递归。享受 -
(require racket/control)
(define (yield x)
(shift return (cons x (return (void)))))
(define (map f lst)
(reset (begin
(for ((x lst))
(yield (f x)))
null)))
(define (square x)
(* x x))
(map square '(1 2 3 4))
'(1 4 9 16)
我的意图是 post 将向您展示将您的思想归类为特定结构的危害。 Scheme/Racket 的美妙之处在于，我已经了解到，任何您梦寐以求的 实现都可供您使用。
我强烈推荐 Matthew Butterick 的 Beautiful Racket。这本简单易懂且免费提供的电子书打破了您脑海中的玻璃天花板，并向您展示了如何以面向语言的方式思考您的解决方案。