関数的って、reduceって何だ

なぜ関数プログラミングは重要かの内容はどうやら関数プログラミングを理解する上で重要なことが書かれているらしいけど、いきなりlispでまったくわからない。
わからないなりにlispリファレンスなページ等片手に調べてたらなんとなくわかってきたのでとりあえずreduceの感触をjavascriptで確かめてみます。

(reduce f  x) nil =  x
(reduce f  x) (cons a l)  = f a ((reduce f x)  l)

何となく再帰的なのはわかる。reduce以外の変数は以下のような意味らしい。

f = 関数
x = 初期値
cons = 引数を二つとり、その二引数からなる配列を作る
(cons a l) = 配列
a = (cons a l)配列の先頭値
l = (cons a l)配列のa以降の要素

(reduce f x)の部分は最初の例だとsum関数に置き換えるので、nil, (cons a l)の部分には配列を指定するということがわかりました。それを踏まえると、

配列要素がない場合はxを返す
配列要素がある場合はfの第一引数に配列先頭値を、第二引数に((reduce f x) 配列残り要素)を指定して実行した結果を返す

ここまでくれば他言語で実装出来そうです。

var reduce = function( f, initial_value, list ) {
    if (list.length == 0) { return initial_value; }
    var car = list.shift();
    return f( car, reduce( f, initial_value, list ) );
}

reduceだけだと何も出来ないので、(reduce f x)の部分、sumを作ります。
lispだと、

sum = reduce add 0

これはjavascriptでもあまり変わらない。

var sum = function( list ){
    return reduce( add, 0, list );
};

sumの引数として渡すlist以外に、addが必要。元のコードだとfにあたる部分ですね。これが実際の計算をします。
lispだと

add x y  =  x +  y

javascriptだと

var add = function( a, b ) {
    return a + b;
}

必要な部品が出来たので使ってみる。

var data = [ 1, 2, 3, 4, 5 ];
alert( "sum result = " + sum( data ) );         // 15

同様に、かけ算する部品も作ってみます。

var multiply = function( a, b ) {
    return a * b;
}

var product = function(list) {
    return reduce( multiply, 1, list );
}

alert( "product result = " + product( data ) ); // 120

かけ算対応するために書いたコードは実際の演算関数と、reduceする際の初期値を決めるためのアダプタを書いただけです。この辺りが関数的なモジュラリティなのかなと。

上記コードを動かしてみるとわかるけど、reduce内でlist.shift()してるので足し算の結果確認直後にかけ算しようとすると新たなlistが必要です。ということで引数list非破壊版は以下のようになります。

var reduce = function( f, initial_value, list ) {
    if ( list.length == 0 ) { return initial_value; }
    var car = list[0];
    var i = 1;
    while( i < list.length ) {
        car =  f( car, list[i++] );
    }
    return car;
}

非破壊のついでに再帰でも無くなってます。これは最初のreduceバージョンでコード実際に動かして再初期化の必要があって駄目だなぁ、そういえばPlagger::Operatorあたりでreduce使ってたよな、と思い出してPerlのList::Util実装をカンニングしました。以下のようなコードです。

sub reduce (&@) {
  my $code = shift;
  no strict 'refs';

  return shift unless @_ > 1;

  use vars qw($a $b);

  my $caller = caller;
  local(*{$caller."::a"}) = \my $a;
  local(*{$caller."::b"}) = \my $b;

  $a = shift;
  foreach (@_) {
    $b = $_;
    $a = &{$code}();
  }

  $a;
}

Perlのreduceは以下のような感じで使います。mapの引数指定と同じですね。

#!/usr/local/bin/perl
use strict;
use warnings;
use List::Util qw( reduce );

my @list = ( 1, 2, 3, 4, 5 );
my $result = reduce { $a + $b } @list;
print $result;

ここまできてそういえばfunctional jsなMochiKitがあるじゃないか、と思い出してMochiKit.Iterを見てみたところ、

while( true ) {
    x = fn( x, iterable.next() )
}

同じでした。iterableについてはCollection & Copy - JavaScriptにおける繰り返し参照。

ここまでくればwhyfpの以降の例についても地道に置換してみようという気になるのではないかと思います。関数的な何かに初めて触れて数ヶ月たつけれども、最初に目にする一般的なコードが関数言語のコードでまったくわからない、というのがかなりハードル高く感じました。結局関数言語については調べる必要はあるけど、きっかけを掴めるかどうかも重要だと感じてます。

ちなみに関数的なjavasctipt実装はmotemenさんのコードが非常に参考になります。
そりゃモテるわけだ。