避免在函数式编程风格的算法中使用set！

Question

我不确定我是否可以在这里提出这个问题。如果这不是正确的地方，请告诉我，我会删除它。

我正在学习Racket，有人告诉我在函数式编程风格中要避免使用set！。但我很困惑，我不理解“函数式编程风格”的含义。只是为了学习，我想问这个问题。

我有以下代码：

 (define lst1 '())

 (do ([i n (- i 1)])
   ((zero? i))
   ; Get an item.
   (set! item (random-chooser original-list))
   ; Insert it into an auxiliary list, lst1
   (set! lst1 (cons item lst1))
   ; Remove the item from the original list
   (set! original-list (remove item original-list)))

 (append (list lst1) (list original-list))))))

这段代码运行良好。我需要随机选择original-list列表中的n个项，且不重复，并创建一个具有两个子列表的列表，其中lst1包含选定的n个项，第二个子列表包含original-list中剩余的项。

是否有更好的方法来完成此操作，而不使用set!？

- VansFannel

---

你的编辑实际上使得三个答案中有两个无效了。据我理解，我们在SO上不应该这样做。我觉得有必要回滚你的编辑。:) 你可以随时提出一个新问题，附带更改后的要求。 :) - Will Ness

@WillNess 如果我问另一个类似于这个问题的问题，我会得到很多负评，因为人们会认为它是重复的。 - VansFannel

但这不是重复的。在这里，您要求随机选择k个值，在那里您需要指定必须使用用户提供的函数。还要包括此问题的链接作为背景。 - Will Ness

这个问题已经关闭（因为我有一个答案），但我想知道如何避免使用 set!。感谢您的评论。 - VansFannel

Answer 1

为了消除对set!和明确循环的使用，您需要使用递归，并将“更新”的值作为参数传递。

Scheme在letrec（递归let，用于可以引用自身的绑定）周围拥有一些不错的语法糖，这允许您创建并一起调用函数：命名为let。这经常用于循环，因此该函数通常称为loop，但也可以称为其他任何名称。重要的是在循环时使用修改后的参数调用它，而在循环结束时不要调用它。

