В этом случае я бы избегал изменяемой реализации, потому что функциональная реализация может довольно хорошо конкурировать с точки зрения производительности. Вот три версии (включая встроенную remove-duplicates) функции:

#lang racket

(define (make-uniquer)
  (let ([uniques (make-hash)])
    (lambda (x)
      (if (not (hash-ref uniques x #f))
          (hash-set! uniques x #t)
          #f))))

(define (uniquify x)
  (let ([uniquer (make-uniquer)])
    (filter uniquer x)))

(define (uniquify-2 lst)
  (define-values (_ r)
   (for/fold ([found (hash)] [result '()])
             ([elem (in-list lst)])
     (cond [(hash-ref found elem #f)
            (values found result)]
           [else (values (hash-set found elem #t)
                         (cons elem result))])))
  (reverse r))

(define randoms (build-list 100000 (λ (n) (random 10))))
(time (for ([i 100]) (uniquify randoms)))
(time (for ([i 100]) (uniquify-2 randoms)))
(time (for ([i 100]) (remove-duplicates randoms)))

;; sanity check
(require rackunit)
(check-equal? (uniquify randoms) (uniquify-2 randoms))
(check-equal? (uniquify randoms) (remove-duplicates randoms))

Время, которое я получаю за это,

cpu time: 1348 real time: 1351 gc time: 0
cpu time: 1016 real time: 1019 gc time: 32
cpu time: 760 real time: 760 gc time: 0

Не научные цифры, так что относитесь к этому с недоверием. Честно говоря, я немного настроил uniquify-2, так как моя первая версия была медленнее. Я также улучшил изменяемую версию с помощью хеш-таблицы, но, возможно, есть другие оптимизации, которые можно было бы применить. Кроме того, встроенный remove-duplicates настроен на производительность и действительно использует изменяемую структуру данных (хотя и избегает set!).

Вас также может заинтересовать статья руководства по производительности. Он указывает на то, что использование set! может нанести вред производительности, поэтому используйте его с осторожностью.

Чистое и нечистое функциональное программирование

Чистые функции по своей сути являются ссылочно прозрачный, который позволяет запоминать (кэшировать результат). Отсутствие изменяемого состояния допускает повторный вход, позволяет различным версиям связанных структур данных совместно использовать память и делает возможным автоматическое распараллеливание. Дело в том, что, ограничивая себя от изменения состояния, вам больше не нужно думать о многих сложных вопросах императивного программирования.

Однако у этого ограничения есть недостатки. Один из них - производительность: некоторые алгоритмы и структуры данных (например, построение хеш-таблицы) просто не могут быть выражены как чистые функции без необходимости копировать большие объемы данных. Другой: сравните с Haskell, чисто функциональным языком. Поскольку мутации не существует (концептуально), вы должны представлять изменения состояния с помощью монады с. (Хотя Haskell предоставляет достаточно сжатый синтаксический сахар do-нотации, программирование в монаде состояний - это совсем другой язык, чем "обычный" Haskell!) Если ваш алгоритм проще всего выразить с помощью нескольких взаимосвязанных циклов, которые изменяют состояние, реализация Haskell будет неуклюже, чем то, что возможно на нечистом языке.

Примером может служить изменение одного узла, глубоко вложенного в документ XML. Это возможно, но более сложно без мутации состояния, используя структуры данных zipper. Пример псевдокода (чистый):

old_xml = <a><b><c><d><e><f><g><h attrib="oldvalue"/></g></f></e></d></c></b></a>
// '\' is the XML selection operator
node_to_change = orig_xml \ "a" \ "b" \ "c" \ "d" \ "e" \ "f" \ "g" \ "h"
node_changed = node_to_change.copy("attrib" -> "newvalue")
new_xml = node_changed.unselect().unselect().unselect().unselect()
                      .unselect().unselect().unselect().unselect()
return new_xml

Пример (нечистый):

xml = <a><b><c><d><e><f><g><h attrib="oldvalue"/></g></f></e></d></c></b></a>
node_to_change = orig_xml.select_by_xpath("/a/b/c/d/e/f/g/h")
node_to_change.set("attrib" -> "newvalue")
return xml    // xml has already been updated

Для получения дополнительной информации о чисто функциональных структурах данных см. https://cstheory.stackexchange.com/questions/1539/whats-new-in-purely-functional-data-structures-since-okasaki. (Кроме того, часто можно написать процедурную функцию, которая управляет только внутренним состоянием, чтобы ее можно было обернуть так, чтобы она фактически была чистой функцией для вызывающих ее. Это немного проще на нечистом языке, потому что вы не нужно записать его в монаду состояния и передать runST.)

Несмотря на то, что при написании нечистого стиля вы теряете эти преимущества, некоторые другие удобства функционального программирования (например, функции высшего порядка) по-прежнему применяются.

Использование мутации

Lisp - это нечистый функциональный язык, что означает, что он допускает изменение состояния . Это сделано намеренно, поэтому, если вам нужна мутация, вы можете использовать ее, практически не используя другой язык.

Как правило, да, можно использовать мутацию состояния, когда

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

Когда вы это сделаете:

• Ясно задокументируйте, что ваша функция uniquify изменит список, который вы ей передаете. Для вызывающей стороны было бы неприятно передать вашей функции переменную и вернуть ее обратно!
• Если ваше приложение многопоточное, проанализируйте, помните и задокументируйте, является ли ваша нечистая функция потокобезопасной.