11

だから私はRacketSchemeを使って関数型プログラミングを自分で学んでいて、今のところそれが大好きです。私自身の演習として、純粋関数型の方法でいくつかの単純なタスクを実装しようとしています。不変性は機能的なスタイルの重要な部分であることは知っていますが、それで問題ない場合があるのではないかと思いました。

ここに示すように、フィルターとともに使用すると、関数が文字列のリストから一意でない文字列を削除する楽しい方法を考えました。

(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

純粋および不純な関数型プログラミング

純粋関数は本質的に参照透過性であり、メモ化（結果のキャッシュ）が可能です。可変状態がないため、再入可能であり、リンクされたデータ構造のさまざまなバージョンでメモリを共有でき、自動並列化が可能になります。重要なのは、状態の変化を制限することで、命令型プログラミングの多くの複雑な問題について考える必要がなくなるということです。

ただし、この制限には欠点があります。1つはパフォーマンスです。一部のアルゴリズムとデータ構造（ハッシュテーブルの作成など）は、大量のデータをコピーせずに純粋関数として表現することはできません。もう1つ：純粋な関数型言語であるHaskellと比較してください。突然変異は（概念的に）存在しないため、モナドを使用して状態の変化を表す必要があります。（Haskellはかなり簡潔なdo表記の構文糖衣を提供しますが、状態モナド内のプログラミングは「通常の」Haskellとはまったく異なる言語です！）状態を変更するいくつかのインターロッキングループを使用してアルゴリズムを最も簡単に表現できる場合、Haskellの実装はより不格好になります不純な言語で可能なことよりも。

例として、XMLドキュメント内に深くネストされた単一のノードを変更します。ジッパーデータ構造を使用することは可能ですが、状態の変化なしではより困難です。擬似コードの例（純粋）：

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関数の3つのバージョン（組み込みを含む）は次のとおりです。

#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 に答える