(define (take-random n lst)
  ; Syntactic sugar that creates a 3-parameter function called `loop` and calls it
  ; with the values `n`, `'()` and `lst`
  (let loop ((n n)
             (picked '())
             (lst lst))
    ; If the loop counter reaches zero or if there are no more items to take
    (if (or (zero? n) (null? lst))
        ; Then combine the picked items and the remaining unpicked items
        (list picked lst)
        ; Otherwise, pick a random item from the list
        (let ((item (random-chooser lst)))
          ; And loop again, decreasing the loop counter to be nearer zero,
          ; adding the picked item to the list of picked items, and removing
          ; it from the list of remaining items to pick from
          (loop (- n 1)
                (cons item picked)
                (remove item lst))))))

;; Examples
(take-random 3 '(1 2 3 4 5 6))
; => ((4 1 6) (2 3 5))
(take-random 3 '(1 2))
; => ((2 1) ())

Óscar López的回答是更加功能化的方法的好演示。

- Billy Brown

---

谢谢你的回答。我已经问了另一个关于何时使用define和何时使用let的问题，链接为https://dev59.com/uLDla4cB1Zd3GeqP50kw。我看到你的回答中只使用`define`来定义函数，在函数体中使用`let`。 - VansFannel

Answer 2

在函数式编程中，我们尽可能地通过组合现有的程序来编写代码。您正在执行的所有操作都可以使用列表过程来表达：

(define n 5)
(define lst '(0 1 2 3 4 5 6 7 8 9))

(let ((shuffled (take (shuffle lst) n)))
  (list shuffled (remove* shuffled lst)))

=> '((5 8 9 6 2) (0 1 3 4 7))

最终你将得到两个列表，第一个包含从原始列表中随机选择的n个元素，第二个包含剩余的元素。

在函数式编程中，我们努力避免显式循环（使用递归代替）和set!。我们使用现有的过程、组合以及创建新数据结构（比如列表），而不是修改现有数据。

我可以看出你来自面向过程的背景，放弃循环和赋值可能有点困难，但这就是函数式编程的美妙之处：它让你以不同的方式思考问题。数据的变异是许多困难的根源，特别是在并发编程时，因此FP会尽一切可能避免它。

请注意，尽可能避免数据突变，但Scheme作为一种杂凑型函数式编程语言是允许的。例如，shuffle过程必须在某个时候更改状态以选择随机值。但这已经封装好了，在日常编程中，大部分工作都可以在不使用set!的情况下完成。

- Óscar López

---

谢谢您的回答，它给了我很大的帮助！但是我不知道如何使用您的示例将random-chooser变为更加函数式的样式，因为它是我自己的函数，而且它与(take (shuffle lst) n)不适配。 - VansFannel

我明白，你在random-chooser上有一个外部依赖。很遗憾，每次只能删除一个元素，这迫使我们进行循环。Billy的解决方案很好，正如你所看到的，它使用递归进行循环并避免了set!。我更喜欢我的版本 :) 但是如果你“必须”使用那个其他过程，我无法改进它。我认为需要使用random-chooser使解决方案在风格上不够函数化。 - Óscar López

在输入中存在重复项的情况下，使用“remove”是不正确的。简单的“drop n”就足够了，或者更好的方法是将“take+drop”融合成一个函数，同时返回列表的两个部分（就像Haskell的“splitAt”一样）。然后，在严格语言中，使用“shuffle”执行多余的工作，随机选择输入中的所有元素，而不仅仅是n。如果有重复项，则也是不正确的，因为Q是关于“无重复地”选择n*个元素的，但“shuffle”显然纯粹是位置性的。/抱歉/ :) - Will Ness

@ÓscarLópez 啊，这样就有意义多了。也许他们的意思确实是不要在同一个位置选择超过一次。我太过字面理解了 :/ 使用洗牌算法是正确的，甚至看起来很巧妙；但仍然会对（随机）进行太多调用（内部推测）。 :) - Will Ness

@WillNess，@ÓscarLópez。也许我应该选择一个更通用的函数名称，比如function1，而不是random-chooser。 - VansFannel

Answer 3

解决方案

shuffle 是一个非常好的解决方案，而且非常实用。函数式编程禁止改变已定义变量的值（因此不能使用 set!），而是创建/复制一个现有对象并对其进行变异或以变异形式创建它。 shuffle 会按照变异顺序创建/复制原始列表。

您可以使用 take 和 drop 来获取或留下任何列表的前 n 个位置。或者使用 split-at 函数。

然而，由于这将结果作为值返回，但任务是返回一个列表，因此您可以使用 let-values 将两个返回结果绑定并将它们绑定到单个列表中。

(define (choose-n-and-rest lst n)
  (let-values ([(chosen rest) (split-at (shuffle lst) n)])
    (list chosen rest)))

或者：

(define (choose-n-and-rest lst n)
  (let ((new-lst (shuffle lst)) ; so that `take` & `drop` use the same shuffled list
    (list (take new-list n) (drop new-list n))))

但是正如您可以在这里阅读到的那样，split-at可能比take和drop的组合略微更有效。

请尝试使用以下内容：

(choose-n-and-rest '(a b c d e 1 2 3 4 5) 3) 
;; e.g. '((a 4 2) (1 b 3 5 c e d))

顺便说一下，在Lisp式的函数编程中，set！或更好的：变异函数不是完全禁止的。原因是性能。复制每个冗长的列表都很昂贵。一个例子是Common Lisp的nreverse，它改变了原始列表的顺序（倒置顺序）。非变异的reverse创建一个按相反顺序排列元素的新列表。但是为此必须进行复制。如果您变异局部变量（由let定义），这可能会导致性能提高——当然非常谨慎，因为变异是一件危险的事情。

- Gwang-Jin Kim