不変データ

純粋関数型言語の鍵は、そのデータが不変であることです。したがって、x=x+1 や ++x などの代入は、純粋関数型言語 Haskell では使用できません。その結果、Haskell は for、while、until などのループをサポートしていません。それらは、ループ変数の変更に基づいています。 Haskell は既存のデータを変更しません。 Haskell は必要に応じて新しいデータを作成し、古いデータを再利用します。

不変データ

不変データには優れた特性があります。これらは、データ競合の必要条件を欠いているため、暗黙的にスレッドセーフです。データ競合とは、少なくとも 2 つのスレッドが同時に共有データにアクセスし、少なくとも 1 つのスレッドがライターである状態です。

Haskell でのクイックソート

Haskell のクイックソート アルゴリズムは、データの不変性を非常によく示しています。

qsort [] = []
qsort (x:xs) = qsort [y | y <- xs, y < x] ++ [x] ++ qsort [y | y <- xs, y >= x]

クイックソート アルゴリズム qsort は、2 つの関数定義で構成されます。最初の行では、空のリストにクイックソートが適用されます。もちろん、結果は空のリストです。 2 行目には、リストが少なくとも 1 つの要素 x:xs で構成される一般的なケースがあります。 x はリストの最初の要素であり、xs は規則によるリマインダーです。

クイックソート アルゴリズムの戦略は、Haskell に直接適用できます。

  • リスト x の最初の要素、いわゆるピボット要素を使用して、そこから 1 つの要素を含むリストを作成します:... [x] ...
  • リスト [x] の前に、x より小さいすべての要素を追加 (++) します。 y <- xs, y
  • リスト [x] の後に x 以上のすべての要素を追加 (++):...[x] ++ (qsort [y | y <- xs, y>=x])
  • 空のリストにクイックソートが適用されると、再帰は終了します。

確かに、命令的な目は Haskell の簡潔さに慣れていません。

このアルゴリズムの重要な点は、再帰ごとに新しいリストが作成されることです。 C または C++ での実装はどのようになりますか?

C++ でのクイックソート

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
void quickSort(int arr[], int left, int right) { 
 int i = left, j = right; 
 int tmp; 
 int pivot = arr[abs((left + right) / 2)]; 
 while (i <= j) { 
 while (arr[i] < pivot) i++; 
 while (arr[j] > pivot) j--; 
 if (i <= j) { 
 tmp = arr[i]; 
 arr[i] = arr[j]; 
 arr[j] = tmp; 
 i++; j--; 
 }
 }
 if (left < j) quickSort(arr, left, j);
 if (i < right) quickSort(arr, i, right);
}

心配ない。アルゴリズムの説明はしません。私には簡単な観察で十分です。要素は行 9 ~ 11 で上書きされます。アルゴリズムはその場で機能するため、変更可能なデータが必要です。関数型プログラミングには、この上書きに適した用語があります:destructive 割り当て。

正直なところ、これは C でのクイックソート アルゴリズムの実装でした。C++ では、std::partition を使用すると、よりうまく処理できます。

template <class ForwardIt>
 void quicksort(ForwardIt first, ForwardIt last)
 {
 if(first == last) return;
 auto pivot = *std::next(first, std::distance(first,last)/2);
 ForwardIt middle1 = std::partition(first, last, 
 [pivot](const auto& em){ return em < pivot; });
 ForwardIt middle2 = std::partition(middle1, last, 
 [pivot](const auto& em){ return !(pivot < em); });
 quicksort(first, middle1);
 quicksort(middle2, last);
 }

しかし、もう一度。重要な点は、std::partition で破壊的な代入も使用することです。 よく見ると、C++ バージョンの戦略は Haskell バージョンとあまり変わらない.

C++ の不変性についての話は何ですか?

C++ の不変データ

C++ での不変データの使用法は、プログラマーの規律に基づいています。定数データ、テンプレート メタプログラミング、および定数式には、不変性を表す 3 つの方法があります。オプション 1 と 2 は非常に簡単に提示できますが、定数式はもっと注意する必要があります。

定数データ

const int value=1; 命令を使用する。値は不変データになります。

テンプレート メタプログラミング

テンプレートのメタプログラミングはコンパイル時に行われます。コンパイル時に変更はありません。したがって、コンパイル時に計算されるすべての値は不変です。もちろん、これはコンパイル時の Factorial::5 の計算にも当てはまります。

template <int N>
struct Factorial{
 static int const value= N * Factorial<N-1>::value;
};

template <>
struct Factorial<1>{
 static int const value = 1;
};

std::cout << Factorial<5>::value << std::endl;
std::cout << 120 << std::endl;

テンプレート プログラミングへの短い通知が短すぎた場合は、記事「C++98 の機能」をお読みください。

