マップ（高階関数）

多くのプログラミング言語において、mapは高階関数であり、リストや集合などのコレクションの各要素に与えられた関数を適用し、結果を同じ型のコレクションに返します。関数型で考えると、しばしば「apply-to-all」と呼ばれます。

マップの概念はリストに限定されません。シーケンシャルなコンテナー、ツリー状のコンテナー、さらにはfutures や promisesなどの抽象的なコンテナーでも機能します。

例: リストのマッピング

整数のリストがあるとします[1, 2, 3, 4, 5]。各整数の2乗squareを計算するには、まず単一の数値に対する関数を定義します（ここではHaskellで示しています）。

平方x = x * x

その後、電話してください:

>>>マップの正方形[ 1 , 2 , 3 , 4 , 5 ]

これにより、が生成され[1, 4, 9, 16, 25]、がリスト全体を調べて各要素に map関数を適用したことがわかります。square

視覚的な例

以下は、関数に従って整数のリストX = [0, 5, 8, 3, 2, 1]を新しいリストにマッピングするマッピングプロセスの各ステップのビューです。X' $f(x)=x+1$

マップ関数の処理手順を適用する — リストにマップ関数を適用する際の処理手順の表示

はmapHaskell の基本プレリュード (つまり「標準ライブラリ」) の一部として提供され、次のように実装されています。

map :: ( a -> b ) -> [ a ] -> [ b ] map _ [] = [] map f ( x : xs ) = f x : map f xs

一般化

Haskell では、多態的関数は多型関数に一般化され、型クラスに属する任意の型に適用されます。map :: (a -> b) -> [a] -> [b] fmap :: Functor f => (a -> b) -> f a -> f bFunctor

リストの型コンストラクタは、前の例の関数を使用して型クラス[]のインスタンスとして定義できます。Functormap

インスタンスFunctor [] 、fmap = map

その他のインスタンスの例としてはFunctor、ツリーがあります。

-- 単純な二分木データTree a = Leaf a | Fork ( Tree a ) ( Tree a )           インスタンスFunctor Treeここで、fmap f ( Leaf x ) = Leaf ( f x ) fmap f ( Fork l r ) = Fork ( fmap f l ) ( fmap f r )

ツリーをマッピングすると次のようになります。

>>> fmap square (フォーク(フォーク(リーフ1 ) (リーフ2 )) (フォーク(リーフ3 ) (リーフ4 )))フォーク(フォーク(リーフ1 ) (リーフ4 )) (フォーク(リーフ9 ) (リーフ16 ))

Functor型クラスのすべてのインスタンスは、契約上、関数法則に従う義務fmapがあります。

fmap id ≡ id -- 恒等法則fmap ( f . g ) ≡ fmap f . fmap g -- 合成法則

ここで、はHaskell における関数合成.を表します。

他の用途の中でも、これによりさまざまな種類のコレクションに対して要素ごとの操作を定義できるようになります。

カテゴリー理論的背景

圏論において、関数は 2つの写像から構成されます。1つは圏の各オブジェクト $Aを別のオブジェクト$ $FA$ に写像する写像、もう1つは各射を別の射に写像する写像で、射は圏上の準同型として機能します（つまり、圏の公理を遵守します）。データ型の集合をカテゴリー $Type$ として解釈し、射を関数とすると、型クラスのメンバーである型構築子はそのような関数のオブジェクト部分であり、型構築子は射部分です。上記の関数法則は、まさにこの関数の圏論的関数公理です。 $F:C\rightarrow D$ $f:A\rightarrow B$ $Ff:FA\rightarrow FB$ FFunctorfmap :: (a -> b) -> F a -> F b

関数者は、自然変換と呼ばれる「射」を持つカテゴリ内のオブジェクトになることもできます。2 つの関数が与えられたとき、自然変換は、カテゴリ $D$ の各オブジェクト $A$ ごとに 1 つずつ、射のコレクションで構成されます。これらの射は、関数者が適用されるオブジェクトを考慮に入れずに、2 つの関数間の「変換」として機能するという意味で「自然」です。自然変換は、形式の関数に対応します。ここで、は普遍量化された型変数であり、に存在する型については何も知りません。このような関数の自然性公理は、いわゆる自由定理であるため、自動的に満たされます。これは、がパラメトリック多相であるという事実に依存します。[ ^1]たとえば、リストを反転するは自然変換です。また、木を左から右に平坦化するや、指定された比較関数に基づいてリストをソートするも自然変換です。 $F,G:C\rightarrow D$ $\eta :F\rightarrow G$ $\eta _{A}:FA\rightarrow GA$ eta :: F a -> G aaetaareverse :: List a -> List aflattenInorder :: Tree a -> List asortBy :: (a -> a -> Bool) -> List a -> List a

