JavaScript: transducerを作ってみた

transducerというものがあるというのを知って、どんなものか自分でもやってみた。
関数合成が見やすく効率的にできるそうな。

試行錯誤の結果、こうなりました。

const compose = (...fs) => x => 
    fs.reduceRight( (acc, f) => f(acc), x )

const mapping = f => reducing => (acc, e) => 
    reducing(acc, f(e))
const filtering = f => reducing => (acc, e) => 
	f(e) 
    ? reducing(acc, e) 
    : reducing(acc, undefined)
const folding = f => x => reducing => (acc, e) => 
	acc.length === 0 
    ? reducing(acc, f(x, e))
    : reducing(acc, f(acc[acc.length-1], e))  
const taking = n => reducing => (acc, e) => 
	acc.length < n 
    ? reducing(acc, e) 
    : reducing(acc, undefined)

const concatF = (acc, e) => 
    e || e===0 
    ? [...acc, e] 
    : [...acc]

const intoArray = (...fs) => xs => 
    xs.reduce( compose( ...fs )( concatF )
    , []
    );

intoArrayの最初のかっこには、mapping()、filtering()、folding()、taking()が適用する順番で入ります。

//使用例:
const succ = x => 
    x + 1;
const even = x => 
    x % 2 === 0;
const sum = (x, y) => 
    x + y;

// 配列の要素に 1 を加える => 偶数 => 3個 =>要素を左から足していく
//[0,1,2,3,4,5,6,7,8,9]=>[1,2,3,4,5,6,7,8,9,10]=>[2,4,6,8,10]=>[2,4,6]=>[2,6,12]になるはず
intoArray( 
	mapping( succ )
	, filtering( even )
	, taking( 3 )
	, folding( sum )( 0 ) 
)( [0,1,2,3,4,5,6,7,8,9] );
//=> [ 2, 6, 12 ]

できたー!

こちらの記事が元です。まとまってて詳しいです。
map, reduce もいいけど transduce もね

こちらも参考にしました。
Understanding Transducers in JavaScript

どうなっているのか?

何とか理屈を考えてみる。

関数合成compose

あとで使うので。これさえあれば素のES6でも何とかなりそうな気がする。多分...

• 初期値xと数が決まってない複数の関数を引数にとって
• ()内で、fsはrest parameters ... で 実際に渡された引数による配列になって関数に渡されます。
• 初期値xのアキュムレータaccに配列fsの要素fを逆順で適用していく(reduceRight)

const compose = (...fs) => x => 
    fs.reduceRight( (acc, f) => f(acc)
    , x 
    )

map,filterをreduceで書く

// xs.map(f):
xs.reduce( 
    (acc, e) => [...acc, f(e)]
    , []
    )
// xs.filter(f):
xs.reduce( 
    (acc, e) => f(e) 
    ? [...acc, e] 
    : [...acc]
    , []
    )

あとあとのために変形します。
共通してるっぽいところをreducingとしてくくりだす。 <- ここ。かなり飛躍あり。

// xs.map(f):
xs.reduce( 
    (acc, e) => reducing(acc, f(e))
    , []
    )
// xs.filter(f):
xs.reduce( 
    (acc, e) => 
        f(e) 
        ? reducing(acc, e) 
        : reducing(acc, undefined)
    , []
    )

reducingとは何?

• 配列accと値eを引数に
• eがあればaccの後にeを加えたあたらしい配列を返す。

//concatF:: ([a], a) -> [a]
const concatF = (acc, e) => 
    e || e === 0 
    ? [...acc, e] 
    : [...acc]

引数として切り出すために名前をつけましたが、常にこれが入ります。
配列と値をとって配列を返す、というのが大事な性質です。

reduceに食べさせる関数を切り出す

//map:
(acc, e) => 
    reducing(acc, f(e))
//filter:
(acc, e) => 
    f(e) 
    ? reducing(acc, e) 
    : reducing(acc, undefined)

f,reducingが引数として必要なのでそれも加えて関数にします。

const mapping = f => reducing => (acc, e) => 
    reducing(acc, f(e))
const filtering = f => reducing => (acc, e) => 
    f(e) 
    ? reducing(acc, e) 
    : reducing(acc, undefined)

これらを使うと：

// xs.map(f):
xs.reduce( mapping( f )( concatF ), [])
// xs.filter(f):
xs.reduce( filtering( f )( concatF ), [])

なんか同じ構造っぽくなってる!
こんな風に使えます。

//使用例:
const succ = x => x + 1;
const even = x => x % 2 === 0;

[0,1,2,3,4].reduce( mapping( succ )( concatF ), [])
//=> [ 1, 2, 3, 4, 5 ]
[0,1,2,3,4].reduce( filtering( even )( concatF ), [])
//=> [ 0, 2, 4 ]

mapping(f),filtering(f)という関数を考える

これらは

• reducing::([a],a)->[a]を引数にとって
• 配列と値を引数にして配列を返す関数::([a],a)->[a]を返す

reducingをちょっと変化したreducingに変える、配列に値を追加するときにちょっと小細工する、という意味合い。
入力と出力がひとつかつ同じ型なので簡単に合成できる。<-ここ。確かにそうだけど...納得感薄い。
そしてこいつらが transducer。関数合成の部品です。
ほかにはこんなものが考えられます。

// transducer版reduce。先頭からその時点までの畳み込み。
const folding = f => x => reducing => (acc, e) => acc.length===0 ? reducing(acc, f(x, e)):reducing(acc, f(acc[acc.length-1], e))  
// transducer版take。先頭から n 個を取得。
const taking = n => reducing => (acc, e) => acc.length < n ? reducing(acc, e) : reducing(acc, undefined)

##合成して使ってみる

[0,1,2,3,4].reduce( mapping( succ )( concatF ), [])
		.reduce( filtering( even )( concatF ), [])
//=> [ 2, 4 ]

const succEven = compose( mapping( succ ), filtering( even ) );
[0,1,2,3,4].reduce( succEven( concatF ), [])
//=> [ 2, 4 ]

できたー!

関数にしてみました

const intoArray = (...fs) => xs => xs.reduce( compose( ...fs )( concatF ), []);
//使用例:
intoArray( mapping( succ ), filtering( even ) )( [0,1,2,3,4,5,6,7,8,9] );
//=> [ 2, 4, 6, 8, 10 ]

使ってみた。

なんでかなめちゃ遅っ。
実用性はなしかな。
まあ勉強にはなりました。