Избегайте использования набора!в алгоритм функционального стиля программирования

Question

Я не уверен, смогу ли я задать этот вопрос здесь.Если это не то место, пожалуйста, скажите мне, и я его удалю.

Я изучаю ракетку, и кто-то сказал мне кое-что о том, как избегать использования 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))))))

Этот код работает отлично.Я должен выбрать n пунктов из списка original-list случайным образом, без повторений.А затем создайте список из двух подсписков с элементами n, выбранными в lst1, и в качестве второго подсписка оставшиеся элементы в original-list.

Есть ли лучший способ сделатьэто без использования set!?

Answer 1

Чтобы исключить использование set! и явных циклов, вам нужно использовать рекурсию, с "обновленными" значениями, передаваемыми в качестве параметров.

Схема имеет хороший синтаксический сахар около 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) ())

Ответ Оскара Лопеса - хорошее представление о более функциональномспособ сделать это.

Answer 2

Решение

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))

Кстати, set! или лучше: мутирующие функции полностью запрещены в функциональном программировании в стиле lisp.Причина в производительности.Копирование каждого длинного списка стоит дорого.Примером является nreverse Common-lisp, который изменяет порядок исходного списка (меняет порядок).Немутация reverse создает новый список с элементами в обратном порядке.Но для этого он должен скопировать.Если вы изменяете локальные переменные (определяемые let), это может привести к повышению производительности, но, конечно, очень осторожно, поскольку мутация опасна.

Answer 3

В функциональном программировании мы пишем код, составляя существующие процедуры, когда это возможно.Все операции, которые вы делаете, могут быть выражены с помощью процедур списка :

(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 избегает их любой ценой.

Обратите внимание, что мутирующих данных избегают, насколько это возможно, но Схема, будучи нечистой функциональный язык программирования позволяет это.Например, процедура shuffle должна изменить состояние в некоторой точке при выборе случайных значений.Но все это скрыто, и в обычном повседневном программировании вы можете выполнять большую часть своей работы, даже не используя set!.