Java : 高階関数

プログラミング

当初の目的とはだいぶ違う方向に進んでいってしまいましたが、そのおかげでだいぶJavaという言語に対する知見を深めることができたような気がします。
ということで、そろそろJavaで高階関数を書くテーマに挑戦できそうです。

      • -

まず、ここで考える高階関数として、配列に対する次の３つの関数を挙げます。

collect
配列の各要素に対して操作を加え、その結果を別の配列として返す。
filter
配列の各要素に対してテストを行い、結果が真となったものだけからなる新しい配列を返す。
fold
配列の各要素に対する操作の結果を蓄積する。

この３つは、SICPでは、"2.2.3 Sequences as Conventional Interfaces"のところで、map, filter, accumulateとして登場する関数であり、Smalltalkでは、Collectionクラスの、collect:, select:, inject:into:というメソッドに対応します。（mapを使わず、collectとしたのは、JavaにはMapというコレクションインターフェースが存在するので、シンボルを別にしたかったためです）
ここでは、String型の配列のみを対象として扱います。これは、JDK1.5より導入されたGenericsを使うことで容易に一般化することができます。また、コレクションクラスへの適用も容易です。
ただし、基本型については、それぞれについて別のクラスを作成する必要があります。（追記）JDK1.5よりautoboxingが導入されたので、基本型への拡張も容易です。

      • -

foldについては、左結合と右結合の２種類があります。Lispを始めとしたconsを基本的なデータ構造として持つ言語では、右結合のfoldが非常に有益な効果をもたらすのですが、Javaにはそういう事情は特にないので、ここでは左結合のfoldのみを対象とします。

collect

public abstract class Collect {
  protected abstract String each(String s);
  public String[] all(String[] sa) {
    String[] ret = new String[sa.length];
    for (int i=0; i<sa.length; ++i) {
      ret[i] = each(sa[i]);
    }
    return ret;
  }
}

filter

publid abstract class Filter {
  protected abstract boolean each(String s);
  publid String[] all(String[] sa) {
    String[] tmp = new String[sa.length];
    int j=0;
    for (int i=0; i<sa.length; ++i) {
      if (each(sa[i])) {
        tmp[j++] = sa[i];
      }
    }
    String[] ret = new String[j];
    for (int i=0; i<j; ++i) {
      ret[i] = tmp[i];
    }
    return ret;
  }
}

fold

public abstract class Fold {
  protected abstract String each(String s0, String s1);
  public String all(String ret, String[] sa) {
    for (int i=0; i<sa.length; ++i) {
      ret = each(ret, sa[i]);
    }
    return ret;
  }
}

使用例

「長さが５以上ある文字列だけを取り出し、小文字を大文字に変換して、全て結合して一つの文字列として返す」という処理を書いて見ます。

class Main {
  String join_Uppper_of_moreThan_5(String[] input) {
    return
      new Fold()
        { String each(String s0, String s1) { return s0+s1;} }
      .all( "",
           new Collect()
              { String each(String s) { return s.toUpperCase();} }
            .all( new Filter()
                    { boolean each(String s) { return s.length() >= 5;} }
                  .all(input)));
  }
}

まあまあかな？ 静的型付けで型推論がないことを考えると、いい線行っているんじゃないでしょうか？
ところで、よくよく見ると、この方式は、デフォルトでカリー化しています。だから、こういう風に書いてもよい。

class Main {
  String join_Uppper_of_moreThan_5(String[] input) {
    Fold join = new Fold()
      { String each(String s0, String s1) { return s0+s1;} }
    Collect upper = new Collect()
      { String each(String s) { return s.toUpperCase();} }
    Filter moreThan_5 = new Filter()
      { boolean each(String s) { return s.length() >= 5;} }
    
    return join.all( "", upper.all( moreThan_5.all( input )));
  }
}