最適化

マップの数学的基礎は、多くの最適化を可能にする。合成法則は、

(map f . map g) listそして
map (f . g) list

どちらも同じ結果、つまりとなります。しかし、2番目の形式は最初の形式よりも計算効率が高くなります。なぜなら、どちらもリスト全体を最初から再構築する必要があるからです。そのため、コンパイラは最初の形式を2番目の形式に変換しようとします。このタイプの最適化はマップ融合と呼ばれ、ループ融合の機能的な類似物です。^[2] $\operatorname {map} (f)\circ \operatorname {map} (g)=\operatorname {map} (f\circ g)$ map

マップ関数はのような折り畳みによって定義されることが多く、これはマップ折り畳みの融合foldrを実行できることを意味します。はと同等です。foldr f z . map gfoldr (f . g) z

上記の単方向リンクリストに対する map の実装は末尾再帰ではないため、大きなリストで呼び出されるとスタック上に多くのフレームが蓄積される可能性があります。多くの言語では、代わりに「逆 map」関数を提供しています。これは、マップされたリストを逆順にするのと同等ですが、末尾再帰です。以下は、fold -left 関数を利用した実装です。

逆マップf = foldl ( \ ys x -> f x : ys ) []

単一リンクリストの逆順も末尾再帰であるため、リストを 2 回パスする必要がありますが、reverse と reverse-map を組み合わせて、末尾再帰の方法で通常の map を実行できます。

言語の比較

map 関数は関数型プログラミング言語に由来します。

Lisp言語は1959年にmaplist^[3]と呼ばれるマップ関数を導入しましたが、わずかに異なるバージョンは1958年にすでに登場していました^。[4]これはmaplist、関数を連続する残りリストにマッピングするの元の定義です。

maplist[x;f] = [null[x] -> NIL;T -> cons[f[x];maplist[cdr[x];f]]]

この関数はCommon Lisp ^[5]maplistのような新しいLispでも利用可能ですが、またはより汎用的な関数の方が好まれます。mapcarmap

リストの要素を二乗することは、S 式表記maplist法では次のように記述されます。

