マップ（高階関数）

多くのプログラミング言語において、mapは、リストやセットなどのコレクションの各要素に指定された関数を適用し、同じ型のコレクションに結果を返す高階関数です。関数形式として考えると、しばしば「すべてに適用」と呼ばれます。

マップの概念はリストに限定されません。シーケンシャルコンテナ、ツリー状のコンテナ、さらにはフューチャーやプロミスといった抽象的なコンテナにも適用できます。

整数のリストがあるとします[1, 2, 3, 4, 5]。各整数の二乗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'${\displaystyle f(x)=x+1}$ :

これmapはHaskellの基本プレリュード（つまり「標準ライブラリ」）の一部として提供され、以下のように実装されています。

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

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

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

instance Functor [] where fmap = map

その他の例としてはFunctor、木などが挙げられます。

-- シンプルな二分木データTree a = Leaf a | Fork ( Tree a ) ( Tree a )instance Functor Tree where fmap f ( Leaf x ) = Leaf ( f x ) fmap f ( Fork l r ) = Fork ( fmap f l ) ( fmap f r )

ツリー上のマッピングの結果：

>>> fmap square ( Fork ( Fork ( Leaf 1 ) ( Leaf 2 )) ( Fork ( Leaf 3 ) ( Leaf 4 ))) Fork ( Fork ( Leaf 1 ) ( Leaf 4 )) ( Fork ( Leaf 9 ) ( Leaf 16 ))

Functor型クラスのすべてのインスタンスは、ファンクタ法則に従うことが契約上義務付けられてfmapいます。

fmap id ≡ id -- 同一性法則fmap ( f . g ) ≡ fmap f . fmap g -- 合成法則

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

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

写像の数学的基礎は、多くの最適化を可能にする。合成法則は、両方が

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

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

マップ関数は、などのフォールドに関して定義することができ、また多くの場合定義されます。これは、マップとフォールドの融合がfoldr可能であることを意味します。はと同等です。foldr f z . map gfoldr (f . g) z

上記の単方向連結リストに対する map の実装は末尾再帰ではないため、大きなリストで呼び出すとスタック上に多くのフレームが蓄積される可能性があります。多くのプログラミング言語では、マップされたリストを反転させるのと同等の機能を持つものの、末尾再帰である「reverse map」関数が提供されています。以下は、fold -left 関数を利用した実装例です。

reverseMap f = foldl ( \ ys x -> f x : ys ) []

単方向連結リストの反転も末尾再帰であるため、reverseとreverse-mapを組み合わせることで、通常のmapを末尾再帰的に実行できますが、リストを2回走査する必要があります。

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

Lisp言語は1959年にmaplist^{[ 3 ]}と呼ばれるマップ関数を導入したが、若干異なるバージョンは1958年には既に存在していた。 ^{[ 4 ]}これはmaplist、連続するレストリストに関数をマッピングするの元の定義である。

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

この関数はCommon Lispmaplistなどの新しい Lisp でもまだ利用可能ですが^{[ 5 ]}、や のようなより汎用的な関数の方が好ましいでしょう。mapcarmap

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

( maplist ( lambda ( l ) ( sqr ( car l ))) ' ( 1 2 3 4 5 ))

上記の例を関数を使ってmapcar記述すると、次のようになります。

( mapcar ( function sqr ) ' ( 1 2 3 4 5 ))

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

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

第一級関数とカリー化をサポートする言語では、 は、単一の値のみに作用する関数を、コンテナ全体に作用する要素ごとの同等の関数に部分的に適用するmapことができます。たとえば、 は、リストの各要素を二乗する Haskell 関数です。map square

• ファンクター（関数型プログラミング）
• ジッピング（コンピュータサイエンス）またはzip、複数のリストに「リスト」をマッピングすること
• フィルタ（高階関数）
• 折り畳み（高階関数）
• foreachループ
• 自由モノイド
• 関数型プログラミング
• 高階関数
• リスト内包表記
• マップ（平行パターン）