고차 함수

3. 주요 특징

고차 함수는 함수를 인자로 받거나 결과로 반환하는 함수이다. 이는 함수형 프로그래밍의 핵심 개념으로, 코드 재사용성과 추상화 수준을 높여준다. 함수를 데이터처럼 취급할 수 있게 해주는 것이다.^[2][3]

C나 파스칼에서는 함수 포인터를 이용하여 고차 함수를 흉내낼 수 있지만, 함수 포인터로 일급 함수를 지원한다고 보지는 않는다. 고차 함수는 주로 함수형 프로그래밍 언어나 그 배경 이론인 람다 계산법에서 많이 사용된다.

어떤 함수의 인수가 되는 함수는 '''함수 인수'''^[2] 또는 '''절차 인수'''^[3]라고 부르기도 한다.

3. 1. 함수를 인자로 받는 함수

다음은 주어진 함수에 인자 2와 3을 전달하여 호출하고 반환값을 반환하는 고차 함수 `apply_2_3`의 예시이다.



(define (add x y) (+ x y))

(define (mul x y) (* x y))

(define (apply_2_3 f) (f 2 3))

(apply_2_3 add) ; => (add 2 3) => 5

(apply_2_3 mul) ; => (mul 2 3) => 6



이 외에도 apply, 함수 합성, 적분, 콜백, 트리 순회, 몬테규 문법 등에서 고차 함수가 활용된다.

3. 1. 1. map 함수

map 함수는 함수 ''f''와 요소들의 모음을 인자로 받아, 모음의 각 요소에 ''f''를 적용한 새로운 모음을 결과로 반환하는 고차 함수의 한 예시이다. 리스트 구조의 각 요소에 대해 순차적으로 주어진 함수를 처리하며, 함수형 프로그래밍이 아닌 패러다임의 언어에서도 구현되어 있는 경우가 있다.

예를 들어, 리스트 '(1 2 3)의 각 요소에 1을 더한 리스트를 얻고 싶을 경우 다음과 같이 할 수 있다.

```scheme

(map (lambda (n) (+ 1 n)) '(1 2 3))

;=> '(2 3 4)

3. 1. 2. filter 함수

필터는 컬렉션의 각 요소에 대해 주어진 조건(함수)을 만족하는 요소만 추출하여 새로운 컬렉션을 반환한다.

리스트의 각 요소를 각각 인수로 전달하여 인수로 전달된 함수를 호출하고, 그 반환값이 참이면 반환값 리스트에 남기고, 거짓이면 제외한다. 제외하고 싶은 요소에 대해 거짓 값을 반환하는, 술어와 같은 역할을 하는 함수를 주어 사용한다.<sup>[4]</sup>

예를 들어, 리스트 '(1 2 -3 -4 5)에서 양수만 추출하려면 다음과 같이 한다.<sup>[4]</sup>

```scheme

