热门问题
时间线
聊天
视角

Map (高階函式)

来自维基百科,自由的百科全书

Remove ads

在很多程式語言中,對映(map)是一個高階函式的名字,它將一個給定函式英語procedural parameter應用到一個函子比如列表的每個元素,返回按相同次序的一個列表。對映的概念不受限於列表:它可工作在順序的容器,類似樹的容器,甚至是抽象容器比如future與promise

對映在作為泛函形式考慮時,經常叫做「應用於全部」。在支援頭等函式柯里化的語言中,map可以部份應用英語partial application在一個函式上,將這個只工作在一個值之上函式,提升為工作在整個容器上的逐個元素上的函式。

定義

map作為Haskell的基本前序(prelude:就是標準庫)的一部份提供並被實現為:

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

在這個定義之中,涉及到四種不同的模式

  • f匹配「無論任何事物」的模式,並繫結f變數至所匹配的任何事物。
  • (x : xs)是匹配「非空串列」的模式,它是通過將要被繫結到x變數某個事物,cons(這裡是(:)函式)到要被繫結到xs變數的某個其他事物之上而形成的。
  • []是匹配「空串列」的模式,它不繫結任何變數。
  • _是匹配不被繫結的任何事物的模式(萬用字元即「不在意」模式)。

Lisp語言在1959年介入了叫做maplist的對映函式[1],與1958年出現的版本稍有不同[2]。這是maplist的最初定義,將一個函式連續的對映到整個列表和去除第一個元素餘下列表之上:

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

函式maplist在更新近的Lisp比如Common Lisp中仍可獲得到[3]Common Lisp提供對映函式家族,如mapcar和更一般性的map等,其中對應這裡所描述行為的那叫做mapcar,這裡的字尾car指示取列表第一個元素的CAR運算英語CAR and CDR

Remove ads

例子:對映一個列表

假定我們有一個整數的列表[1, 2, 3, 4, 5],並想要計算每個整數的平方。要完成這個任務,首先要定義一個函式square來做單一數值的平方,下面用Haskell演示:

square x = x * x

然後就可以呼叫:

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

它產生[1, 4, 9, 16, 25],展示了map遍歷了整個列表並應用函式square於每個元素。在MLHaskellF#中,函式是預設以柯里化形式定義的,從而map square是對列表的每個元素做平方的Haskell函式。

Lisp中,使用mapcar對列表的元素做平方,使用S-表達式表示法寫為:

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

使用函式maplist,上例將寫為:

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

可視的例子

下面將看到一個對映過程的每一步驟的可視演示,它依據函式將整數列表X = [0, 5, 8, 3, 2, 1]對映成新的列表X'

Thumb
在應用一個函式於一個列表時的處理步驟的演示

推廣

在Haskell中,多型函式map :: (a -> b) -> [a] -> [b],被推廣成多類型函式fmap :: Functor f => (a -> b) -> f a -> f b,它應用於屬於函子Functor類型類的任何類型上。

列表的類型構造子[]可以定義為Functor類型類別的實例,使用上例中的map函式:

instance Functor [] where
  fmap = map

其他Functor實例的例子包括樹:

-- 一个简单的二叉树
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)

在一個樹之上的對映產生:

>>> 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中指示函式複合英語Function composition (computer science)

尤其是,它允許為各種搜集定義逐個元素的運算。

此外,如果FG是兩個函子,自然變換是多型類型的函式,它遵守

,對於任何函式

如果函式是按上述類型定義那樣用參數多型定義的,這個規定總是滿足的。

Remove ads

最佳化

對映的數學基礎允許很多最佳化英語Program optimization。複合定律確保了如下二者:

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

導致相同的結果;就是說。但是第二種形式比第一種形式在計算上更加有效率,因為每個map要求從頭重建整個列表。因此,編譯器將嘗試將第一種形式變換第二種形式;這種類型的最佳化叫做「對映融合」,是迴圈融合英語Loop fission and fusion函數式類似者[4]

對映函式可以並經常依據fold比如foldr來定義,這意味著可以做「map-fold融合」:foldr f z . map g等價於foldr (f . g) z

在一個單鏈結串列上的map實現不是尾遞迴的,所以它在呼叫於大型列表的時候,可能在棧上建造大量的訊框。很多語言作為替代的提供「逆向map」函式,它等價於逆轉一個對映後的列表,但它是尾遞迴的。下面是利用了左fold函式的一個實現:

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

因為逆轉單鏈結串列也是尾遞迴的,reverse和reverse-map可以複合起來以尾遞迴方式進行正常的map,儘管這需要在這個列表上進行兩趟。

Remove ads

語言比較

對映函式出現在函數式程式設計語言之中。現在對映函式在很多程序式物件導向和多範式語言中也能獲得到(或能夠定義):在C++標準模板庫中,它叫做std::transform,在C#(3.0)的LINQ庫中,它被作為叫做Select的擴充方法。對映也經常在高階語言中的計算,比如ColdFusion標記式語言英語ColdFusion Markup Language(CFML)、PerlPythonRuby;在這四種語言中這個運算都叫做map 。在Ruby中還提供collect作為map的別名(來自Smalltalk)。有些語言通過語法構造提供與對映函式相同的功能。

對映有時被推廣為接收二元的(2個參數)函式,它可以把使用者提供的函式應用到來自兩個列表的對應元素上。有些語言對它使用特殊名字,比如「map2」或「zipWith」。使用顯式的可變元數函式的語言擁有可變元數版本的對映來支援可變元數函式。有2個或更多列表在這些列表有不同長度的時候遇到需要處理的問題。各種語言在這個問題上是不同的。有些引起異常。有些在達到最短列表長度之後停止並忽略在其他列表上的額外專案。有些繼續直到最長列表長度,並對已經結束的列表,向函式傳遞某個預留位置的值來指示沒有值。

更多資訊 語言, Map ...
Remove ads

參見

參照

Loading related searches...

Wikiwand - on

Seamless Wikipedia browsing. On steroids.

Remove ads