地図、フィルタ、Cの減少:ポインタを使用している再帰的な高次の機能

機能プログラミングの旅は、二重の側面を持っている:概念を理解するパラダイムを理解し、日常の作業で実際にそれを適用する.プログラマのための現在の一般的なツールで働くとき、しかし、我々は通常Haskellと機能Lispの不可解な知識から遠くに取り除かれます.時々、私たちがしなければならないことは、PythonやJavaScriptのように、私たちが日々使っている言語の機能的なスタイルでプログラムする方法を見つけることです.
通常、これは3つのテクニックで始まります.そして、心が再帰的で高次の機能のような機能的なプログラミング基礎に使用される誰かのために単純であるけれども、ループと可変変数代入のために命令的なスタイルに慣れている誰かのために挑戦することができます.これらのテクニックは、「ブランク」のチュートリアルで最も機能しています.

map(function,list):要素が引数のリストの要素への関数のアプリケーションの結果である新しいリストを生成します

filter(function,list):要素が要素のアプリケーションが真を返す位置にある新しいリストを生成します.

縮小:アキュムレータ上のすべての要素に関数のアプリケーションの結果を生成します.

これらは高次の関数である.

list = 1 2 3 4 5 6

f(x) = x + 2    
map(f, list) = 3 4 5 6 7 8

g(x) = x > 3
filter(g, list) = 4 5 6

h(x,y) = x + y
reduce(h, list) = 21

本稿では、Cプログラミング言語でこの機能を実装しようとしています.これは、この言語でのプログラミングの深刻なスタイルのための勧告ではない、これは単なる運動であることに注意してください.

Cにおける機能ツールの実装に関する考察

Cでこれらの機能ツールを実装しようとする前に、私たちが考えなければならないことがいくつかあります.
まず、関数型プログラミングにおいて、データは不変であることを意味しなければならない.したがって、私たちの関数が変数とデータ構造の値を変更しないことを確認しなければなりませんが、新しい変数とデータ構造を作成します.
第二に、Cでは、関数は最初のクラスオブジェクトではないと考えなければなりません.関数の内部で定義されていて、関数から返されたり、引数として関数に渡されたりすることはできません.私たちは、データ構造の値に適用される関数を持つ関数を見つける方法を見つける必要があります.

連結リストの実装

再帰的なアルゴリズムが再帰的に定義されたデータ構造で最もよく働くというのは一般的な規則です.
リンクリストはノードのチェーンです.そして、それぞれは値と次のノードへのリファレンス(したがってリストの残りに)を含みます.
LISPから借りられた機能プログラミングでは、私たちはconsセル(1つの要素(A、B))に関してリンクリストを定義することができます.
我々のツール--マップ、フィルタ、縮小--再帰的な高次関数であるので、反復するリストが再帰的に定義されるのは当然です.最初のステップはデータ型を定義することです.
リンクリストの各要素をstruct Node 2つの値を含むint data , ノードそのものの値Node *next , 連鎖内の次のノードへのポインター.すべてのノードは、次のノードを指します.最後の要素は、最後の要素を指します.
また、我々はcons 関数は、リンクリストを作成することができます.それは整数値とリストをそれに加えるために受けて、ノードのためにメモリのスペースを割り当てて、そのデータとして値を割り当てて、ポインティングによってノードをリストに入れますnext にhead リストの

/* functional.h */
typedef struct Node {
  int data;
  struct Node* next;
} Node;

Node *cons(int, Node *);

/* linkedlist.c */
#include "functional.h"
#include <stdlib.h>

Node *cons(int el, Node *n){
  Node *node = (Node *) (malloc(sizeof(Node)));
  node->data = el;
  node->next = n;

  return node;
 }

リンクリストは、最初のノード自体としてではなく、最初のノード名へのポインタとして定義されます.明示的にするには、型定義をtypedef *Node Linkedlist , ここでLinkedListはリンクリストの最初のノードへのポインタである.

関数ポインタを引数として渡すための関数ポインタの使用

ラムダ関数は関数型プログラミングに必須です.なぜなら、関数から渡されて関数から返される関数オブジェクトを作成するための明確な構文を提供するからです.例えば、Haskellで書くことができます\x -> x + 3 関数を作成するには、メインのプログラムとは別に名前を付けたり書いたりする必要はありません.
残念ながら、私たちはCでその贅沢を持っていません.言語は他の関数の中で関数を書き、引数として渡すか、関数の結果として返すことを許しません.したがって、関数を通過する別の方法を見つけなければなりません.
Cが提供する1つのものすごいことは関数ポインタ、関数のメモリアドレスへのポインタです.これにより関数のアドレスを引数として渡すことができます.例えば、我々は関数を作成することができますapply これは関数(または関数へのポインタ)と値をとり、その関数を値に適用した結果を返します.

/* functional.h */
typedef int (*fp) (int);
typedef int (*gp) (int, int);

int apply(fp, int);

/* apply.c */
#include "functional.h"    
int apply(fp fp, int x){
  return (*fp)(x)
}

このデバイスを使用すると、変数に対して異なる操作を行うことができますapply .

再帰的反復子の実装

我々は2つの考慮事項に対処し、現在3つの高次機能を定義することができます:マップ、フィルタ、および減少.再帰的に定義されたデータ構造を再帰的に計算することを覚えているなら、実装するのはとても簡単です.
つの関数はリストの最初の要素をとりますhead ), 関数を適用し、次の要素を計算するtail ) それがNILポインターに達するまで、結果によって、再帰的に、そのポイントで、リストは使い果たされます、そして、計算は止まります.
より詳細にそれらを実行して、探検しましょう.

マップ