(filter positive? '(1 2 -3 -4 5))

;=> '(1 2 5)

3. 1. 3. reduce (fold) 함수

고차 함수의 일종인 ''fold'' 함수는 중첩, 누산, 겹침, 접기 등으로 불리며, 영어로는 ''reduce'' 또는 ''inject''라고도 한다. fold는 리스트의 각 요소에 주어진 함수를 적용하여 하나의 값을 만든다.

```scheme

(fold func returns-first list)

```

예를 들어, 리스트 '(1 2 3)의 각 요소의 총합을 구하려면 다음과 같이 할 수 있다.

```scheme

(fold + 0 '(1 2 3))

;=> 6

```

오른쪽 방향 겹침(''foldr'')과 왼쪽 방향 겹침(''foldl'')이 있으며, 프로그래밍 언어에 따라 처음부터 유사한 기능이 내장되어 있는 경우도 있다. (자세한 내용은 fold의 영어판 기사 참조)

```scheme

(fold-right + 0 '(1 2 3))

;=> 6

; (+ 1 (+ 2 (+ 3 0)))과 동일

(fold-right cons '(0) '(1 2 3))

;=> '(1 2 3 0)

; (cons 1 (cons 2 (cons 3 '(0))))과 동일

```

```scheme

(fold-left + 0 '(1 2 3))

;=> 6

;(+ (+ (+ 0 1) 2 ) 3) 과 동일

(fold-left cons '(0) '(1 2 3))

;=> '((((0) . 1) . 2) . 3)

;(cons (cons (cons '(0) 1) 2 ) 3) 과 동일

3. 2. 함수를 반환하는 함수

함수를 반환하는 함수는 특정 동작을 수행하는 함수를 동적으로 생성하는 데 사용될 수 있다. 이러한 방식은 클로저와 함께 사용될 때 특히 유용하다.

고차 함수 `twice`는 함수를 인자로 받아, 어떤 값에 해당 함수를 두 번 적용한다. 만약 `twice`를 같은 함수 `f`에 대해 여러 번 적용해야 한다면, 값을 받는 대신 함수를 반환하는 것이 더 효율적이다. 이는 "반복 금지" 원칙을 따르는 방법이다.

3. 2. 1. 커링 (Currying)

커링은 여러 인수를 받는 함수를 단일 인수 함수로 변환하는 기법이다. 예를 들어 두 숫자를 더하는 함수 `add`는 다음과 같이 표현할 수 있다.<sup>[1]</sup>

일반적인 정의와 호출 방식은 다음과 같다.

```scheme

; 일반적인 정의, 호출

(define (add x y) (+ x y))

(add 2 3) ;=> 5

```

커링을 적용하면 다음과 같이 정의하고 호출할 수 있다.

```scheme

; 커링을 적용한 정의, 호출

(define (add x) (lambda (y) (+ x y)))

((add 2) 3) ;=> 5

```

일부 프로그래밍 언어는 내장 함수가 처음부터 커링되어 있다. 이는 함수 호출이 항상 1개의 인수를 받는 함수를 반환하도록 정의하는 것과 같다. 즉, n개의 인수를 받는 함수를 n개 인수의 직곱을 받는 함수로 정의하는 대신, 1개의 인수를 받는 고차 함수를 n개 나열한 것과 같은 형식으로 정의한다.^[1]

예를 들어 하스켈에서는 다음과 같이 표현할 수 있다.^[1]

```haskell

(2 +)

```

이는 앞서의 `(add 2)`와 마찬가지로, 2를 더하는 함수가 된다. `+` 함수가 이미 커링되어 있기 때문에, 1개의 인수를 적용하는 것만으로 함수로서 작동한다.^[1] 다음은 실행 예시다.

```haskell

Prelude> 2 + 3

5

Prelude> (2 +) 3

5

4. 프로그래밍 언어별 지원 현황

다양한 프로그래밍 언어에서 고차 함수를 지원하며, 각 언어마다 구현 방식과 특징이 조금씩 다르다.

• 많은 함수형 프로그래밍 언어에서 발견되는 `map` 함수는 고차 함수의 한 예시이다.
• 정렬 함수는 비교 함수를 매개변수로 받아, 프로그래머가 정렬 알고리즘을 정렬되는 항목의 비교와 분리할 수 있게 한다. C 표준 함수 `qsort`가 그 예이다.<sup>[1]</sup>
• 필터<sup>[4]</sup>
• 접기
• apply
• 함수 합성
• 적분
• 콜백
• 트리 순회
• 자연어의 의미론적 이론인 몬테규 문법은 고차 함수를 사용한다.

4. 1. 함수형 언어

4. 2. 비함수형 언어

5. 대안

함수 포인터는 C, C++, 포트란, 파스칼과 같은 언어에서 함수에 대한 참조를 전달할 수 있게 해준다. 다음 C 코드는 임의의 함수의 적분 근사값을 계산한다.<sup>[1]</sup>

```c

#include

double square(double x)

{

return x * x;

}

double cube(double x)

{

return x * x * x;

}

/* f()의 [a,b] 구간에서의 적분을 계산 */

double integral(double f(double x), double a, double b, int n)

{

int i;

double sum = 0;

double dt = (b - a) / n;

for (i = 0; i < n; ++i) {

sum += f(a + (i + 0.5) * dt);

}

return sum * dt;

}

int main()

{

printf("%g\n", integral(square, 0, 1, 100));

printf("%g\n", integral(cube, 0, 1, 100));

return 0;

}

```

C 표준 라이브러리의 qsort 함수는 고차 함수의 동작을 에뮬레이션하기 위해 함수 포인터를 사용한다.^[1]

매크로는 고차 함수의 일부 효과를 얻는 데에도 사용될 수 있다. 하지만, 매크로는 변수 포획 문제를 쉽게 피할 수 없으며, 많은 양의 중복된 코드를 생성할 수 있는데, 이는 컴파일러가 최적화하기 더 어려울 수 있다. 매크로는 일반적으로 강력한 유형을 가지지 않지만, 강력한 유형의 코드를 생성할 수 있다.^[1]

다른 명령형 프로그래밍 언어에서는 고차 함수를 통해 얻는 것과 동일한 알고리즘 결과를 평가 범위 내에서 코드를 동적으로 실행(때로는 ''Eval'' 또는 ''Execute'' 연산이라고 함)하여 달성할 수 있다. 이 접근 방식에는 다음과 같은 상당한 단점이 있을 수 있다.^[1]

• 실행될 인자 코드는 일반적으로 정적으로 타입 지정되지 않는다. 이러한 언어는 일반적으로 실행될 코드의 적합성과 안전성을 결정하기 위해 동적 타이핑에 의존한다.^[1]
• 인자는 일반적으로 런타임까지 그 값을 알 수 없는 문자열로 제공된다. 이 문자열은 프로그램 실행 중에 JIT 컴파일을 사용하여 컴파일되거나 인터프리테이션을 통해 평가되어 런타임에 약간의 추가 오버헤드를 발생시키고 일반적으로 덜 효율적인 코드를 생성한다.^[1]

참조

_[1] 웹사이트 PHP: Arrow Functions - Manual https://www.php.net/[...] 2021-03-01
_[2] 문서 functional argument/parameter
_[3] 문서 procedural argument/parameter
_[4] 웹사이트 http://www.shido.inf[...]
_[5] 웹사이트 Functional Programming - Implementing Scan (Prefix Sum) using Fold http://stackoverflow[...] 2014-09-14
_[6] 뉴스 로드맵수학학원 - 수학 공부의 틀을 바꾸는 종횡무진 학습법 http://www.naeil.com[...] 내일신문 2014-10-17
_[7] 뉴스 PART 01. 의심스러운 토대 위에 싹트다 http://www.dongascie[...] 동아사이언스 2015-08-27
_[8] 뉴스 함수 언어 : 3대 함수 언어 전문가가 말하는 정체와 역할 http://www.itworld.c[...] ITWorld 2016-02-19