(マップリスト(ラムダ( l ) (平方根(車l ))) ' ( 1 2 3 4 5 ))

関数を使用するとmapcar、上記の例は次のように記述されます。

( mapcar (関数sqr ) ' ( 1 2 3 4 5 ))

今日では、マッピング関数は、多くの手続き型言語、オブジェクト指向言語、およびマルチパラダイム言語でもサポート（または定義）されています。C ++の標準ライブラリstd::transformではまたはと呼ばれstd::ranges::transform、C#（3.0）の LINQ ライブラリではという拡張メソッドとして提供されています。 map は、 ColdFusion Markup Language（CFML）、Perl、Python、RubySelectなどの高級言語でも頻繁に使用される操作です。この操作は、これら 4 つの言語すべてで呼び出されます。のエイリアスも Ruby（Smalltalkから）で提供されています。Common Lisp は、map のような関数のファミリーを提供しています。ここで説明する動作に対応する関数は（CAR 操作を使用してアクセスすることを示す）と呼ばれます。map 関数と同じ機能を提供する構文構造を持つ言語もあります。mapcollectmapmapcar-car

map は、2 つのリストの対応する要素にユーザー指定の関数を適用できる 2 項 (引数 2 つ) 関数を受け入れるように一般化されることがあります。一部の言語では、map2やzipWithなど、これに特別な名前が付けられています。明示的な可変個引数関数を使用する言語では、可変個引数関数をサポートするために、可変個引数の map バージョンが用意されている場合があります。2 つ以上のリストを持つ map では、リストの長さが異なる場合の処理の問題が発生します。これは言語によって異なります。例外を発生させる言語もあります。最短リストの長さに達した時点で停止し、その他のリストにある余分な項目を無視する言語もあります。最長リストの長さまで処理を続け、すでに終了したリストについては、値がないことを示すプレースホルダー値を関数に渡す言語もあります。

第一級関数とカリー化をサポートする言語では、を部分的に適用して、 1 つの値のみに機能する関数を、コンテナ全体に機能する要素ごとの等価関数に持ち上げることmapができます。たとえば、はリストの各要素を 2 乗する Haskell 関数です。map square

さまざまな言語の地図
言語	地図	マップ2のリスト	マップnリスト	注記	異なる長さのリストの扱い
APL	`func list`	`list1 func list2`	`func/ list1 list2 list3 list4`	APLの配列処理能力により、mapのような操作は暗黙的に実行される。	リストの長さが等しくない場合、または1の場合、長さエラーが発生します。
コモンリスプ	`(mapcar func list)`	`(mapcar func list1 list2)`	`(mapcar func list1 list2 ...)`		最短リストの長さに達したら停止します
C++	`std::transform(begin, end, result, func)` `list \| std::views::transform(result, func)`	`std::transform(begin1, end1, begin2, result, func)` `std::views::zip_transform(func, list1, list2)`	`std::views::zip_transform(func, list1, list2 ...)`	ヘッダー<algorithm>の begin、end、result は反復子であり、result から結果が書き込まれる。
C#	`ienum.Select(func)` または SELECT句	`ienum1.Zip(ienum2, func)`		`Select` ienumはIEnumerableの拡張メソッドであり、 `Zip`.NET 4.0で導入されました。同様に、すべての.NET言語でも同様です。	最短リストが終了したら停止します
CFML	`obj.map(func)`			は`obj`配列または構造体です。`func`各項目の値、そのインデックスまたはキー、および元のオブジェクトへの参照を引数として受け取ります。
クロージュア	`(map func list)`	`(map func list1 list2)`	`(map func list1 list2 ...)`		最短リストが終了したら停止します
D	`list.map!func`	`zip(list1, list2).map!func`	`zip(list1, list2, ...).map!func`		StoppingPolicy によって zip に指定: shortest、longest、または requireSameLength
アーラン	`lists:map(Fun, List)`	`lists:zipwith(Fun, List1, List2)`	`zipwith3`も利用可能		リストの長さは同じである必要があります
エリクサー	`Enum.map(list, fun)`	`Enum.zip(list1, list2) \|> Enum.map(fun)`	`List.zip([list1, list2, ...]) \|> Enum.map(fun)`		最短リストが終了したら停止します
F#	`List.map func list`	`List.map2 func list1 list2`		他の型（SeqとArray）用の関数が存在します	例外をスローする
輝き	`list.map(list, func)` `yielder.map(yielder, func)`	`list.map2(list1, list2, func)` `yielder.map2(yielder1, yielder2, func)`			長いリストの余分な要素を削除します
グルーヴィー	`list.collect(func)`	`[list1 list2].transpose().collect(func)`	`[list1 list2 ...].transpose().collect(func)`
ハスケル	`map func list`	`zipWith func list1 list2`	`zipWithn func list1 list2 ...`	`n`リストの数に対応します。最大で`zipWith7`	最短リストが終了したら停止します
ハックス	`array.map(func) list.map(func) Lambda.map(iterable, func)`
J	`func list`	`list1 func list2`	`func/ list1, list2, list3 ,: list4`	Jの配列処理能力により、mapのような操作は暗黙的に実行される	リストの長さが等しくない場合は長さエラー
Java 8以降	`stream.map(func)`
JavaScript 1.6 ECMAScript 5	配列#map(関数)	`List1.map(function (elem1, i) { return func(elem1, List2[i]); })`	`List1.map(function (elem1, i) { return func(elem1, List2[i], List3[i], ...); })`	Array#map はfuncに3つの引数（要素、要素のインデックス、配列）を渡します。使用されない引数は省略できます。	List1の最後で停止し、必要に応じて、未定義の項目を含む短い配列を拡張します。
ジュリア	`map(func, list)`	`map(func, list1, list2)`	`map(func, list1, list2, ..., listN)`		エラー: 寸法不一致
ログトーク	`map(Closure, List)`	`map(Closure, List1, List2)`	`map(Closure, List1, List2, List3, ...) (up to seven lists)`	Closure引数のみをインスタンス化する必要があります。	失敗
マセマティカ	`func /@ list Map[func, list]`	`MapThread[func, {list1, list2}]`	`MapThread[func, {list1, list2, ...}]`		リストは同じ長さでなければなりません
マキシマ	`map(f, expr₁, ..., expr_n) maplist(f, expr₁, ..., expr_n)`			mapは式と同じ先頭演算子を持つ式を返します。maplist はリストを返します。
OCaml	`List.map func list Array.map func array`	`List.map2 func list1 list2`			Invalid_argument例外が発生します
PARI/GP	`apply(func, list)`				—
パール	`map block list map expr, list`			ブロックまたはexprでは、特殊変数$_ がリストの各値を順番に保持します。	ヘルパーは`List::MoreUtils::each_array`、最長のリストがなくなるまで複数のリストを結合し、他のリストを次の内容で埋めます。`undef.`
PHP	`array_map(callable, array)`	`array_map(callable, array1,array2)`	`array_map(callable, array1,array2, ...)`	呼び出し可能オブジェクトのパラメータの数は、配列の数と一致する必要があります。	短いリストをNULL項目で拡張する
プロローグ	`maplist(Cont, List1, List2).`	`maplist(Cont, List1, List2, List3).`	`maplist(Cont, List1, ...).`	リスト引数は入力、出力、またはその両方です。zipWith、unzip、allも包含します。	サイレント障害（エラーではない）
パイソン	`map(func, list)`	`map(func, list1, list2)`	`map(func, list1, list2, ...)`	Python 2 ではリストを返し、 Python 3 では反復子を返します。	`zip()`(3.x)は`map()`最短リストが終了した時点で停止するが、`map()`(2.x)と`itertools.zip_longest()`(3.x)は短いリストを`None`項目で拡張する。
ルビー	`enum.collect {block} enum.map {block}`	`enum1.zip(enum2).map {block}`	`enum1.zip(enum2, ...).map {block} [enum1, enum2, ...].transpose.map {block}`	`enum is an Enumeration`	呼び出されたオブジェクトの末尾（最初のリスト）で停止します。他のリストが短い場合は、nil項目で拡張されます。
さび	`list1.into_iter().map(func)`	`list1.into_iter().zip(list2).map(func)`		とメソッドはどちらも元のイテレータの所有権を取得し、新しいイテレータを返します。メソッドは内部的にメソッドを呼び出します`Iterator::map`。`Iterator::zipIterator::zipIntoIterator::into_iterlist2`	短いリストが終わると停止します
S - R	`lapply(list, func)`	`mapply(func, list1, list2)`	`mapply(func, list1, list2, ...)`		短いリストは循環される
スカラ	`list.map(func)`	`(list1, list2).zipped.map(func)`	`(list1, list2, list3).zipped.map(func)`	注: 3 つ以上は不可能です。	短いリストが終わると停止します
計画（策略と詐欺を含む）	`(map func list)`	`(map func list1 list2)`	`(map func list1 list2 ...)`		リストはすべて同じ長さでなければなりません（SRFI-1 は異なる長さのリストも扱えるように拡張されています）
雑談	`aCollection collect: aBlock`	`aCollection1 with: aCollection2 collect: aBlock`			失敗
標準ML	`map func list`	`ListPair.map func (list1, list2) ListPair.mapEq func (list1, list2)`		2引数マップの場合、funcは引数をタプルで受け取ります。	`ListPair.map`最短リストが終了したら停止しますが、例外が`ListPair.mapEq`発生します`UnequalLengths`
迅速	`sequence.map(func)`	`zip(sequence1, sequence2).map(func)`			最短リストが終了したら停止します
XPath 3 XQuery 3	`list ! block` `for-each(list, func)`	`for-each-pair(list1, list2, func)`		`block`コンテキスト項目は`.`現在の値を保持します	最短リストが終了したら停止します

参照

ファンクタ（関数型プログラミング）
ジッピング（コンピュータサイエンス）または zip、複数のリストに「リスト」をマッピングする
フィルタ（高階関数）
Fold（高階関数）
foreachループ
自由モノイド
関数型プログラミング
高階関数
リストの理解
地図（平行パターン）

参考文献

^ Haskellのような一般再帰を許す 非正格言語では、これはの第一引数が正格である場合にのみ成り立ちます。Wadler , Philip (1989年9月). Theorems for free! (PDF) . 4th International Symposium on Function Programming Languages and Computer Architecture. London: Association for Computing Machinery .fmap
^ 「マップの融合：Haskell を 225% 高速化する」
^ J. マッカーシー、K. マリン、S. ラッセル、N. ロチェスター、S. ゴールドバーグ、J. スレーグル。 LISP プログラマーズマニュアル。 1959 年 3 月から 4 月
^ J. マッカーシー「記号操作言語 - 言語の改訂」AIメモ第4号、1958年10月
^ ANSI Common Lisp の関数 MAPC、MAPCAR、MAPCAN、MAPL、MAPLIST、MAPCON

[1] ^ Haskellのような一般再帰を許す 非正格言語では、これはの第一引数が正格である場合にのみ成り立ちます。Wadler , Philip (1989年9月). Theorems for free! (PDF) . 4th International Symposium on Function Programming Languages and Computer Architecture. London: Association for Computing Machinery .fmap

[2] 「マップの融合：Haskell を 225% 高速化する」

[3] J. マッカーシー、K. マリン、S. ラッセル、N. ロチェスター、S. ゴールドバーグ、J. スレーグル。 LISP プログラマーズマニュアル。 1959 年 3 月から 4 月

[4] J. マッカーシー「記号操作言語 - 言語の改訂」AIメモ第4号、1958年10月

[5] ANSI Common Lisp の関数 MAPC、MAPCAR、MAPCAN、MAPL、MAPLIST、MAPCON