Harita (üst düzey işlev) - Map (higher-order function)

Birçok olarak programlama dilleri , harita bir adıdır yüksek mertebeden fonksiyonu bir uygular verilen fonksiyon bir her elemana funktor örneğin bir, listede aynı sırada sonuçların listesini dönen,. İşlevsel formda düşünüldüğünde genellikle herkese uygulanır olarak adlandırılır .

Harita kavramı listelerle sınırlı değildir: sıralı kaplar , ağaç benzeri kaplar ve hatta vadeli işlemler ve vaatler gibi soyut kaplar için çalışır .

Örnekler: bir listeyi eşleme

Bir tamsayı listemiz olduğunu [1, 2, 3, 4, 5]ve her tamsayının karesini hesaplamak istediğimizi varsayalım . Bunu yapmak için önce squaretek bir sayıya bir fonksiyon tanımlarız (burada Haskell 'de gösterilmiştir ):

square x = x * x

sonra arayabiliriz

>>> map square [1, 2, 3, 4, 5]

hangi verir [1, 4, 9, 16, 25], maptüm listeden geçtiğini ve işlevi squareher öğeye uyguladığını gösterir.

Görsel örnek

Aşağıda, işleve göre X = [0, 5, 8, 3, 2, 1]yeni bir listeye eşlemek istediğimiz tamsayıların bir listesi için eşleme sürecinin her adımının bir görünümünü görebilirsiniz  : X'${\displaystyle f(x)=x+1}$

Bir listede harita işlevi uygularken işlem adımlarının görünümü

mapHaskell'ın taban başlangıcı (yani "standart kütüphanesi") bir parçası olarak sağlanır ve şekilde uygulanır:

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

genelleme

Haskell'de polimorfik fonksiyonu map :: (a -> b) -> [a] -> [b] a genelleştirilmiş polytypic fonksiyonu fmap :: Functor f => (a -> b) -> f a -> f b ait herhangi bir türü için geçerli olan, tip sınıfı . Functor

Bir tipte listelerinin []bir örneği olarak tanımlanabilir Functorkullanılarak tip sınıfı mapÖnceki örnekten elde edilen işlevi:

instance Functor [] where
  fmap = map

Örneklerin diğer örnekleri Functorarasında ağaçlar bulunur:

-- a simple binary tree
data 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)

Bir ağaç üzerinde eşleme şu sonuçları verir:

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

FunctorType sınıfının her örneği için fmap, sözleşmeye dayalı olarak functor yasalarına uymakla yükümlüdür :

fmap id      ≡ id              -- identity law
fmap (f . g) ≡ fmap f . fmap g -- composition law

burada Haskell'deki işlev bileşimini. belirtir .

Diğer kullanımların yanı sıra, bu, çeşitli koleksiyon türleri için eleman bazında işlemlerin tanımlanmasına izin verir .

Ayrıca, eğer F ve G, iki funktorlar olan, bir doğal dönüşüm polimorfik tür bir fonksiyonudur açıdan fmap : ${\displaystyle h:\forall TF(T)\to G(T)}$

${\displaystyle h_{Y}\circ \operatöradı {fmap} (f)=\operatöradı {fmap} (f)\circ h_{X}}$herhangi bir işlev için .${\ Displaystyle f:X\'den Y'ye}$

Eğer h fonksiyonu ile tanımlanır parametrik polimorfizm yukarıdaki tip tanımı olarak, bu şartnamenin her zaman tatmin edilir.

Optimizasyonlar

Haritaların matematiksel temeli, bir dizi optimizasyona izin verir . Kompozisyon yasası, her ikisinin de

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

aynı sonuca yol açar; yani, . Bununla birlikte, ikinci formun hesaplanması ilk forma göre daha verimlidir, çünkü her biri bir listenin tamamını sıfırdan yeniden oluşturmayı gerektirir. Bu nedenle, derleyiciler ilk formu ikinciye dönüştürmeye çalışacaklardır; bu tür optimizasyon, harita füzyonu olarak bilinir ve döngü füzyonunun işlevsel analoğudur . ${\displaystyle \operatöradı {harita} (f)\circ \operatöradı {harita} (g)=\operatöradı {harita} (f\circ g)}$map

Harita işlevleri, örneğin bir katlama cinsinden tanımlanabilir ve sıklıkla tanımlanır foldr; bu, birinin bir harita katlama füzyonu yapılabileceği anlamına gelir : foldr f z . map geşdeğerdir foldr (f . g) z.