マップは、関数とリンクリストを受け取り、リストの各要素に関数を適用することで、新しいリンクリストを生成します.

/* functional.h */
Node *map(fp, Node *);

/* iterators.c */
Node *map(fp fp, Node *n){
  if (n == 0) return 0;
  int val = (*fp)(n->data);
  return cons(val, map(fp, n->next));
} 

リストの先頭の値をとり、引数で指定された関数を適用しますfp , and cons の結果を再帰的なアプリケーションでビルドする新しいリストにmap を返します.
私たちに渡すことができるいくつかの異なる機能を定義しようmap , 変換されたリンクリストを作成します.

/* functional.h */
int addThree(int);
int doDouble(int);
int toFour(int);

/* main.c */
int main(){
  Node *src = seq(1, 5, NULL);
  Node *li = map(&addThree, source);
  Node *lj = map(&doDouble, source);
  Node *lk = map(&toFour, source);

printlist(li); // prints 4 5 6 7 8
printlist(lj); // prints 2 4 6 8 10
printlist(lk); // prints 4 4 4 4 4

  return 0;
}

int addThree(int x) {
  return x + 3;
}
int doDouble(int x){ 
  return x * 2;
}
int toFour(int x){
  return 4;
}

フィルタ

フィルタは関数とリンクリストを受け取り、引数の各要素に関数を適用することで、新しいリンクリストを生成します.

/* functional.h */
Node *filter(fp, Node *);

/* iterators.c */
Node *filter(fp fp, Node *n){
  if (n == 0) return 0;
  if ((*fp)(n->data))
    return cons(n->data, filter(fp, n->next));
  else
    return filter(fp, n->next);
}

私たちはfilter 述語と呼ばれているもの:ブール値を返す関数.リストの先頭の値を取り、述語を適用します.を返しますcons この値は、filter を返します.それがfalseを返すならば、我々はそれを捨てて、尾の再帰を進めます.
私たちに渡すことができるいくつかの異なる機能を定義しようfilter , フィルタリングされたリストを作成します.

/* functional.h */
int isEven(int);
int greaterThanTwo(int);

/* main.c */
int main(){
  Node *src = seq(1, 5, NULL);
  Node *li = filter(&isEven, source);
  Node *lj = filter(&greaterThanTwo, source);

  printlist(li); // prints 2 4
  printlist(lj); // prints 3 4 5

  return 0;
}

int isEven(int x) {
  return (x % 2 == 0);
}
int greaterThanTwo(int x){ 
  return x > 2;
}

減らす

reduceは関数、リンクリスト、アキュムレータを受け取り、その関数をアキュムレータに適用した結果とリストのすべての要素を返す.

/* functional.h */
Node *filter(fp, Node *);

/* iterators.c */
int reduce(gp gp, int acc, Node *n){
  if (n == 0) return acc;
  int val = (*gp)(n->data, acc);
  return reduce(gp, val, n->next);
}

The reduce 関数はバイナリ演算子を受け取ります.基本演算子と同じように2つの引数を持つ関数です.リストの先頭を取り、アキュムレータと一緒にバイナリ演算子を適用します.次に、結果をアキュムレータの新しい値として設定し、リストの次の要素に対して再帰的に操作を繰り返します.
私たちに渡すことができるいくつかの異なる機能を定義しようreduce , と縮小リストの値を計算します.

/* functional.h */
int sum(int, int);
int sumTimesTen(int, int);

/* main.c */
int main(){
  Node *src = seq(1, 5, NULL);
  int i = reduce(&sum, source);
  int j = filter(&greaterThanTwo, source);

printf("%d\n", i); // prints 15
printf("%d\n", j); // prints 150

  return 0;
}

int sum(int x) {
  sum;
}
int sumTimesTen(int x, int y){ 
  return (x * 10) + y;
}

結論

ラムダ関数を実際にサポートしていない言語、map、filter、reduce - in、cのための一般的なツールを実装する方法を開発しました.
要約すると、まず最初に我々が考えなければならなかったのは、我々が操作したいデータ構造でした.Scheme,Haskell,Erlangのような関数型プログラミング言語の項目を収集するための標準データ構造をリンクリストとして選んだ.リストをノードへのポインタとして定義したりリンクしたりして、すべてのノードはいくつかのデータ(整数)を格納し、リストの次の項目を指す構造体である.リストの最後にはNILポインター(ゼロ値)が付けられています.また、定義しているcons 既存のリスト(またはNLLポインターによって表される空リスト)に要素をプラグインすることでリストを構築できる機能.
念頭に置いておくべきことは、再帰的なデータ構造と関数ポインタに関する研究だけであり、C言語での関数型プログラミングに関する研究ではないということです.我々のアプローチの1つの大きな問題は、データ構造の不変性を達成するために、メモリに新しいデータを割り当てることですが、不要なデータを使用しないデータをきれいにする方法はありません.これは、ガベージコレクター(Cでは提供されていないもの)を必要とします.
言及する価値があるもう一つのものは、我々の機能が整数型で働くことに限られているということですint . 何らかの種類のパラメータを受け入れる関数型の定義、すなわちパラメトリック多形を実装するのは良いことでしょう.
私は、コメント、訂正、批評または提案に感謝します.
使用されるが、記事で説明されない機能

Node *seq(int fst, int lst, Node *acc){
  if (fst <= lst) {
    acc = cons(lst, acc);
    return seq(fst, lst - 1, acc);
  }
  else {
    return acc;
  }
}

int length(Node *n){
  if (n == 0) return 0;
  return 1 + length(n->next);
}

void printlist(Node *n){
  if (n != 0) {
    printf("%d ", n->data);
    printlist(n->next);
  }
  else printf("\n");
}