しかしここで、C++ の未来、つまり定数式に話を戻します。

定数式

C++11 は定数式をサポートしています。 C++14 では、通常の関数とほぼ同じように動作する定数式として関数を宣言できます。

C++ は、変数、ユーザー定義型、および関数の 3 つのバリエーションで定数式をサポートしています。定数式の特別な点は、コンパイル時に評価できることです。

<オール>
  • constexpr double pi=3.14 を使用すると、pi は定数式になります。したがって、pi は暗黙的な const であり、定数式で初期化する必要があります:3.14.
  • ユーザー定義型のインスタンスが定数式になるように、ユーザー定義型にはいくつかの制限があります。たとえば、コンストラクターは空で定数式でなければなりません。インスタンスは、定数式であるメソッドのみを使用できます。もちろん、コンパイル時に仮想メソッドを呼び出すことはできません。ユーザー定義型がすべての要件を満たしている場合は、コンパイル時にそのオブジェクトをインスタンス化して使用できます。
  • コンパイル時に C++14 で関数を実行するには、いくつかの規則に従う必要があります。まず、それらの引数は定数式でなければなりません。次に、静的データまたはスレッドローカル データを使用できません。
  • 次の例は、定数式にどのような力があるかを示しています。ユーザー定義のリテラルを使用して、コンパイル時にすべての距離を計算します。

     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    // userdefinedLiteralsConstexpr.cpp
    
    #include <iostream>
    
    namespace Distance{
    
     class MyDistance{
     public:
     constexpr MyDistance(double i):m(i){}
    
     friend constexpr MyDistance operator+(const MyDistance& a, const MyDistance& b){
     return MyDistance(a.m + b.m);
     }
     friend constexpr MyDistance operator-(const MyDistance& a,const MyDistance& b){
     return MyDistance(a.m - b.m);
     }
     
     friend constexpr MyDistance operator*(double m, const MyDistance& a){
     return MyDistance(m*a.m);
     }
     
     friend constexpr MyDistance operator/(const MyDistance& a, int n){
     return MyDistance(a.m/n);
     }
     
     friend std::ostream& operator<< (std::ostream &out, const MyDistance& myDist){
     out << myDist.m << " m";
     return out;
     }
     private:
    double m; }; namespace Unit{ constexpr MyDistance operator "" _km(long double d){ return MyDistance(1000*d); } constexpr MyDistance operator "" _m(long double m){ return MyDistance(m); } constexpr MyDistance operator "" _dm(long double d){ return MyDistance(d/10); } constexpr MyDistance operator "" _cm(long double c){ return MyDistance(c/100); } } } constexpr Distance::MyDistance getAverageDistance(std::initializer_list<Distance::MyDistance> inList){ auto sum= Distance::MyDistance{0.0}; for (auto i: inList) sum = sum + i ; return sum/inList.size(); } using namespace Distance::Unit; int main(){ std:: cout << std::endl; constexpr auto work= 63.0_km; constexpr auto workPerDay= 2 * work; constexpr auto abbrevationToWork= 5400.0_m; constexpr auto workout= 2 * 1600.0_m; constexpr auto shopping= 2 * 1200.0_m; constexpr auto distPerWeek1= 4*workPerDay-3*abbrevationToWork+ workout+ shopping; constexpr auto distPerWeek2= 4*workPerDay-3*abbrevationToWork+ 2*workout; constexpr auto distPerWeek3= 4*workout + 2*shopping; constexpr auto distPerWeek4= 5*workout + shopping; constexpr auto averageDistance= getAverageDistance({distPerWeek1,distPerWeek2,distPerWeek3,distPerWeek4}); std::cout << "averageDistance: " << averageDistance << std::endl; // 255900 m std::cout << std::endl; }

    定数式とユーザー定義リテラルについて詳しく説明することは繰り返しません。 constexpr およびユーザー定義リテラルへの投稿で既に実行しています。私は 2 つの観察だけをしたいと思います:

    <オール>
  • constexpr 宣言により、すべての変数、MyDistance クラスのインスタンス、および関数が定数式になります。したがって、コンパイラはコンパイル時に必要な操作を実行します。
  • すべての変数、インスタンス、および関数 (std::cout を除く) は定数式です。つまり、コンパイル時にプログラム全体が実行されます。したがって、使用されるすべての変数とインスタンスは不変です。 77 行目のプログラム 255900 m の出力のみが実行時に実行されます。
  • 次は?

    純粋関数は、数学関数に非常に似ています。 Haskell とテンプレートのメタプログラミングが純粋な関数型言語と呼ばれる理由です。しかし、純粋に関数型の言語が戦わなければならない制限は何ですか?これらは、次の投稿のトピックになります。