11

所以我正在使用 Racket Scheme 自学函数式编程，到目前为止我很喜欢它。作为我自己的练习，我一直在尝试以纯粹的功能方式实现一些简单的任务。我知道不变性是函数式风格的重要组成部分，但我想知道是否有任何时候可以。

我想到了一种有趣的方法，让函数在与过滤器一起使用时从字符串列表中去除非唯一字符串，如下所示：

(define (make-uniquer)
  (let ([uniques '()])
    (lambda (x)
      (if (not (member x uniques))
          (set! uniques (cons x uniques))
          #f))))

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

如您所见，make-uniquer返回一个字符串列表的闭包以比较其唯一性，这样它就可以充当过滤器的简单谓词。但我正在破坏性地更新封闭列表。这是不好的形式，还是可以以这种方式更改局部封闭变量？

4

2 回答 2

11

纯函数式和非纯函数式编程

纯函数本质上是引用透明的，它允许记忆（缓存结果）。缺乏可变状态允许重入，允许不同版本的链接数据结构共享内存，并使自动并行化成为可能。关键是通过限制自己不受变异状态的影响，您不再需要考虑许多复杂的命令式编程问题。

然而，这种限制有缺点。一是性能：一些算法和数据结构（如构建哈希表）根本无法表达为纯函数，而无需复制大量数据。另：与纯函数式语言 Haskell 进行比较。由于突变不存在（概念上），您必须使用monad来表示状态变化。（尽管 Haskell 提供了相当简洁的do-notation 语法糖，但在状态 monad 中编程与“常规” 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函数将改变您传递给它的列表。调用者向你的函数传递一个变量并让它回来改变是很讨厌的！
  • 如果您的应用程序是多线程的，请分析、注意并记录您的非纯函数是否是线程安全的。
于 2012-08-21T03:06:00.783 回答
10

在这种情况下，我会避免使用可变实现，因为函数式实现在性能方面可以很好地竞争。以下是该函数的三个版本（包括内置的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!会损害性能，因此请谨慎使用。

于 2012-08-21T03:44:57.830 回答