지도(고차 함수)

이 기사는 대체로 또는 전적으로 단일 출처에 의존한다. 관련 토론은 토크 페이지에서 찾을 수 있다. 추가 출처에 인용구를 도입하여 이 기사를 개선할 수 있도록 도와주십시오. 출처 찾기: "지도" 고차 기능 – 뉴스 · 신문 · 책 · 학자 · JSTOR (2012년 11월)

많은 프로그래밍 언어에서 map은 목록이나 세트와 같은 집합의 각 요소에 주어진 함수를 적용하는 고차 함수의 이름이며, 결과는 동일한 유형의 집합으로 반환된다. 기능적 형태로 고려할 때 흔히 적용-투-올(Apply-to-all)이라고 불린다.

지도의 개념은 목록에만 국한되지 않는다: 순차적 컨테이너, 나무와 같은 컨테이너, 또는 심지어 선물과 약속과 같은 추상적인 컨테이너에도 작용한다.

예제: 목록 매핑

우리가 정수의 목록을 가지고 있다고 가정하자. [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' $f{\displaystyle (}$ ${\displaystyle x}$)${\displaystyle }$= ${\displaystyle x}$+ ${\displaystyle 1}$ ${\displaystyle f(x)=x+1$} 함수:$$

리스트에서 지도 기능을 적용할 때의 처리 단계 보기

그 map 하스켈의 베이스 전주곡(예: "표준 라이브러리")의 일부로 제공되며, 다음과 같이 구현된다.

지도를 그리다 :: (a -> b) -> [a] -> [b] 지도를 그리다 _ []       = [] 지도를 그리다 f (x : xs) = f x : 지도를 그리다 f xs 

일반화

하스켈에서는 다형성 함수 map :: (a -> b) -> [a] -> [b] 다형 함수로 일반화됨 fmap :: Functor f => (a -> b) -> f a -> f b , 형식 클래스에 속하는 모든 형식에 적용된다.

리스트 유형 생성자 [] 의 예로서 정의할 수 있다. Functor 를 사용하여 클래스를 타이핑하다. map 이전 예에서 나온 기능:

예시 펑터 [] 어디에   fmap = 지도를 그리다 

의 다른 예 Functor 예시로는 트리를 들 수 있다.

- 단순한 이진수 자료 나무 a = 잎 a   포크 (나무 a) (나무 a)  예시 펑터 나무 어디에     fmap f (잎 x) = 잎 (f x)   fmap f (포크 l r) = 포크 (fmap f l) (fmap f r) 

트리를 통한 매핑:

>>> fmap 정사각형의 (포크 (포크 (잎 1) (잎 2)) (포크 (잎 3) (잎 4))) 포크 (포크 (잎 1) (잎 4)) (포크 (잎 9) (잎 16)) 

의 모든 예에 대해 Functor 유형 클래스, fmap 계약상 감독자 법률을 준수해야 한다.

fmap id      ≡ id              -- 신원법 fmap (f . g) ≡ fmap f . fmap g -- 작곡법 

어디에 . 하스켈의 함수 구성을 나타낸다.

다른 용도 중에서도, 이것은 다양한 종류의 수집품에 대한 요소별 연산을 정의할 수 있다.

더욱이 F와 G가 두 개의 펑커라면 자연적 변환은 다형 $h$의 함수다 :${\displaystyle \mathrm{:}}$ ${\displaystyle T.}$ ${\displaystyle F}$ (${\displaystyle T}$)${\displaystyle }$→ ${\displaystyle G}$( T${\displaystyle }$) ${\displaysty h:\forall T.$fmap과 관련된$$ $F(T)\to G(T)}:$

${\$$모든$ 함수 $f{\displaystyle }$: ${\displaystyle X}$→ ${\displaystyle Y}$에$대한$ Y$}\circle \operatorname {fmap}(f)=\operatorname {fmap}(f)\circ h_$${X$

h 함수가 위의 형식 정의에서와 같이 파라메트릭 다형성에 의해 정의되는 경우, 이 규격은 항상 충족된다.

최적화

지도에 대한 수학적인 기초는 여러 가지 최적화를 허용한다. 구성법은 두 가지 모두를 보장한다.

• (map f . map g) list 그리고
• map (f . g) list

같은 결과로 이어짐, 즉 ${\displaystyle \mathrm{지도}}$ ${\displaystyle \mathrm{map}}$(${\displaystyle f}$ )${\displaystyle =}$ 지도${\displaystyle }$ ( g${\displaystyle }$)${\displaystyle }$= 지도${\displaystyle f}$ (${\displaystyle f)}$ g ) $\displaystyle \operatorname {map} (f)\circule \operatorname {map} (g)$ =\$operatorname {map} (f\circirg$ 그러나 두 번째 양식은 각각이 첫 번째 형태보다 계산이 더 효율적이다. map 처음부터 전체 목록을 다시 작성해야 한다. 따라서 컴파일러는 첫 번째 형태를 두 번째 형태로 변환하려고 시도할 것이다; 이러한 유형의 최적화는 지도 융합으로 알려져 있으며 루프 융합의 기능적 아날로그다.^[1]

지도 기능은 다음과 같은 접이식 측면에서 정의될 수 있으며 종종 다음과 같이 정의된다. foldr즉, 맵폴드 융합을 할 수 있다는 뜻이다. foldr f z . map g 와 같다 foldr (f . g) z.

단독 링크된 리스트에서 위의 지도를 구현하는 것은 꼬리가 재귀적이지 않기 때문에, 큰 리스트로 호출할 때 스택에 많은 프레임을 쌓을 수 있다. 많은 언어가 번갈아 가며 '역지도' 기능을 제공하는데, 이는 매핑된 목록을 역순으로 나열하는 것과 맞먹지만 꼬리가 재생된다. 여기 왼쪽 접이식 기능을 활용한 구현이 있다.

역지도 f = 접다 (\ys x -> f x : ys) [] 

단독으로 연결된 리스트의 역방향도 꼬리가 반복되므로, 리스트 위로 두 번의 패스를 수행해야 하지만, 역방향 및 역방향 맵을 구성하여 꼬리가 반복되는 방식으로 정상 맵을 수행할 수 있다.

언어비교

지도 기능은 기능 프로그래밍 언어에서 비롯되었다.

Lisp라는 언어는 지도 함수를 도입했다. maplist^[2] 1959년에, 약간 다른 버전이 이미 1958년에 나타났다.^[3] 이것은 에 대한 원래의 정의다. maplist, 연속된 정지 목록에 함수를 매핑하는 방법:

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

함수 maplist Common Lisp과 같은 최신 Lisps에서 여전히 사용할 수 있지만,^[4] 다음과 같은 기능들 mapcar 또는 보다 일반적인 map 더 선호할 겁니다

리스트의 요소들을 제곱하기 위해 maplist 다음과 같이 S-표현 표기법으로 쓰일 것이다.

(지도 목록 (람다 (l) (sqr (자동차 l))) '(1 2 3 4 5)) 

기능 사용 mapcar, 위의 예는 다음과 같이 쓰일 것이다.

(맵카 (기능을 하다 sqr) '(1 2 3 4 5)) 

오늘날 매핑 기능은 많은 절차적, 객체 지향적 및 다중 패러다임 언어에서도 지원(또는 정의될 수 있음)된다. C++의 표준 라이브러리에서는 이 라이브러리를 다음과 같이 부른다. std::transform, C#(3.0)의 LINQ 라이브러리에서, 라고 하는 확장 방법으로 제공된다. Select. 맵은 CFML(ColdFusion Markup Language), Perl, Python, Ruby와 같은 고급 언어에서도 자주 사용되는 작업으로, 이 작업을 호출한다. map 이 4개 국어를 모두 사용할 수 있다. a collect 의 가명. map 루비(스몰토크에서)에서도 제공된다. Common Lisp은 지도와 같은 기능을 제공한다. 여기서 설명하는 동작에 해당하는 것을 다음과 같이 부른다. mapcar (-car CAR 작동을 사용하여 접근을 표시한다. 또한 지도 기능과 동일한 기능을 제공하는 구문 구조를 가진 언어도 있다.

맵은 사용자 제공 기능을 두 리스트의 해당 요소에 적용할 수 있는 디아디드(2-argument) 기능을 수용하기 위해 일반화되기도 한다. 일부 언어에서는 map2 또는 zipWith와 같은 특수 이름을 사용한다. 명시적 가변 함수를 사용하는 언어는 가변 아리티 함수를 지원하기 위해 가변 아리티가 있는 지도 버전을 가질 수 있다. 목록이 2개 이상 있는 지도는 목록의 길이가 다를 때 처리 문제가 발생한다. 이에 대해서는 다양한 언어가 다르다. 어떤 사람들은 예외를 제기한다. 어떤 사람들은 가장 짧은 리스트의 길이 이후에 멈추고 다른 리스트의 추가 항목을 무시한다. 일부는 가장 긴 목록의 길이까지 계속되며, 이미 종료된 목록의 경우 일부 자리 표시자 값을 값이 없음을 나타내는 함수에 전달한다.

1급 기능과 쿠레이팅을 지원하는 언어에서는 map 예를 들어, 전체 컨테이너에서 작동하는 원소-현상 등가물에 한 값만 작용하는 함수를 들어올리기 위해 부분적으로 적용할 수 있다. map square 리스트의 각 요소를 정사각형으로 배열하는 하스켈 함수다.

참고 항목

• 펑터(기능 프로그래밍)
• 지핑(컴퓨터 과학) 또는 zip, 여러 목록에 'list' 매핑
• 필터(고차 함수)
• 접기(고차 함수)
• 앞을 내다
• 프리 모노이드
• 기능 프로그래밍
• 고차함수
• 목록 이해
• 지도(병렬 패턴)

참조