左畳み込み演算とは
左畳み込み演算について, ご存知の方はこの節は読み飛ばしてください.
左畳み込み演算は, 多くのプログラミング言語において, 組み込みで, または, 基本ライブラリで提供される大変汎用的な演算です.
残念ながら言語によって reduce, accumulate, inject, fold-left など, 名前が様々で, また引数の順序もそれぞれです. (参考: 畳み込み関数の比較)
多くの繰り返し処理は左畳み込みに抽象化されます.
a = <累算器の初期値>;
for (i = 0; i < <データ列>.長さ; i++) {
a = <累算器の更新>(a, <データ列>[i]);
}
return a;
のような形の, データ列中の要素を順番に見て, 累算器を更新していくような処理は,
<左畳み込み> <累算器の更新> <累算器の初期値> <データ列>
のように抽象化できます.
また, 左畳み込みとして抽象化すると, データ列全体を読み込んで処理する必要がなく, 非常に大きなデータ列に対してシーケンシャルに累算器を更新することが可能であるという利点もあります. (実装によりますが, あくまでこの抽象化において原理的には.)
形式的な定義や説明は他に譲るとして, 以下
- Ruby の
inject - JavaScript の
reduce - Clojure の
reduce
で例示します.
以下の環境で試験しました.
% irb --version
irb 0.9.6(09/06/30)
% node --version
v0.10.26
% java -jar clojure-1.7.0.jar
Clojure 1.7.0
user=>
データ列の最初の要素を累算器の初期値とみなしてよいものは, 初期値 (その演算における単位元) を与えた場合と省略した場合の両方を紹介します.
数値の総和
数値列中の数値を全て足しあわせます.
Ruby
irb(main):001:0> [3, 1, 4, 1, 5, 9, 2, 6].inject(0, :+)
=> 31
irb(main):002:0> [3, 1, 4, 1, 5, 9, 2, 6].inject(:+)
=> 31
JavaScript
> [3, 1, 4, 1, 5, 9, 2, 6].reduce(function(a, x) {return a + x}, 0)
31
> [3, 1, 4, 1, 5, 9, 2, 6].reduce(function(a, x) {return a + x})
31
Clojure
user=> (reduce + 0 [3 1 4 1 5 9 2 6])
31
user=> (reduce + [3 1 4 1 5 9 2 6])
31
数値の総積
数値列中の数値を全て掛け合わせます.
Ruby
irb(main):003:0> [3, 1, 4, 1, 5, 9, 2, 6].inject(1, :*)
=> 6480
irb(main):004:0> [3, 1, 4, 1, 5, 9, 2, 6].inject(:*)
=> 6480
JavaScript
> [3, 1, 4, 1, 5, 9, 2, 6].reduce(function(a, x) {return a * x}, 1)
6480
> [3, 1, 4, 1, 5, 9, 2, 6].reduce(function(a, x) {return a * x})
6480
Clojure
user=> (reduce * 1 [3 1 4 1 5 9 2 6])
6480
user=> (reduce * [3 1 4 1 5 9 2 6])
6480
最大の長さを持つ文字列
文字列の列の中から, 最大の長さを持つ文字列を返します.
Ruby
irb(main):005:0> ["May", "I", "have", "a", "large", "container", "of", "coffee"].inject(""){|a, x| (a.length < x.length) ? x : a}
=> "container"
irb(main):006:0> ["May", "I", "have", "a", "large", "container", "of", "coffee"].inject{|a, x| (a.length < x.length) ? x : a}
=> "container"
JavaScript
> ["May", "I", "have", "a", "large", "container", "of", "coffee"].reduce(function(a, x) { if (a.length < x.length) return x; else return a}, "")
'container'
> ["May", "I", "have", "a", "large", "container", "of", "coffee"].reduce(function(a, x) { if (a.length < x.length) return x; else return a})
'container'
Clojure
user=> (reduce (fn [a x] (if (< (count a) (count x)) x a)) "" ["May" "I" "have" "a" "large" "container" "of" "coffee"])
"container"
user=> (reduce (fn [a x] (if (< (count a) (count x)) x a)) ["May" "I" "have" "a" "large" "container" "of" "coffee"])
"container"
文字列連結
Ruby
irb(main):008:0> ["May", "I", "have", "a", "large", "container", "of", "coffee"].inject{|a, x| a + " " + x} + "?"
=> "May I have a large container of coffee?"
JavaScript
> ["May", "I", "have", "a", "large", "container", "of", "coffee"].reduce(function(a, x) { return a + " " + x}) + "?"
'May I have a large container of coffee?'
Clojure
user=> (str (reduce (fn [a x] (str a " " x)) ["May" "I" "have" "a" "large" "container" "of" "coffee"]) "?")
"May I have a large container of coffee?"
ハッシュマップ
文字列の列を与えると, 列中の文字列をキーとして, その文字列の長さを値とするハッシュマップ(言語によっては連想配列, オブジェクトなどとも) を返します.
Ruby
irb(main):007:0> ["May", "I", "have", "a", "large", "container", "of", "coffee"].inject({}) {|a, x| a.merge({x => x.length})}
=> {"May"=>3, "I"=>1, "have"=>4, "a"=>1, "large"=>5, "container"=>9, "of"=>2, "coffee"=>6}
JavaScript
> ["May", "I", "have", "a", "large", "container", "of", "coffee"].reduce(function(a, x) { a[x] = x.length; return a}, {})
{ May: 3,
I: 1,
have: 4,
a: 1,
large: 5,
container: 9,
of: 2,
coffee: 6 }
Clojure
user=> (reduce (fn [a x] (assoc a x (count x))) {} ["May" "I" "have" "a" "large" "container" "of" "coffee"])
{"May" 3, "I" 1, "have" 4, "a" 1, "large" 5, "container" 9, "of" 2, "coffee" 6}
シェルで
さて, 前置きが長くなりました, Bourne Shell スクリプトで左畳み込みの実装は以下のようになります.
reduce.sh
#!/bin/sh
f=$1
i=$2
if [ "X$i" = "X" ]
then
read i
fi
while read line
do
set "$i" "$line"
i=`eval $f`
done
echo $i
- 累算処理は, 第一引数に「第一引数を累算器の値として, 第二引数をデータ列中の要素として処理し結果を標準出力に出力するプログラム」を与えます.
- 初期値は, 第二引数に与えます. 省略するとデータ列中最初の要素を初期値とします.
- データ列は, 改行区切りで標準入力から与えられるものとします.
上記を reduce として PATH 環境変数に含まれるディレクトリに保存 (または保存したディレクトリを PATH に追加) し, 実行パーミッションを与えてある (chmod +x reduce してある) ものとして, 以下使い方を例示します.
$/bin/sh --version
GNU bash, version 3.2.57(1)-release (x86_64-apple-darwin15)
Copyright (C) 2007 Free Software Foundation, Inc.
で試験しました.
数値の総和
数値列中の数値を全て足しあわせます.
$ echo "3 1 4 1 5 9 2 6" | tr ' ' '\n' | reduce 'expr $1 + $2' 0
31
$ echo "3 1 4 1 5 9 2 6" | tr ' ' '\n' | reduce 'expr $1 + $2'
31
数値の総積
数値列中の数値を全て掛け合わせます.
$ echo "3 1 4 1 5 9 2 6" | tr ' ' '\n' | reduce 'expr $1 \* $2' 1
6480
$ echo "3 1 4 1 5 9 2 6" | tr ' ' '\n' | reduce 'expr $1 \* $2'
6480
最大の長さを持つ文字列
文字列の列の中から, 最大の長さを持つ文字列を返します.
$ echo "May I have a large container of coffee" | tr ' ' '\n' | reduce 'if [ ${#1} -lt ${#2} ]; then echo $2; else echo $1; fi'
container
$ echo "May I have a large container of coffee" | tr ' ' '\n' | reduce 'if [ ${#1} -lt ${#2} ]; then echo $2; else echo $1; fi' ""
container
文字列連結
$ echo "May I have a large container of coffee" | tr ' ' '\n' | reduce 'echo "$1 $2"' | tr '\n' '?' ; echo
May I have a large container of coffee?
ハッシュマップ
オリジナルの Bourne Shell にはありませんが, bash にはハッシュマップがあるようですので, 機会あれば追記します.
最後まで読んでいただき, ありがとうございました.