「CやJavaで関数型(2)」関数型プログラミング事始め (47) 増補版(3)

関数型プログラミングがはじめての方へ贈る入門の書
前節：CやJavaで関数型(1)　次節：CやJavaで関数型(3)
参考書：
・五味 弘「はじめてのLisp関数型プログラミング」技術評論社(2016)
・大山口 通夫、五味 弘「プログラミング言語論」コロナ社(2008)
・五味 弘「関数型プログラミングと数学(ITと数学)」技術評論社(2021)

ここでは「CやJavaなどの普段使いの言語で関数型プログラミングに挑戦」の2回目の記事になります。前回は副作用なしの参照透過性のあるプログラミングの記事でしたが、今回はその続きになります。
CやJavaでは関数型の仕掛けを自作する必要があり、多少（？）の苦労が必要です。でも関数型のご利益が得られますので、楽をするためにはどんな苦労もしてください。

2.4 副作用をなくす例（スタック）続き

(4) 副作用のないスタック(Java)
ここではCと同様に、(a)コピー方式での実装を見ていきます。プログラム実はCと同様で、pushとpopするときにコピーするようになっています。
なおJavaではコピーするためのメソッド関数としてcloneがありますので、それを使うようにしています。

class Stack implements Cloneable {
  private int sp;
  private int[] stack;

  Stack(int size){
    sp = 0;
    stack = new int[size];
  }

  public Stack clone(){
    Stack stack = null;
      try {
        stack = (Stack)super.clone();
        stack.stack = this.stack.clone();
        stack.sp = this.sp;
      } catch (Exception e){
        e.printStackTrace();
    }
      return stack;
  }

  public Stack push(int element){
    Stack clone = this.clone();
    clone.stack[clone.sp++] = element;
    return clone;
  }

  public Pair pop(){
    Stack clone = this.clone();
    int element = clone.stack[--clone.sp];
    return new Pair(clone, element);
  }
}

class Pair {  // Javaには多値(複数の値を返す機構)がないので自作
  public Stack stack;
  public int element;

  Pair(Stack stack, int element){
    this.stack = stack;
    this.element = element;
  }
}

2.5 副作用をなくす例（リストを使ったスタック）

ここでは副作用のないスタックの実装例として、(c) 差分方式を採用して実装します。具体的には差分方式の実装としてリスト構造を採用して実装します。

(a)のコピー方式はpushとpopのときに全コピーをしていましたが、(c)の差分方式はpushのときの差分コピーだけで済むので、効率は良くなります。お勧めです。

(a) リストによる副作用にないスタック(C)
struct list {　// Cにはリスト（コンスセル）の実装がないので自作
  int car;
  list* cdr;
};

struct mv {  // Cには多値(複数の値を返す機構)がないので自作
  struct list* stack;
  int element;
} mv;

struct list* push(struct list* stack, int element){
  list* cell = (struct list*)malloc(sizeof(struct list));
  cell->car = element;
  cell->cdr = stack;
  return cell;
}

struct mv pop(struct list* stack){ 
  mv.element = stack->car;
  mv.stack = stack->cdr;
  return mv;
}

(b) リストによる副作用にないスタック(Java)

Cと同様にJavaでもリストによるスタックの実装を見ていきます。

class Stack {
  // JavaにはLinkedListはありますが
  // リスト（コンスセル）の実装がないので自作
  private int car;  
  private Stack cdr;

  public Stack push(int element){
    Stack cons = new Stack();
    cons.car = element;
    cons.cdr = this;
    return cons;
  }

public Pair pop(){
    return new Pair(cdr, car);
  }
}

class Pair {    // Javaには多値(複数の値を返す機構)がないので自作
  public Stack stack;
  public int element;

  Pair(Stack stack, int element){
    this.stack = stack;
    this.element = element;
  }
}

（予告）2.6 関数をファーストクラスに

普段使いの非関数型言語で、関数をファーストクラスとして、通常のデータタイプと同様に、関数の引数や値、配列の要素など、どこでも使えるようにしてみます。

Javaについてはラムダ式が実装されるようになりましたので、既にJavaのメソッド関数はファーストクラスとして扱えます。

そこでCによるラムダ式のような「関数をファーストクラスにする実装」を見ていきます。その時に使うのは「関数ポインタ」で、それを使った実装を見ていきます。