Yukarıdaki haritanın tek başına bağlantılı listelerde uygulanması kuyruk özyinelemeli değildir , bu nedenle büyük bir listeyle çağrıldığında yığında çok sayıda çerçeve oluşturabilir. Birçok dil, dönüşümlü olarak, eşlenmiş bir listeyi tersine çevirmeye eşdeğer, ancak kuyruk özyinelemeli bir "ters eşleme" işlevi sağlar. İşte fold -left işlevini kullanan bir uygulama .

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

Tekil bağlantılı bir listeyi tersine çevirmek de kuyruk özyinelemeli olduğundan, normal haritayı kuyruk özyinelemeli bir şekilde gerçekleştirmek için ters ve ters harita oluşturulabilir, ancak liste üzerinde iki geçiş yapılmasını gerektirir.

Dil karşılaştırması

Harita işlevi, işlevsel programlama dillerinde ortaya çıkmıştır .

Lisp dili maplist, 1959'da adı verilen ve 1958'de zaten görünen biraz farklı sürümleri olan bir harita işlevi tanıttı . Bu, maplistardışık dinlenme listeleri üzerinde bir işlevi eşlemek için orijinal tanımdır :

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

Bu işlev maplist, Common Lisp gibi daha yeni Lisp'lerde hala mevcuttur , ancak benzeri mapcarveya daha genel olan işlevler maptercih edilir.

Bir listenin öğelerini kullanarak kare almak, S-ifadesi notasyonunda maplistşu şekilde yazılır :

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

Fonksiyonu kullanarak mapcar, yukarıdaki örnek şu şekilde yazılır:

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

Günümüzde eşleme işlevleri birçok prosedürel , nesne yönelimli ve çok paradigmalı dilde de desteklenmektedir (veya tanımlanabilir) : C++ 'ın Standart Kitaplığında buna std::transform, C# (3.0)'ın LINQ kitaplığında denir. adlı bir uzatma yöntemi olarak sağlanır Select. Harita ayrıca ColdFusion Markup Language (CFML), Perl , Python ve Ruby gibi yüksek seviyeli dillerde sıklıkla kullanılan bir işlemdir ; işlem mapbu dillerin dördünde de çağrılır . Ruby'de ( Smalltalk'tan ) collectiçin bir takma ad mapda sağlanır . Common Lisp , bir harita benzeri işlevler ailesi sağlar; burada açıklanan davranışa karşılık gelen çağrılır ( CAR işlemini kullanarak erişimi gösterir ). Harita işleviyle aynı işlevselliği sağlayan sözdizimsel yapılara sahip diller de vardır. mapcar-car

Harita bazen, kullanıcı tarafından sağlanan bir işlevi iki listeden karşılık gelen öğelere uygulayabilen ikili (2-argüman) işlevleri kabul edecek şekilde genelleştirilir. Bazı diller gibi bunun için özel adlar kullanın map2 veya zipWith . Açık değişken işlevleri kullanan diller , değişken işlevli işlevleri desteklemek için değişken eşlilikli harita sürümlerine sahip olabilir . 2 veya daha fazla liste içeren harita, listeler farklı uzunlukta olduğunda ele alma sorunuyla karşılaşır. Bu konuda çeşitli diller farklıdır. Bazıları bir istisna oluşturur. Bazıları en kısa listenin uzunluğundan sonra durur ve diğer listelerdeki fazlalıkları görmezden gelir. Bazıları en uzun listenin uzunluğuna kadar devam eder ve zaten sona eren listeler için, değer olmadığını belirten işleve bir yer tutucu değeri iletir.

Destekleyen diller birinci sınıf işlevleri ve tımar , mapolabilir , kısmen tatbik için asansör bir işlevi olduğunu öğeye eşdeğer tek bir değer çalışmaları bu bütün bir kap üzerinde çalışır; örneğin, map squarebir listenin her öğesinin karesini alan bir Haskell işlevidir.

Ayrıca bakınız

• Functor (fonksiyonel programlama)
• Konvolüsyon (bilgisayar bilimi) , conv veya zip olarak da adlandırılır
• Filtre (üst düzey işlev)
• Katlama (üst düzey işlev)
• her biri için
• serbest monoid
• Fonksiyonel programlama
• Üst düzey işlev
• Liste anlama
• Harita (paralel desen)

Referanslar