再帰、リスト操作、遅延評価

関数型プログラミングの残りの 3 つの特徴 (再帰、リストの操作、遅延評価) はすぐに説明できます。

再帰

純粋な関数型言語は、変更可能なデータをサポートしていません。ループの代わりに、再帰を使用します。 Pure Functions のメタ関数は、すでにそれを示しています。コンパイル時には、ループの代わりに再帰を使用します。 C++ の階乗関数

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

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

Haskell で非常に簡単に記述できます:

リストの操作

LIS t P 処理 (LISP) は関数型プログラミング言語の特徴です。リストは一般的なデータ構造であるため、関数型言語における非常に強力な関数構成の基礎です。

リストの処理は単純なパターンに従います:

リスト処理は関数型プログラミングでは非常に慣用的であるため、リストの最初の要素と残りの要素には、(x,xs)、(head,tail)、または (car,cdr) という特別な名前が存在します。

リストを処理するためのパターンは、Haskell と C++ に直接適用できます。

まず、C++ の簡潔なバージョンです。関数 mySum は、1 から 5 までの数値を合計します。

mySum [] = 0
mySum (x:xs) = x + mySum xs
mySum [1,2,3,4,5] -- 15

これが C++ バージョンです。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

template<int ...> 
struct mySum;

template<>
struct mySum<>{
 static const int value= 0;
};

template<int head, int ... tail>
struct mySum<head,tail...>{
 static const int value= head + mySum<tail...>::value;
};

int sum= mySum<1,2,3,4,5>::value; // 15

Haskell バージョンは非常に簡単に入手できます。または？しかし、C++ 版はかなり重いです。 C++ 構文では、基本テンプレートまたは呼び出される一般テンプレートを宣言する必要があります。 4 行目から 7 行目は、空の引数リストに使用される完全に特殊化されたテンプレート (メタメタ関数) です。少なくとも 1 つのテンプレート引数が使用されている場合、部分的に特殊化されたクラス テンプレート (9 ～ 12 行目) が開始されます。3 つのドット、いわゆる楕円について少し説明させてください。これが、14 行目のクラスが任意の数の引数を取ることができる理由です。 1 行目と 9 行目の 3 つのドットは、テンプレート パラメーター パックをパックします。 10 行目と 11 行目の 3 つのドットは、関数パラメーター パックを展開します。

Haskell と C++ はパターン マッチングを適用して適切な関数を使用します。

パターン マッチング

Haskell と C++ には微妙な違いがあります。 Haskell マッチング戦略は最初のマッチングです。それが理由です。最初に特別なケースを定義する必要があります。 C++ のマッチング戦略が最適です。パターン マッチングを使用して、加算を連続して適用することにより、2 つの数値の乗算を定義できます。

簡潔にするために、最初に C++ を使用します。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

mult n 0 = 0
mult n 1 = n
mult n m = (mult n (m - 1)) + n



mult 3 2 = (mult 3 (2 - 1)) + 3
 = (mult 3 1 ) + 3
 = 3 + 3
 = 6

行 7 ～ 10 は、2 つの数値 3 と 2 の登録された乗算を示しています。行 1 は、m ==0 が成立する場合に適用されます。 m ==1 が成り立つ場合、2 行目が使用されます。一般的なケースは 3 行目です。

C++ も同様の戦略を適用します。違いは、C++ バージョンの方が冗長であり、最初に一般的なケースを定義する必要があることです。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

template <int N, int M>
struct Mult{
static const int value= Mult<N, M-1>::value + N;
};
template <int N>
struct Mult<N, 1> {
static const int value= N;
};

template <int N>
struct Mult<N, 0> {
static const int value= 0;
};

std::cout << Mult<3, 2>::value << std::endl; // 6

遅延評価

C++ での遅延評価に関する話は非常に短いものです。これは、C++20 では Eric Niebler の range ライブラリによって変更されます。 Haskell では遅延評価がデフォルトです。遅延評価とは、式が必要な場合にのみ評価されることを意味します。この戦略には 2 つの利点があります。

次のコード スニペットは、Haskell での印象的な 3 つの例を示しています。

1
2
3
4
5
6
7
8

length [2+1, 3*2, 1/0, 5-4] -- 4

successor i= i: (successor (i+1))
take 5 ( successor 1 ) -- [1,2,3,4,5]

odds= takeWhile (< 1000) . filter odd . map (^2)
[1..]= [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15 ... Control-C 
odds [1..] -- [1,9,25, ... , 841,961] 

最初の行で、引数 1/0 を含むリストの長さを計算できます。 3 行目の後続は、整数の無限シーケンスを定義します。しかし、4 行目で 5 つだけ (take 5) 要求します。したがって、すべて問題ありません。 7 行目のようにすべて整数にしたい場合は、Control-C を押して再帰を停止する必要があります。関数 odds の引数として同じ式 [1..] を使用できます。 6 行目は、Haskell での電源オフ関数の構成を示しています。ドット (.) は関数合成の記号です。少し練習すれば、6 行目の関数構成を右から左に読むことができます。 各引数に二乗関数を適用します。結果の数値が 1000 未満である限り、奇数要素が通過し、継続します。最後のリストでアプリケーションの結果を得ることができます。

C++ はデフォルトで熱心な評価を使用します。 Haskell とは異なり、式は内側から外側に向かって評価されることを意味します。 C++ には短絡評価があります。そのため、C++ は少し怠け者です。式全体が評価される前に論理式の結果が与えられた場合、C++ は式の評価を停止します。したがって、次のコード スニペットは C++ で有効ですが、1/0 は定義されていません。

if ( true or (1/0) ) std::cout << "short circuit evaluation" << std::endl;

次は?

次の投稿では、C++ の未来に足を踏み入れます。 C++17 のフォールド式は可変個引数テンプレートに基づいており、コンパイル時にフォールド アルゴリズムを適用するために使用できます。