الخريطة (دالة من الرتبة العليا)

في العديد من لغات البرمجة ، تُعتبر دالة map دالة من الرتبة العليا تُطبّق دالة مُحددة على كل عنصر من عناصر مجموعة ، مثل قائمة أو مجموعة ، وتُعيد النتائج في مجموعة من نفس النوع. وغالبًا ما تُسمى دالة تُطبّق على الكل عند النظر إليها في سياق البرمجة الوظيفية .

إن مفهوم الخريطة لا يقتصر على القوائم: فهو يعمل مع الحاويات المتسلسلة ، والحاويات الشبيهة بالأشجار، أو حتى الحاويات المجردة مثل المستقبلات والوعود .

لنفترض أن لدينا قائمة من الأعداد الصحيحة [1, 2, 3, 4, 5]. لحساب مربع كل عدد صحيح، يجب أولاً تعريف دالة squareلعدد واحد (كما هو موضح هنا بلغة هاسكل ):

مربع س = س × س

بعد ذلك، اتصل بـ:

>>> map square [ 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

في لغة هاسكل، يتم تعميم الدالة متعددة الأشكال إلى دالة متعددة الأنماط ، والتي تنطبق على أي نوع ينتمي إلى فئة النوع .map::(a->b)->[a]->[b]fmap::Functorf=>(a->b)->fa->fbFunctor

يمكن تعريف مُنشئ النوع للقوائم على []أنه نسخة من Functorفئة النوع باستخدام mapالدالة من المثال السابق:

مثال Functor [] حيث fmap = map

ومن الأمثلة الأخرى على Functorالحالات الأشجار:

-- بيانات شجرة ثنائية بسيطة: Tree a = Leaf a | Fork ( Tree a ) ( Tree a )مثال شجرة الدوال حيث 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 -- قانون التركيب

حيث .يشير إلى تركيب الدوال في لغة هاسكل.

من بين استخدامات أخرى، يسمح هذا بتحديد العمليات على مستوى العناصر لأنواع مختلفة من المجموعات .

يُتيح الأساس الرياضي للخرائط إجراء عدد من التحسينات . ويضمن قانون التركيب أن كليهما

• (map f . map g) listو
• map (f . g) list

يؤدي إلى نفس النتيجة؛ أي،${\displaystyle \operatorname {map} (f)\circ \operatorname {map} (g)=\operatorname {map} (f\circ g)}$مع ذلك، فإن الصيغة الثانية أكثر كفاءة في الحساب من الصيغة الأولى، لأن كلتيهما mapتتطلبان إعادة بناء قائمة كاملة من الصفر. لذلك، ستحاول المترجمات تحويل الصيغة الأولى إلى الثانية؛ يُعرف هذا النوع من التحسين باسم دمج الخرائط ، وهو النظير الوظيفي لدمج الحلقات . ^{[ 2 ]}

يمكن تعريف دوال الخرائط، وغالبًا ما يتم تعريفها، من حيث الطي مثل foldr، مما يعني أنه يمكن للمرء إجراء دمج بين الخريطة والطي : foldr f z . map gوهو ما يعادل foldr (f . g) z.

إنّ تطبيق دالة map المذكورة أعلاه على القوائم المرتبطة أحادية الاتجاه ليس تكراريًا ذيليًا ، لذا قد يؤدي إلى تراكم عدد كبير من الإطارات على مكدس الاستدعاءات عند استدعائها مع قائمة كبيرة. توفر العديد من لغات البرمجة بديلًا لذلك دالة "reverse map"، وهي مكافئة لعكس قائمة map، ولكنها تكرارية ذيلية. إليك تطبيقًا يستخدم دالة fold -left.

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

بما أن عكس قائمة مرتبطة بشكل فردي هو أيضًا عملية تكرارية ذيلية، يمكن دمج reverse و reverse-map لتنفيذ الخريطة العادية بطريقة تكرارية ذيلية، على الرغم من أنها تتطلب إجراء عمليتي مرور على القائمة.

نشأت دالة الخريطة في لغات البرمجة الوظيفية .

قدمت لغة Lisp دالة map تسمى maplist^{[ 3 ]} في عام 1959، مع ظهور إصدارات مختلفة قليلاً في عام 1958. ^{[ 4 ]} هذا هو التعريف الأصلي لـ maplist، حيث تقوم هذه الدالة برسم دالة على قوائم الباقي المتتالية:

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

maplistلا تزال هذه الوظيفة متاحة في لغات Lisp الأحدث مثل Common Lisp ، ^{[ 5 ]} على الرغم من أن الوظائف مثل mapcarأو الأكثر عمومية mapستكون مفضلة.

maplistيمكن كتابة عملية تربيع عناصر القائمة باستخدام صيغة S-expression على النحو التالي:

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

باستخدام الدالة mapcar، سيُكتب المثال أعلاه على النحو التالي:

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

اليوم، تُدعم دوال الربط (أو يُمكن تعريفها) في العديد من لغات البرمجة الإجرائية ، والبرمجة كائنية التوجه ، واللغات متعددة الأنماط : في مكتبة C++ القياسية ، تُسمى `map` أو ` map()` ، وفي مكتبة LINQ الخاصة بلغة C# (3.0)، تُقدم كدالة إضافية تُسمى `map()` . تُعد دالة `map` أيضًا عملية شائعة الاستخدام في لغات البرمجة عالية المستوى مثل ColdFusion Markup Language (CFML)، وPerl ، و Python ، و Ruby ؛ وتُسمى هذه العملية `map()` في جميع هذه اللغات الأربع. كما يُوفر Ruby (من Smalltalk ) اسمًا بديلًا لـ `map( )`. تُوفر Common Lisp مجموعة من الدوال الشبيهة بدالة `map()`؛ وتُسمى الدالة التي تُطابق السلوك الموصوف هنا `map()` ( مما يُشير إلى الوصول باستخدام عملية CAR ). توجد أيضًا لغات ذات بنى نحوية تُوفر نفس وظائف دالة `map()`.std::transformstd::ranges::transformSelectmapcollectmapmapcar-car

تُعمم دالة map أحيانًا لقبول الدوال الثنائية (ذات وسيطين) التي تُطبق دالة يُحددها المستخدم على العناصر المتناظرة في قائمتين. تستخدم بعض اللغات أسماءً خاصة لهذا الغرض، مثل map2 أو zipWith . قد تحتوي اللغات التي تستخدم دوالًا متعددة الوسائط صريحة على إصدارات من map ذات عدد وسائط متغير لدعم هذه الدوال . تواجه دالة map مع قائمتين أو أكثر مشكلة التعامل مع القوائم ذات الأطوال المختلفة. تختلف اللغات في هذا الشأن؛ فبعضها يُصدر استثناءً، وبعضها يتوقف بعد طول أقصر قائمة ويتجاهل العناصر الزائدة في القوائم الأخرى، بينما يستمر بعضها حتى طول أطول قائمة، وبالنسبة للقوائم التي انتهت بالفعل، يُمرر قيمة افتراضية إلى الدالة تُشير إلى عدم وجود قيمة.

في اللغات التي تدعم الدوال من الدرجة الأولى والتقسيم الجزئي ، mapيمكن تطبيقها جزئيًا لرفع دالة تعمل على قيمة واحدة فقط إلى مكافئ عنصري يعمل على حاوية كاملة؛ على سبيل المثال، map squareهي دالة Haskell تقوم بتربيع كل عنصر من عناصر القائمة.

• الدالة الوظيفية (Functor)
• الضغط (في علوم الحاسوب) أو zip، هو عملية ربط "قائمة" بقوائم متعددة.
• التصفية (دالة من الرتبة العليا)
• الطي (دالة من الرتبة العليا)
• حلقة foreach
• أحادي حر
• البرمجة الوظيفية
• دالة من الرتبة العليا
• فهم القوائم
• خريطة (نمط متوازٍ)