Javascriptでfoldを実装してみたメモ

defineFold.js

/*
fold(reduce, inject)を定義するまでの足跡
JavascriptのArray.prototype.reduce()はちょっと定義がおかしい。

引用元(MDN[https://developer.mozilla.org/ja/docs/Web/JavaScript/Reference/Global_Objects/Array/reduce])
>>構文
>>var result = array.reduce(callback[, initialValue]);
>>引数
>>callback:4つの引数をとって、配列内の各値に対し実行するコールバック関数
>>  previousValue:現在処理されている配列要素の 1 つ前の要素。もしくは、initialValue。 initialValue については、後で述べます。
>>  currentValue:現在処理されている配列要素
>>  index:現在処理されている配列要素のインデックス
>>  array:reduce に呼ばれた配列
>>initialValue:callback の最初の呼び出しのときに、最初の実引数として用いるためのオブジェクト。

>>callback:4つの引数をとって、配列内の各値に対し実行するコールバック関数
4つも引数をとっちゃだめだろ……。という話をQiitaで見たため、まともなfoldを定義してみる。

foldは以下のように説明されます。

引用元(Wikipedia - 高階関数#fold[https://ja.wikipedia.org/wiki/%E9%AB%98%E9%9A%8E%E9%96%A2%E6%95%B0#fold])
>>fold 関数は重畳（英語版）、堆積、畳み込みや折り畳みなどと呼ばれ、英語ではreduce、injectとも表現される。foldはリストの各要素に対して与えられた関数を適用する。

つまりfold(+, 0, list)と呼び出すことでlistの合計を出力するような関数になる(+は二項加算関数として考える)。
以下のような式でも表すことができる。
>>g [] = v
>>g (x:xs) = f x (g xs)
よくわからないが、英語版Wikipedia(https://en.wikipedia.org/wiki/Fold_%28higher-order_function%29)のfoldを見てみると、
>>g = foldr f v
に変換できるとある。
よくわからない。

要はリストの先頭の値と引数accumulatorに対して関数を適用することを繰り返す関数のことだと思うので、そのように実装する。
*/

//listの先頭の要素を取得する関数
function head(list){
  return list[0];
}

//listの先頭の要素を除いた値を取得する関数
function tail(list){
  var shallowCopy = list.slice();
  shallowCopy.shift();
  return shallowCopy;
}

//fold
function fold(func, accum, list){
  if(list.length == 0) return accum;
  var car = head(list);
  var cdr = tail(list);
  return fold(func, func(accum, car), cdr);
}

var reduce = foldl = fold;

//離散リスト作成用の関数
function range(initial, limit, incremental){
  if(incremental == 0) return [];
  var list = [];
  var accumlator = initial;
  for(var i = initial; i <= limit; i = i +incremental){
    list.push(accumlator);
    accumlator = accumlator + incremental;
  }
  return list;
}

//実行してみる:(1 + (2 + (3 + (4 + 5)))) = (+ (+ (+ (+ (+ 0 1) 2) 3) 4) 5) 左畳み込み
fold(function(x,y){return x+y;}, 0, range(1,5,1));

/*
では右畳み込みはどうなるのか？
左畳み込みはリストの先頭headと初期値initに対してfunction(head, init)を適用し、
それをまた初期値として左畳み込みに渡す。そして最終的にリストが空になった時の
初期値が返される。(+ (+ (+ (+ (+ 0 1) 2) 3) 4) 5) = (((((0 + 1) + 2) + 3) + 4) + 5)

対して右畳み込みはリストの先頭headをひとまず(関数を適用せず)置いておき、再帰処理を行う。
*/
//foldr
function foldr(func, accum, list){
  if(list.length == 0) return accum;
  var car = head(list);
  var cdr = tail(list);
  return func(car, foldr(func, accum, cdr));
}

foldr(function(x,y){return x+y;}, 0, range(1,5,1));

/*
つまり左右の畳み込みはどう違うかというと、先に関数を適用するか、後に関数を適用するかということになる。(本当に？)
右畳み込みは(+ 0 (+ 1 (+ 2 (+ 3 (+ 4 5))))) = (0 + (1 + (2 + (3 + (4 + 5)))))
文字列でリストを結合すると分かりやすいかもしれない。
*/
fold(function(x,y){return x+y;}, "a", ["b","c","d","e","f"]);
foldr(function(x,y){return x+y;}, "a", ["b","c","d","e","f"]);
//無名関数のreturn x+yをreturn y+xにしてみる。
fold(function(x,y){return y+x;}, "a", ["b","c","d","e","f"]);
foldr(function(x,y){return y+x;}, "a", ["b","c","d","e","f"]);

