使用以下规范在 LISP 中编写 Foo 函数
Writing the Foo Function In LISP With the following Specification
我正在努力寻找解决以下功能的正确方法
(FOO #'– '(1 2 3 4 5))
=> ((–1 2 3 4 5) (1 –2 3 4 5) (1 2 –3 4 5) (1 2 3 –4 5) (1 2 3 4 –5))
foo 函数的第一个参数应该是函数“-”，它必须应用于返回列表列表的每个元素，如上所示。我不确定我可以采用什么方法来创建此功能。我想到了递归，但不确定如何在每次调用中保留列表以及我会有什么样的基本标准。任何帮助，将不胜感激。我不能使用循环，因为这是函数式编程。
递归的基本情况可以通过问问自己来确定"When do I want to stop?"。
举个例子，当我想计算一个整数和它下面所有正整数的总和时，我可以通过用 "When the value I might add in is zero." 回答 "When do I want to stop?" 确定的基本情况来递归地执行此操作：
(defun sumdown (val)
(if (zerop val)
0
(+ (sumdown (1- val)) val)))
关于 'preserve the list in each call'，我不会试图保留任何东西，而是会在您进行时建立一个结果。使用 'sumdown' 示例，这可以通过各种基本相同的方法来完成。
方法是有一个带有结果参数的辅助函数，可以让你在递归时建立一个结果，以及一个供用户调用的函数，它调用辅助函数：
(defun sumdown1-aux (val result)
(if (zerop val)
result
(sumdown1-aux (1- val) (+ val result))))
(defun sumdown1 (val)
(sumdown1-aux val 0))
您可以通过使用可选参数将辅助函数和要由用户调用的函数组合起来：
(defun sumdown2 (val &optional (result 0))
(if (zerop val)
result
(sumdown2 (1- val) (+ val result))))
您可以隐藏正在使用辅助函数的事实，方法是在用户调用的函数中本地绑定它：
(defun sumdown3 (val)
(labels ((sumdown3-aux (val result)
(if (zerop val)
result
(sumdown3-aux (1- val) (+ val result)))))
(sumdown3-aux val 0)))
可以通过回答问题 "When do I want to stop when I want to operate on every element of a list?" 来确定基本情况并构建结果列表列表（而不是像示例中那样添加）来实现您的问题的递归解决方案递归。将问题分解成更小的部分会有所帮助 - "Make a copy of the original list with the nth element replaced by the result of calling the function on that element" 可以被认为是一个子问题，因此您可能希望首先编写一个函数来执行此操作，然后使用该函数编写一个解决整个问题的函数。如果你被允许使用像 mapcar 和 substitute 或 substitute-if 这样的函数会更容易，但如果你不是，那么你可以自己写出你被允许使用的等价物.
很遗憾你不能使用loop，因为这可以像这样优雅地解决：
(defun foo (fctn lst)
(loop
for n from 0 below (length lst) ; outer
collect (loop
for elt in lst ; inner
for i from 0
collect (if (= i n) (funcall fctn elt) elt))))
所以我们有一个外部循环将 n 从 0 递增到 (length lst) excluded，还有一个内部循环将逐字复制列表，除了元素 [=14] =] 其中 fctn 应用：
CL-USER> (foo #'- '(1 2 3 4 5))
((-1 2 3 4 5) (1 -2 3 4 5) (1 2 -3 4 5) (1 2 3 -4 5) (1 2 3 4 -5))
Replacing loop by recursion 就是用labels创建局部函数，替换内循环和外循环，例如：
(defun foo (fctn lst)
(let ((len (length lst)))
(labels
((inner (lst n &optional (i 0))
(unless (= i len)
(cons (if (= i n) (funcall fctn (car lst)) (car lst))
(inner (cdr lst) n (1+ i)))))
(outer (&optional (i 0))
(unless (= i len)
(cons (inner lst i) (outer (1+ i))))))
(outer))))
您在此处选择的部分实施策略将取决于您是否要支持结构共享。一些答案提供了解决方案，您可以在其中获得全新的列表，这可能正是您想要的。如果你真的想共享一些共同的结构，你也可以这样做，使用这样的解决方案。 （注意：我使用 first/rest/list* 而不是 car/car/cons，因为我们使用的是列表，而不是任意树。）
(defun foo (operation list)
(labels ((foo% (left right result)
(if (endp right)
(nreverse result)
(let* ((x (first right))
(ox (funcall operation x)))
(foo% (list* x left)
(rest right)
(list* (revappend left
(list* ox (rest right)))
result))))))
(foo% '() list '())))
我们的想法是沿着 list 走一次，在我们经过它们时跟踪左侧（反向）和右侧，所以我们得到左和右：
() (1 2 3 4)
(1) (2 3 4)
(2 1) (3 4)
(3 2 1) (4)
(4 3 2 1) ()
在除最后一步之外的每一步中，我们从右侧取第一个元素，应用操作，并使用 revappend 和 left[=37= 创建一个新列表]，运算的结果，剩下的对。所有这些操作的结果都累积在 result 中（以相反的顺序）。最后，我们简单的returnresult，反了过来。我们可以检查结果是否正确，同时观察结构共享：
CL-USER> (foo '- '(1 2 3 4 5))
((-1 2 3 4 5) (1 -2 3 4 5) (1 2 -3 4 5) (1 2 3 -4 5) (1 2 3 4 -5))
通过设置*print-circle*为true，我们可以看到结构共享：
CL-USER> (setf *print-circle* t)
T
CL-USER> (let ((l '(1 2 3 4 5)))
(list l (foo '- l)))
((1 . #1=(2 . #2=(3 . #3=(4 . #4=(5))))) ; input L
((-1 . #1#)
(1 -2 . #2#)
(1 2 -3 . #3#)
(1 2 3 -4 . #4#)
(1 2 3 4 -5)))
输出中的每个列表尽可能与原始输入列表共享结构。
我发现从概念上讲，使用 标签 更容易递归地编写一些此类函数，但 Common Lisp 不保证尾调用优化，因此值得编写这也是迭代的。这是可以完成的一种方法：
(defun phoo (operation list)
(do ((left '())
(right list)
(result '()))
((endp right)
(nreverse result))
(let* ((x (pop right))
(ox (funcall operation x)))
(push (revappend left (list* ox right)) result)
(push x left))))
我正在努力寻找解决以下功能的正确方法
(FOO #'– '(1 2 3 4 5))
=> ((–1 2 3 4 5) (1 –2 3 4 5) (1 2 –3 4 5) (1 2 3 –4 5) (1 2 3 4 –5))
foo 函数的第一个参数应该是函数“-”，它必须应用于返回列表列表的每个元素，如上所示。我不确定我可以采用什么方法来创建此功能。我想到了递归，但不确定如何在每次调用中保留列表以及我会有什么样的基本标准。任何帮助，将不胜感激。我不能使用循环，因为这是函数式编程。
递归的基本情况可以通过问问自己来确定"When do I want to stop?"。
举个例子，当我想计算一个整数和它下面所有正整数的总和时，我可以通过用 "When the value I might add in is zero." 回答 "When do I want to stop?" 确定的基本情况来递归地执行此操作：
(defun sumdown (val)
(if (zerop val)
0
(+ (sumdown (1- val)) val)))
关于 'preserve the list in each call'，我不会试图保留任何东西，而是会在您进行时建立一个结果。使用 'sumdown' 示例，这可以通过各种基本相同的方法来完成。
方法是有一个带有结果参数的辅助函数，可以让你在递归时建立一个结果，以及一个供用户调用的函数，它调用辅助函数：
(defun sumdown1-aux (val result)
(if (zerop val)
result
(sumdown1-aux (1- val) (+ val result))))
(defun sumdown1 (val)
(sumdown1-aux val 0))
您可以通过使用可选参数将辅助函数和要由用户调用的函数组合起来：
(defun sumdown2 (val &optional (result 0))
(if (zerop val)
result
(sumdown2 (1- val) (+ val result))))
您可以隐藏正在使用辅助函数的事实，方法是在用户调用的函数中本地绑定它：
(defun sumdown3 (val)
(labels ((sumdown3-aux (val result)
(if (zerop val)
result
(sumdown3-aux (1- val) (+ val result)))))
(sumdown3-aux val 0)))
可以通过回答问题 "When do I want to stop when I want to operate on every element of a list?" 来确定基本情况并构建结果列表列表（而不是像示例中那样添加）来实现您的问题的递归解决方案递归。将问题分解成更小的部分会有所帮助 - "Make a copy of the original list with the nth element replaced by the result of calling the function on that element" 可以被认为是一个子问题，因此您可能希望首先编写一个函数来执行此操作，然后使用该函数编写一个解决整个问题的函数。如果你被允许使用像 mapcar 和 substitute 或 substitute-if 这样的函数会更容易，但如果你不是，那么你可以自己写出你被允许使用的等价物.
很遗憾你不能使用loop，因为这可以像这样优雅地解决：
(defun foo (fctn lst)
(loop
for n from 0 below (length lst) ; outer
collect (loop
for elt in lst ; inner
for i from 0
collect (if (= i n) (funcall fctn elt) elt))))
所以我们有一个外部循环将 n 从 0 递增到 (length lst) excluded，还有一个内部循环将逐字复制列表，除了元素 [=14] =] 其中 fctn 应用：
CL-USER> (foo #'- '(1 2 3 4 5))
((-1 2 3 4 5) (1 -2 3 4 5) (1 2 -3 4 5) (1 2 3 -4 5) (1 2 3 4 -5))
Replacing loop by recursion 就是用labels创建局部函数，替换内循环和外循环，例如：
(defun foo (fctn lst)
(let ((len (length lst)))
(labels
((inner (lst n &optional (i 0))
(unless (= i len)
(cons (if (= i n) (funcall fctn (car lst)) (car lst))
(inner (cdr lst) n (1+ i)))))
(outer (&optional (i 0))
(unless (= i len)
(cons (inner lst i) (outer (1+ i))))))
(outer))))
您在此处选择的部分实施策略将取决于您是否要支持结构共享。一些答案提供了解决方案，您可以在其中获得全新的列表，这可能正是您想要的。如果你真的想共享一些共同的结构，你也可以这样做，使用这样的解决方案。 （注意：我使用 first/rest/list* 而不是 car/car/cons，因为我们使用的是列表，而不是任意树。）
(defun foo (operation list)
(labels ((foo% (left right result)
(if (endp right)
(nreverse result)
(let* ((x (first right))
(ox (funcall operation x)))
(foo% (list* x left)
(rest right)
(list* (revappend left
(list* ox (rest right)))
result))))))
(foo% '() list '())))
我们的想法是沿着 list 走一次，在我们经过它们时跟踪左侧（反向）和右侧，所以我们得到左和右：
() (1 2 3 4)
(1) (2 3 4)
(2 1) (3 4)
(3 2 1) (4)
(4 3 2 1) ()
在除最后一步之外的每一步中，我们从右侧取第一个元素，应用操作，并使用 revappend 和 left[=37= 创建一个新列表]，运算的结果，剩下的对。所有这些操作的结果都累积在 result 中（以相反的顺序）。最后，我们简单的returnresult，反了过来。我们可以检查结果是否正确，同时观察结构共享：
CL-USER> (foo '- '(1 2 3 4 5))
((-1 2 3 4 5) (1 -2 3 4 5) (1 2 -3 4 5) (1 2 3 -4 5) (1 2 3 4 -5))
通过设置*print-circle*为true，我们可以看到结构共享：
CL-USER> (setf *print-circle* t)
T
CL-USER> (let ((l '(1 2 3 4 5)))
(list l (foo '- l)))
((1 . #1=(2 . #2=(3 . #3=(4 . #4=(5))))) ; input L
((-1 . #1#)
(1 -2 . #2#)
(1 2 -3 . #3#)
(1 2 3 -4 . #4#)
(1 2 3 4 -5)))
输出中的每个列表尽可能与原始输入列表共享结构。
我发现从概念上讲，使用 标签 更容易递归地编写一些此类函数，但 Common Lisp 不保证尾调用优化，因此值得编写这也是迭代的。这是可以完成的一种方法：
(defun phoo (operation list)
(do ((left '())
(right list)
(result '()))
((endp right)
(nreverse result))
(let* ((x (pop right))
(ox (funcall operation x)))
(push (revappend left (list* ox right)) result)
(push x left))))