/*
foldはaccumがa,ab,abc,abcd,abcde,abcdeと変化していく。
f(accum, head(list))を繰り返しているためだ。
f(f(f(accum, head(list)), head(list)), head(list))
対してfoldrはaccumが変化しない。
f(head(list), f(head(list), f(head(list), accum)))
つまりリストの先頭(head)からhead(tail)、その結果と次のhead(tail)、というように
リストの左から右へ関数を適用していくのが左畳み込み、
対してリストの右(末尾)から左に関数を適用していくのが右畳み込みになる。
*/

/*
foldlとfoldrは畳み込みの方向と末尾再帰であるかどうかが異なる。
末尾再帰とは関数の最後のステップが自分自身の呼び出しになっているものをいう。
foldlはreturn fold(func, func(accum, car), cdr)となっており、func(accum, car)を
fvに置き換えるとfold(func, fv, cdr)となり、自分自身の呼び出しになる。
対してfoldrはreturn func(car, foldr(func, accum, cdr))となっており、
foldr(func, accum, cdr)をfvに置き換えるとfunc(car, fv)となり、自分自身の呼び出し
ではない。
そのためfoldlは末尾再帰だが、foldrはただの再帰である。
ただの再帰は計算の結果を覚えておくためにスタックを用いる必要があるが、末尾再帰は
計算の結果を覚えておく必要がない。(Haskellの話)

foldlとfoldrの使い分けは、リストから新しいリストを構成するような処理の場合、foldr
が有利になる。リストは左方向にしか伸ばせないため。(Haskellの話)
またfoldrは無限リストを扱える。

map関数を定義することでリストから新しいリストを構成するケースを考えてみる。
*/

function mapr(func, list){
  return foldr(function (val, accum){
    var shallowCopy = accum.slice();
    shallowCopy.unshift(func(val));
    return shallowCopy;
  }, [], list);
}

function mapl(func, list){
  return foldl(function (accum, val){
    /*var shallowCopy = accum.slice();
    shallowCopy.push(func(val));
    return shallowCopy;*/
    return accum.concat(func(val));
  }, [], list);
}

mapl(function(x){return x+10;}, range(0,5,1));
mapr(function(x){return x+10;}, range(0,5,1));
/*
foldlに渡す無名関数の引数がfoldrとは逆になっているのがわかる。ついでにArray#unshiftとArray#pushも違う。
Javascriptは左右どちらにもリスト(配列)を伸ばせるのであまり有利不利はない？
*/

/*
foldの逆変換を行うunfoldを実装する。初期値から何らかの動作を行ってリストを生成する関数。
(unfold condition func iterate-update seed)
1.seedにfuncを適用した結果をリストへ格納する
2.seedをiterate-updateで更新し、その結果にfuncを適用した結果をリストへ格納する
3.2をconditionが真になるまで繰り返す
*/
//unfoldr
function unfoldr(cond, func, update, seed){
  var list = (function makeList(val, list){
    if(cond(val)){
      return list;
    }else{
      return makeList(update(val), list.concat(func(val)));
    }
  })(seed, []);
  return list;
}

function unfoldl(cond, func, update, seed){
  var list = (function makeList(val, list){
    if(cond(val)){
      return list;
    }else{
      return makeList(update(val), list.concat(func(val)));
    }
  })(seed, []);
  return list;
}

unfoldl(function(x){return x == 0 ? true : false;},
       function(x){return x;},
       function(x){return x - 1;},
       3);
unfoldr(function(x){return x == 0 ? true : false;},
       function(x){return x;},
       function(x){return x - 1;},
       3);

function ranger(initial, limit, incremental){
  return unfoldr(function(x){return x > limit;}, function(x){return x;}, function(x){return x + incremental;}, initial);
}

/*
filterはリストの各要素に対して与えられた条件式を適用し、真である物だけをリストにまとめて返す。
*/
function filter(func, list){
  return (function fl(list, accum){
    if(list.length == 0) return accum;
    if(func(head(list))){
      accum.push(head(list));
    }
    return fl(tail(list), accum)
  })(list, []);
}

filter(function(x){return x <= 2;}, ranger(0, 5, 1));
filter(function(x){return x % 3 == 0;}, ranger(0,100,1));

/*
foldrは再帰を作る関数のため、今まで実装した関数をfoldrで再実装してみる。
foldlをfoldrを使って実装してみる。
*/
function foldlfr(func, accum, list){
  //未完成
}

function mapfr(func, list){
  return foldr(function(x,y){
    y.unshift(func(x));
    return y;
  }, [], list);
}

function filterfr(func, list){
  return foldr(function(x, y){
    if(func(x)){
      y.unshift(x);
    }
    return y;
  }, [], list);
}